《数据结构》期末复习题答案

1、1. 以下与数据的存储结构无关的术语是（ c ）C、哈希表2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5 个元素的地址是（ B ）B、 1083. 假设带头结点的单向循环链表的头指针为head®该链表为空的判定条件是（ C ）C、head >next= =head4. 若进栈序列为1，2，3，4， 5， 6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（D ）D、2， 3，5，1，6，45. 下列关键字序列中，构成小根堆的是（A ）A、 12 ， 21， 49， 33， 81， 56， 69， 416. 下列数据结构中，不属于二叉树的是（A ）A

2、、 B 树7. 用顺序存储的方法来存储一棵二叉树，存放在一维数组A1.N中，若结点Ai有右孩子，则其右孩子是（ C）。C、 A2i+18. 设树 T 的高度为4，其中度为1 、 2、 3、 4 的结点个数分别为 4、 2、 1、 1，则 T 中叶子数为（ D ）D、 89. 有数据 53 ， 30， 37， 12， 45， 24， 96 ，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（ B ）8、 37， 24， 12， 30， 53， 45， 9610. 对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）C、 5， 1， 6， 3， 4， 2

3、11. m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于（B ）8、 m/2-112. 散列文件也称为（ C ）B 、索引文件13. 数据结构是（ D ）D 、相互之间存在一种或多种特定关系的数据元素的集合14. 从逻辑关系来看，数据元素的直接前驱为0 个或 1 个的数据结构只能是（ C ）C、线性结构和树型结构15. 设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用尸llink和p-rlink表示，则同样表示p指针所指向结点的表达式是（D、pfllinkfrlink16. 若栈采用顺序存储方式存储，现两栈共享空间V1.m, topi代表第i个栈（i=1

4、,2）栈顶，栈1的底在v1,栈2的底在Vm,则栈满的条件是（ B ）8、 top1+1=top217. 若一棵二叉树有11 个叶子结点，则该二叉树中度为2 的结点个数是（ A ）A 、 1018. 树的先根序列等同于与该树对应的二叉树的（ A ）A、先序序列19. 下面关于哈希（Hashi,杂凑）查找的说法正确的是（C ）C、不存在特别好与坏的哈希函数，要视情况而定20. 下列序列中， （ D ）是执行第一趟快速排序后所得的序列。D 、 68， 11， 69， 23， 1893， 7321. 下列关键字序列中，构成小根堆的是 （ D ）D、 （15， 28， 46， 37， 84， 58， 6

5、2， 41）22. ISAM 文件和 VASM 文件属于 （ C ）C、索引顺序文件23. 下面程序段的时间复杂度为（ C ）for （i=0; i<m; i+）for （j=0; j<n; j+）Aij=i*j;C、 O（m*n）24. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在 s所指结点之后插入上述链表应执行的语句为（ A ）A 、 q->next=s->next ； s->next=p ；25. 为便于判别有向图中是否存在回路，可借助于（ D ）D 、拓扑排序算法26. 若以 S 和 X 分别表示进

6、栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）D 、 SSSXXSXX27. 设有一顺序栈S,元素s1,s2,s3,s4,s5,S6次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,则栈的容量至少应该是（B ）B、 328. 假设以数组Am存放循环队列的元素。已知队列的长度为length,指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位 置为（ B ） 。8、 （rear-length+m）%m29. 在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（DD 、 rear->next=s;rear=s;30.

7、 对于哈希函数H（key）=key%13,被称为同义词的关键字是（D ）D 、 25 和 5131. 采用二叉链表存储的n 个结点的二叉树，共有空指针（ A ）个。A、 n+132. 连通网的最小生成树是其所有生成树中（ D ）D 、边的权值之和最小的生成树33. 对记录序列（314， 298， 508， 123， 486， 145）依次按个位和十位进行两趟基数排序之后所得结果为（B ）8、 508， 314， 123， 145， 486， 29834. 任何一个无向连通图的最小生成树 （ C ）。C、一棵或多棵35. 无向图的邻接矩阵是一个 （ C ）C、对称矩阵36. 设无向图G-=（V,

