25. 起泡排序在最好情况下的比较次数为 ，最坏情况下为
。
（最好正序C=n-1，最坏逆序C=n*(n-1)/2）
26. 起泡排序在最好情况下的移动次数为 ，最坏情况下为
。
（最好正序M=0，最坏（逆序）M=3*n*(n-1)/2）
27. 在直接选择排序中，排序码比较次数的时间复杂度为O( n^2 )。
28. 在直接选择排序中，数据对象移动次数的时间复杂度为O( n )。
29. 快速排序在平均情况下的时间复杂度为O( nlog2n )。
30. 快速排序在最坏情况下的时间复杂度为O( n2 )。
三、简答题
1. 下面程序段的时间复杂度是 O(n*m) 。
for(i=0;i 2. 下面程序段的时间复杂度是 O(n^0.5) 。 i=s=0; while(s 3. 下面程序段的时间复杂度是O(n^2) 。 s=0; for(i=0;i 4. 下面程序段的时间复杂度是O(log3n) 。 i=1; while(i<=n) i=i*3; 5. 写出下列程序段的输出结果: 514263 。 void main( ) { SqStack S; SqQueue Q; int i,j,n=6,e; for(i=1;i<=n;++i)Push(&S,i); for(i=1;i<=n;++i){ Pop(&S,&e); EnQueue(&Q,e); DeQueue(&Q,&e); EnQueue(&Q,e); } for(i=1;i<=n;++i){ DeQueue(&Q,&e); Push(&S,e); } for(i=1;i<=n;++i){ Pop(&S,&e); printf(\} 6 6. 已知一棵二叉树的前序和中序序列，画图并求该二叉树的后序序列。 前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 后序序列： 7. 已知一棵二叉树的中序和后序序列如下，画图并求该二叉树的前序序列。 中序序列：c, b, d, e, a, g, i, h, j, f 后序序列：c, e, d, b, i, j, h, g, f, a 前序序列： 8. 有7个带权结点，其权值分别为3, 7, 8, 2, 6, 10, 14，试以它们为叶结点生成一棵赫夫曼树， 求出该树的带权路径长度： 9. 设连通图G如图所示。试给出对它执行从顶点V0开始的广度优先遍历和深度优先遍历的结果。 广度优先遍历：012345678 深度优先遍历：013256784 V0 V2 V5 V3 V8 V6 V1 V4 V7 10. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。（写出加入生成树顶点 集合S和选择边Edge的顺序） 0 9 10 边(顶点，顶点，权值) 顶点集合 7 0 1 2 ( 0 ， 1 ， 9 ) 5 7 6 01 ( 1 ， 3 ， 5 ) 11 8 3 4 5 013 ( 1 ， 2 ， 7 ) 0132 01324 013245 11. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。 8 顶点号 1 3 2 4 ( 2 ， 4 ， 6 ) ( 2 ， 5 ， 7 ) 路径长度 4 7 8 10 路径 01 03 012 0124 0 4 1 7 9 3 5 2 2 4 1 4 7 12. 试对下图所示的AOE网络 2 (1) 这个工程最早可能在什么时间结束。 1 4 (2) 确定哪些活动是关键活动。画出由所有关键活动构15 成的图，指出哪些活动加速可使整个工程提前完成。 3 拓扑序列132456 每个顶点的最早发生时间、最迟发生时间： 1(0,0),3(15,15),2(19,19),4(29,37),5(38,38),6(43,43) 2 10 19 4 6 6 11 5 5 工期：43天 每个活动的最早开始时间、最迟开始时间： 1-2(0,17),1-3(0,0),3-2(15,15),3-5(15,27),2-5(19,19),2-4(19,27) 5-6(38,38),4-6(29,37) 13. 一个一维数组a[10]中存储着一个有序表，该有序表为：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 )，画出折半搜索所对应的判定树，并求出在等概率情况下搜索成功的平均搜索长度。 平均搜索长度： 2.9 14. 给定一组数据对象的排序码为 {46, 79, 56, 38, 40, 84}，对其进行一趟快速排序， 结果为 40,38,46,56,79,84 。 四、算法设计题 1. 设有一个顺序表 (e0, e1, …, en-2, en-1)。请编写一个函数将这个顺序表原地逆置，即顺序表的内 容置换为 (en-1, en-2, …, e1, e0)。 void Reverse(SqList *L){ int i=0,j=L->length-1; ElemType t; for(;i 2. 试编写一个函数，用以删除顺序表L中所有值为x的元素（要求就地工作）。 void DeleteX(SqList *L, ElemType x){ int j=0; for(i=0;i if(i>j) L->elem[j]=L->elem[i]; ++j; } } L->length =j; } 8 3. 试编写一个函数，在数组R（已正序排列）中进行折半查找某个值k，找到则返回其位置，否则返回0。 int SearchBin(int R[], int n, int k){ //有序（正序）的顺序表的二分查找，n为数组元素个数，k为待查找的值 int low=0,high=n-1,mid; while(low<=high){ mid=(low+high)/2; if(R[mid]==k)return mid+1; else if(R[mid]>k) high=mid-1; else low=mid+1; } return 0; } 4. 试编写一个函数，对数组r进行选择法排序（结果为正序）。 void SelectSort(ElemType r[],int n){ //对顺序表r作简单选择排序，n为数组元素个数 int i,j,k; ElemType tmp; for(i=0;i for(j=i+1;j tmp=r[i]; r[i]=r[k]; r[k]=tmp; } } } 9 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构》试题汇编(带答案)(2)在线全文阅读。
相关推荐：