数据结构习题汇总(北邮)

北邮数据结构实验报告实验名称：实验四排序学生姓名：XXX班级：XXX班内序号：XX学号：XXX日期：2013年12月20日1．实验要求a. 实验目的通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

b. 实验内容使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、归并排序8、基数排序（选作）9、其他2. 程序分析2.1 存储结构存储结构:顺序存储结构示意图如下:2.2 关键算法分析核心算法思想：1.利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。

2.将数组名当做地址传入函数，实现快速调用和统计。

使得程序代码可读性增、结构更加优化。

关键算法思想描述和实现：关键算法1：实现七种算法的基本排序功能。

1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

2、希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

3、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。

4、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

5、选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。

6、堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。

7、归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。

C++实现：void Insert(int r[],int n) //直接插入排序，升序{int compare=0,move=0; 定义比较和移动的系数并初始化为零，以下相同不再叙述 for(int i=2;i<n;i++) 将数组中的数一个一个放入序列{if(r[i]<r[i-1]) 第一个位置当做哨兵，从第二个开始，若后面的数不比前面的数大则将哨兵入列，较小的数作为新哨兵{r[0]=r[i];int j;for (j=i-1;r[0]<r[j];j--) 若后面的数比哨兵大，则直接放进数列{r[j+1]=r[j];move++; 每进行一次上移动从操作则移动加1}r[j+1]=r[0];}compare++; 每判断一次比较加1}cout<<"比较次数："<<compare<<" 移动次数："<<move<<endl;}void ShellInsert(int r[],int n) //希尔排序{int compare=0,move=0;for(int d=n/2;d>=1;d=d/2) 主要思想每次循环跨越的步子折半{for(int i=d+1;i<n;i++) 依次比较每一个下标等差增长的数列{if(r[i]<r[i-d]) 判断，小的值放前面{r[0]=r[i];int j;for(j=i-d;j>0&&r[0]<r[j];j=j-d) 比较没一个数列内的元素r[j+d]=r[j];r[j+d]=r[0];move++;}compare++;}}cout<<"比较次数："<<compare<<" 移动次数："<<move<<endl;}void BubbleSort(int r[],int n) //改进后的冒泡排序{int compare=0,move=0;int pos=n;while(pos!=0) 判断循环的结束条件，下面会有介绍{int bound=pos;pos=0; 令pos初始化为0，之后如果没有进入循环修改其值则跳出while循环for(int i=1;i<bound-1;i++) bound为每次循环需要进行的次数，因为排好序的元素不需要再进行比较if(r[i]>r[i+1]) 大数后置{r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];pos=i+1;move++;}compare++;}}cout<<"比较次数："<<compare<<" 移动次数："<<move<<endl;}int Partion(int r[], int first, int end,int a,int b) //一次快排{int i=first; 头int j=end; 尾int pivot=r[i]; 哨兵while(i<j) 头在尾之前，即尚未遍历数组{while((i<j)&&(r[j]>=pivot)) 右侧扫瞄，大于哨兵的不动j--;a++;}r[i]=r[j]; 小小于哨兵的进入哨兵b++;while((i<j)&&(r[i]<=pivot)) 进行左侧扫描，小于哨兵的写入数组{i++;a++;}r[j]=r[i]; 否则，进入哨兵b++;}r[i]=pivot; 哨兵入列return i;}void Qsort(int r[],int i,int j) //运用递归实现多次快排{if(i<j){int pivotloc=Partion(r,i,j,a,b); 依次分割排序区间Qsort(r,i,pivotloc-1);Qsort(r,pivotloc+1,j);}}void SelectSort(int r[],int n) //简单选择排序{int compare=0,move=0;for(int i=1;i<n;i++) 目前比较开始的元素{int min=i; 为了判断目前的元素是否为最小for(int j=i+1;j<n;j++) 那当前元素和之后的元素比较{if(r[j]<r[min]) 找出最小当前最小的元素并贴上标记min=j;compare++;}if(min!=i) 如果标记被改变，就交换标记改变前后位置的元素，否则标记的元素即为最小不用改变{r[0]=r[i];r[i]=r[min];r[min]=r[0];move++;}}cout<<"比较次数："<<compare<<" 移动次数："<<move<<endl;}void Sift(int r[],int k,int m) //小根堆的筛选{int i=k,j=2*i;while(j<=m) 循环结束的条件，最后的子节点大于总结点{if(j<m&&r[j]>r[j+1]) 比较左右孩子的大小，并将j指向较小的孩子j++;if(r[i]<r[j]) 父节点比最大的子节点小则该堆建成，跳出循环break;else 否则把父节点往下筛{r[0]=r[j];r[j]=r[i];r[i]=r[0];i=j;j=2*i;}}}void HeapSort(int r[],int n) //小根堆排序{for(int i=n/2;i>=1;i--) 从最后一个有字节点的节点开始建小根堆Sift(r,i,n);for(int i=1;i<n;i++) 依次取出每一个小跟对的根节点，再重新筛，形成有序数列{r[0]=r[n-i+1];r[n-i+1]=r[1];r[1]=r[0];Sift(r,1,n-i);}void Merge(int r[],int r1[],int s,int m,int t,int *c,int *d) r为要排序的数组，r1为缓冲数组，s为第一个序列开始的位置，m为第一个序列的结束的位置，t为第二个序列的结束位置，c为比较次数的指针，d为移动次数的指针{int i=s; 定义两个要归并的序列的起始位置int j=m+1;int k=s;while(i<=m&&j<=t) 循环条件，两个序列都不空{if(r[i]<r[j]) 将小数写进缓冲数组，小数对应的序列比较值后一一位{r1[k++]=r[i++];(*d)++;}else{r1[k++]=r[j++];(*d)++;}(*c)++;}if(i<=m) 当一个序列穷尽时，将另一个序列抄进缓冲数组while(i<=m){r1[k++]=r[i++];(*d)++;}if(j<=t)while(j<=t){r1[k++]=r[j++];(*d)++;}}void MergePass(int r[],int r1[],int n,int h,int *c,int *d) 将一个数组一次拆分成长度不同的小数组再两两归并{int i=1;while(i<=n-2*h+1) h为本次小序列的长度，当能拆成两个等长的序列时，拆出该序列进行归并{Merge(r,r1,i,i+h-1,i+2*h-1, c, d);i+=2*h; 每次归并完，序列长度增加一倍，再次归并}if(i<n-h+1) 当只能拆出一个单位长度的序列和一个残缺序列时，只将第二个序列归并到最大长度nMerge(r,r1,i,i+h-1,n,c,d);Else 只能拆出一个残序列时，只把该序列抄进缓冲数组即可for(;i<=n;i++){r1[i]=r[i];(*d)++;}}void MergeSort(int r[],int r1[],int n){int compare=0,move=0;int h=1; 起始拆分的序列长度定义为一，即每个数都需要进行比较 while(h<n) 依次展长序列长度进行归并{MergePass(r,r1,n,h,&compare,&move);h=2*h;for(int i=1;i<=n;i++) 将缓冲数组里的有序数写进原数组{r[i]=r1[i];move++;}}cout<<"比较次数："<<compare<<" 移动次数："<<move<<endl;}关键算法2：获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。