8、E）和G' =（V' ,E'）,如G'为G的生成树，则下列说法中不正确的是（B ）。B、G'为G连通分量37. 以 v1 为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）D 、 v1， v2， v5， v6 ， v7 ， v3 ， v438. 下面几个符号串编码集合中，不是前缀编码的是（ B ）B、 0,1,00,1139. 希尔排序的增量序列必须是（ B ） 。B、递减的40. 采用起泡排序法对 n 个关键字进行升序排序，若要使排序过程中比较关键字的次数最多，则初始时的序列应满足条件（D ）D 、关键字从大到小排列41. 在下列内部排序中（

9、 A ） 是不稳定的。A、希尔排序42. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（C ）。A、 （100, 80, 90, 60, 120, 110, 130）43. 在查找过程中，冲突指的是（ CC、不同键值对应相同的存储地址44. 对有14个元素的有序表A1.14作二分查找，查找元素 A4时的被比较元素依次为（DD、A7, A3, A5, A445. 以v1为起始结点对下图进行广度度优先遍历，正确的遍历序列是（ A ）A、 v1, v2, v3, v4, v5, v6, v7二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）1. 数

10、据的物理结构包括数据元素的存储和数据之间关系的存储。2. 若一个算法中的语句频度之和为T（n）=1921n+4nlogn,则算法的时间复杂度为nlogn。3. 下面程序段的时间复杂度是_log 3ni=1 ；while （i<=n） i=i*3 ；4. 循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear,则当前队列的元素个数是 （rear-front+m ） % m5. 主要是使插入和删除等操作统一6. （n-1） /2。7. 在单链表中设置头结点的作用是深度优先。8. 线性表L= （a1,a2； -,an）用数组表示，假定删除表中任一元素的概率相同，则删除

11、一个元素平均需要移动元素的个数是相同值关键字。9. 已知一无向图G= （V, E）,其中V=a；b；c；d；e E=（a；b）；（a；d）；（a；c）；（d；c）；（b；e舰用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd,则采用的是前移遍历方法。10. 如果排序过程不改变时间复杂度之间的相对次序,则称该排序方法是稳定的。11. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需出度一个位置。12. 当问题的规模n趋向无穷大时，算法执行时间 T（n）的数量级被称为算法的10。13. 若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的sxssxxssxs

12、sxxxo14. 一棵含999个结点的完全二叉树的深度为12 。15. 假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序歹U为SSXSXX,则由“a*b+c/d得到J “ ab*cd/+ ”的操作序列为 4。1.1. 如图所示的有向无环图可以排出L->next->next=L17. 边种不同的拓扑序列18. 从空树起，依次插入关键字11, 27, 35, 48, 52, 66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为384 o19. 带头结点的双循环链表L中只有一个元素结点的条件是队列 。20. 求最小生成树的克

13、鲁斯卡尔（Kruskal）算法耗用的时间与图中边稠密、边稀疏的数目正相关。21. 已知一棵完全二叉树中共有 768结点，则该树中共有5 个叶子结点。22. 实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要8、64 存放被访问的结点以实现遍历。23. Prim （普里姆）算法适用于求2h-1的网的最小生成树;kruskal （克鲁斯卡尔）算法适用于求2h-1的网的最小生成树。24. 对长度为20的有序表进行二分查找的判定树的高度为n-1 。25. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为n ,有_个叶子结点。26. 高度为h的完全二叉树中最少有 栈 个结点，最多

14、有 个结点。27. 设连通图G中有n个顶点e条边，则对应的最小生成树上有3条边。28. 构造n个结点的强连通图，至少有O（n2）条弧。29. 表达式求值是（42,13,94,55,05,46,17应用的一个典型例子。30. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6次通过栈S, 一个元素出栈后即进入队列 Q,若6个元素出队的 序列是e2,e4,e3,e6,e5,e 1则栈的容量至少应该是。31. 快速排序算法在最差的情况下其时间复杂度是 。32. 对序列55, 46, 13, 05, 94, 17, 42进行基数排序，第一趟排序后的结果是 。三、应用题（本大题共 5小

15、题，每小题6分，共30分）1. 已知二叉树的先序遍历序列 ABCDEFGH ,中序遍历序列为 CBEDFAGH ,画出二叉树。答案：二叉树形态2.如图请给出邻接表、邻接矩阵及逆邻接表。参考答案如下:(1)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1)vertex firstedge next(2)逆邻接表:(3)& 1 0 1 OLD1 0 0 03 0 103.由字符集s,t, a, e, I及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100请根据该哈夫曼树进行译码，写出原来的电文答案：原来白电文为：ea

