实用标准文档
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; } } } 文案大全