实用标准文档
7. 用简单的模式匹配算法在主串\中检索子串”string”，总的比较次数为 12 。
8. 假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为 5 。假定根结点的高度为1。
9. 在一棵高度为3的四叉树中，最多含有 21 结点。
10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为
0的结点数有 6 个。
11. 一棵高度为5的完全二叉树中，最多包含有 31个结点。假定根结点的高度为1。
12. 在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶结点数
为 6个。
13. 假定一棵二叉树的结点个数为18，则它的最小高度为 5 。假定根结点的高度为1。
14. 按照二叉树的定义，具有5个结点的二叉树有 42 种形态。
15. 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为 O(n) 。
16. 对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi，搜索长度（即在搜索过程中依次同
有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为
n 。
ASL?pici i?117. 假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度
为 20.5 。
18. 以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为 O(log2n) 。
19. 从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为 3 。
20. 假定对长度n = 50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为 19 个。
21. 直接插入排序在最好情况下的比较次数为 ，最坏情况下为 。
（正序最好C=n-1，逆序最坏C=n*(n-1)/2）
22. 直接插入排序在最好情况下的移动次数为 ，最坏情况下为 。
（最好M=0，最坏M=(n+4)*(n-1)/2）
23. 简单选择法排序时比较数据的次数为 。（任何情况下C=n*(n-1)/2）
24. 简单选择法排序在最好情况下的移动次数为 ，最坏情况下为 。
（最好正序M=0，最坏（非逆序，如6,1,2,3,4,5）M=3*(n-1)）
?文案大全
实用标准文档
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 )。
2
30. 快速排序在最坏情况下的时间复杂度为O( n )。
三、简答题
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. 已知一棵二叉树的前序和中序序列，画图并求该二叉树的后序序列。 前序序列：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开始的广度优先遍历和深度优先遍历的结果。 V0 广度优先遍历：012345678 V2 V1 深度优先遍历：013256784 V5 V4 V3 V7 V8 V6 10. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。（写出加入生成树顶点集 合S和选择边Edge的顺序） 0 9 10 顶点集合 边(顶点，顶点，权值) 7 1 2 0 ( 0 ， 1 ， 9 ) 5 7 6 01 ( 1 ， 3 ， 5 ) 11 8 3 4 5 013 ( 1 ， 2 ， 7 ) 0132 01324 013245 ( 2 ， 4 ， 6 ) ( 2 ， 5 ， 7 ) 11. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。 8 顶点号 1 3 2 4 文案大全 路径长度 4 7 8 10 路径 01 03 012 0124 0 4 1 7 9 3 5 2 2 4 1 4 实用标准文档 10 2 12. 试对下图所示的AOE网络 4 2 6 (1) 这个工程最早可能在什么时间结束。 1 19 6 4 (2) 确定哪些活动是关键活动。画出由所有关键活动构成15 11 5 的图，指出哪些活动加速可使整个工程提前完成。 5 3 拓扑序列132456 每个顶点的最早发生时间、最迟发生时间： 1(0,0),3(15,15),2(19,19),4(29,37),5(38,38),6(43,43) 工期：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 t=L->elem[i]; L->elem[i]=L->elem[j]; L->elem[j]=t; } } 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; } 文案大全 实用标准文档 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 }//k指向r[i~n-1]中的最小元素 if(k!=i){ tmp=r[i]; r[i]=r[k]; r[k]=tmp; } } } 文案大全