2022年北京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

S1 T
数据结构---第四章 串 11
S2
Status SubString(HString &Sub, HString S, int pos, int len) //求串S从第pos个字符起长度为len的子串Sub { if ( (pos<1 || pos >S.length || len<0 || len > S.length-pos+1 ) return ERROR; if (Sub.ch) free(Sub.ch); if ( !len ) { Sub.ch=NULL; Sub.length=0; } else { if ( !(Sub.ch=(char *)malloc(len* sizeof(char)))) exit(OVERFLOW); Sub.ch[0..len-1]=S.ch[pos-1..pos+len-2]; Sub.length=len; } pos-1 0 S.length-1 return OK; } // SubString len
数据结构---第四章 串 2
4.1.2 串的常用基本操作 (1)用串常量赋值 用串变量赋值 (2)判定空串 (3)两串比较 (4)求串长 (5)串清空 (6)两串连接 (7)求子串 (8)子串定位 (9)子串置换 (10)插入子串 (11)删除子串 (12)串销毁 StrAssign(&T, chars) StrCopy(&T, S) StrEmpty(S) StrCompare(S, T) StrLength(S) ClearString(&S) Concat(&T, S1, S2) SubString(&Sub, S, pos, len) Index(S, T, pos) Replace(&S, T, V) StrInsert(&S, pos, T) StrDelete(&S, pos, len) DestroyString(&S)

北邮数据结构与算法课后答案第7章第7章1.选择题（1）A （2）C （3）C （4）D （5）D （6）C （7）B （8）C （9）D （10）C2.判断题（1）√ （2）Ⅹ （3）√ （4）Ⅹ （5）Ⅹ （6）√ （7）Ⅹ （8）√ （9）√ （10）√3.简答题（1）以关键字序列（tim,kay,eva,roy,dot,jon,kim,ann,tom,jim,guy,amy）为例，手工执行以下排序算法（按字典序比较关键字的大小），写出每一趟排序结束时的关键字状态：1）直接插入排序；2）冒泡排序；3）直接选择排序；4）快速排序；5）归并排序；6）基数排序。

【解答】略。

（2）已知序列{50,18,12,61,8,17,87,25}，请给出采用堆排序对该序列做升序排序时的每一趟结果。

【解答】堆排序过程如下图示：1887 12178255061618712178185025（3）有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最小？为什么？【提示】采用基数排序。

基数排序是一种借助多关键码排序思想对单关键码进行排序的方法，它适合n很大，而关键码较小的序列。

本题中英文单词数目n>>50，而单词长度m<5，因此采用基数排序方法最佳。

（4）如果只想得到一个含有n个元素的序列中第k（k<<n）小元素之前的部分排序序列，最好采用什么排序方法？为什么？如有这样一个序列：{57,11,25,36,18,80,22}得到其第3个最小元素之前的部分序列{11,18,22}，使用所选择的算法实现时，要执行多少次比较？< p="">【解答】采用堆排序。

简单选择排序和冒泡排序可以在一趟排序后选出一个最大（或最小）元素，要比较n-1次，选次大元素要再比较n-2次,…其时间复杂度是O(n2)。

当k<<n时，从n个元素中选k 个元素不能使用这种方法。