《大数据结构》试题总汇编(带答案) 下载本文

实用标准文档

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;ilength;++i){ if(L->elem[i]!=x){

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; } } }

文案大全