16、tst4. 请画出下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历中序遍历为：348675215. 设散列表为HT13,散列函数为H (key) = key %13。用闭散列法解决冲突，对下列关键码序列12, 23, 45, 57, 20, 03,78, 31,15, 36造表。采用线性探查法寻找下一个空位 ，画出相应的散列表，并计算等概率下搜索成功的平均搜索长度。答案:使用散列函数 H(ke» = key mod 13,有H(12) = 12,H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H

17、(31) = 5,H(15) = 2,H(36) = 10.012345678910111278150357452031233612(1)(1)(1)(1)(1)(1)(4)(1)(2)(1)利用线性探查法造表:搜索成功的平均搜索长度为ASLsucc = _1_ (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) =1410106. 已知带权图G如图所示，画出图G的一棵最小生成树。1=1 -7. 假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这9:8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.

18、21,0.10青为这 8个字母设计哈夫曼编码。哈夫曼编码为：a：1001b：01 c:10111 d:1010 e:11 f:10110 g:00h:1000注意：答案不唯一8. 试用权集合12,4,5,6,1,2胸造哈夫曼树，并计算哈夫曼树的带权路径长度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=699. 画出与如图所示森林对应的二叉树答:352033485910.已知一个散列表如下图所示:0123456789101112其散列函数为h(key)=key%13,处理冲突的方法为双重散列法，探查序列为：hi=(h(key)+ i *h1(key)%m i =0,1

19、，m-1其中：h1(key)=key%11+1回答下列问题：(1)对表中关键字35, 20, 33和48进行查找时，所需进行的比较次数各为多少?(2)该散列表在等概率查找时查找成功的平均查找长度为多少?答:(1)对关键字35 20、33和48进行查找的比较次数为3、2、1、1;(2 )平均查找长度 ASL3 2 11295511.请画出与下列二叉树对应的森林。答:12.对于给定结点的关键字集合K=5 ,7, 3, 1, 9, 6, 4, 8, 2, 10, (1)试构造一棵二叉排序树;(2)求等概率情况下的平均查找长度 ASL答:(2) ASL=(1*1+2*2+3*4+4*3)/10=2.9

20、答案：邻接矩阵为：A B C D E FA000100B101000C000111D000000E110100F010010其中顶点A的入度为2,出度为1;其中顶点B的入度为2,出度为2;其中顶点C的入度为1,出度为3;14.已知图5.32如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）答:"占八、最短路径求解过程b6 (a,b)5 (a,c,b)c3 (a,c)d6 (a,c,d)6 (a,c,d)e7 (a,c,e)7 (a,c,e)7 (a,c,e)f9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba,c,da,c,ea,c,d,f15.

21、 阅读下列算法，并回答问题：(1)假设串由合法的英文字母和空格组成，并以0'作结束符。设串s=" ？ ？ I? am? a? ? ? student '?俵示空格符),写出f30 (s)的返回值；(2)简述算法f30的功能。int f30 (char*s)答案：(1) 4(2)算法功能：统计单词的个数。16. 阅读下列函数并回答问题：(1)假设队列q中的元素为(a,b,c,d,e淇中"a"为队头元素。写出执行函数调用Conv(&q)后的队列q；(2)简述算法Conv的功能。答案：(1) e, d, c, b, a(2) 将队列里的值反转17

22、. 阅读下列函数并回答问题：已知整形数组L 1.8中的元素依次为(19, 18, 15, 17, 16, 13, 12, 10),阅读下列函数，并写出执行函数调用sort(L,8)时，对L进行的头两趟(pass分别为0和1)处理结果答案：(1)第一趟(pass = 0) 19 15 18 16 17 12 13 10(2)第二趟(pass = 1) 19 15 16 18 12 17 10 1318. 已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m,散列函数为Hash(key)=key%m=链表的结点结构为：。请在空缺处填入适当

23、内容，使其成为一个完整算keynextvoid f33 (LinkList L, LinkList H , int m)答案： NULL p->next=Hjp=q19. 下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到 La中，其中La和Lb分别为两个链表的头指针。请在空缺处 填入合适内容，使其成为一个完整的算法。答案： pre->next=pb (2) pre->next=pa(3) pre->next=pb20. 阅读算法f30,并回答问题：下列算法为有向

24、图拓扑排序，请在空缺处填入合适的内容，使其成为一个完整的算法。答案：(1) top=-1(2) top=graphj.count(3) graphk.count=021. 阅读算法f31,并回答问题：下列算法功能为在数组 a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a 中各元素的值都不相同。请在空缺处填入合适的内容，使其成为一个完整的算法。答案： (i=k) return;(2) i+1(3) i-122. 阅读算法f33,并回答问题：下列算法功能为奇偶交换排序，思路如下：第一趟对所有奇数的i,将ai和ai+1进行比较，第二趟对所有偶数的i,将a

25、i和ai+1进行比较每次比较时若ai>ai+1,将二者交换；以后重复上述二趟过程，直至整个数组有 序。请在空缺处填入合适的内容，使其成为一个完整的算法。答案：(1)ai=t(i=2;i<=n;i+=2)(3)flag四、算法设计题(本大题共 2小题，每小题10分，共20分)1.已知单链表的结点类型为 Lnode,包含next和data成员。编写算法，实现带头结点单链表的逆置算法。参考答案：void invent(Lnode *head)Lnode *p,*q;if(!head->next) return ERROR;p=head->next; q=p->next;

26、 p->next =NULL;while(q)p=q; q=q->next; p->next=head->next; head->next=p;2. 编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。其中，栈类型为SeqStack可以直接使用InitStack(SeqStack*)Push(SeqStack*,ElemType) Pop(SeqStack*,ElemType*丽数。参考答案：void Inverse(ElemType arr,int n)SeqStack *s;int i;InitStack(&s);for(i=0;i<n;i+

27、) / 数组元素依次入栈Push(s,arri);for(i=0;i<n;i+) / 栈中元素依次出栈，存入数组，是数组逆序Pop(s,&arri);3. 二叉树采用链接存储2构，结点类型为Btree,包才§ left、right和data三个成员，试设计一个算法计算一棵给定二叉树的度为 2 的结点的个数。参考答案：int twochild(Btree *b) int num1,num2;if (b=NULL) return 0;else num1=twochild1(b->left);num2=twochild1(b->right);if ( b->

28、left!=NULL&&b->right!=NULL) return (num1+num2+1);else return (num1+num2);4.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：typedef char DataType;typedef struct node DataType data;struct node *lchild, *rchild; / 左右孩子指针struct node *parent;/ 指向双亲的指针 BinTNode;typedef BinTNode *BinTree;若px为指向非空二叉树中某个结点

29、的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。(1)就后继的不同情况，简要叙述实现求后继操作的方法；参考答案：( 1)分两种情况讨论当 *px 的右子树不为空时，则从*px 的右孩子开始，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，则该结点为 *px 在中序序列中的后继；当 *px 的右孩子为空时， 则沿 *px 的双亲指针链向上查找， 直至找到其左子树中包含 *px 的最年轻祖先， 则该祖先结点为*px 在中序序列中的后继。(2)编写算法求px 所指结点的中序序列后继，并在算法语句中加注注释。( 2) BinTree f34(BinTree px)BinTree

30、q=px->rchild;if(q!=NULL)/ 沿左孩子往下查找px=q;while(px->lchild!=NULL)px=px->lchild;else/ 沿双亲指针链向上查找while(px!=NULL && px->rchild=q)q=px;px=px->parent;return px;/ 返回所找到的中序序列后继结点的指针/ 或者无后继结点时返回空指针5.已有邻接表表示的有向图，请编程判断从第u 顶点至第 v 顶点是否有简单路径，若有则印出该路径上的顶点。参考答案：voidAllSPdfs(AdjList g,vertype u,vertype v) / 求有向图 g 中顶点u 到顶点 v 的所有简单路径，初始调用形式：AllSPdfs(g,u,v)int top=0,s;s+top=u; visitedu=1;while (top>0 | p)p=gstop.firstarc; / 第一个邻接点。while (p!=null &&