完整word版数据结构考试题10

1、所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写要求： 上姓名和学号。 20301.5分）分，一、单项选择题（每小题小题，共计 属非线性结构。 1. 以下数据结构中 平衡二叉树 D. C.队列 A.栈 B.串 。 2. 以下算法的时间复杂度为 void func(int n) int i=0,s=0; while (sprior-next=p-next;p-next-prior=p-prior; B.p-prior=p-prior-prior;p-prior-prior=p; C.p-next-prior=p;p-next=p-next-next; D.p-next=p-p

2、rior-prior;p-prior=p-prior-prior; 4. 设n个元素进栈序列是1、2、3、n，其输出序列是p、p、p，若p=3，11n2则p的值为 。 2 A.一定是2 B.一定是1 C.不可能是1 D.以上都不对 5. 在数据处理过程中常需要保存一些中间数据，如果要实现先保存的数据先处理，则应采用 来保存这些数据。 A.线性表 B.栈 C.队列 D.单链表 6. 中缀表达式a*(b+c)-d的对应的后缀表达式是 。 A.a b c d * + - B.a b c +* d - C.a b c * + d - D.- + * a b c d 7. 设栈s和队列q的初始状态都为空

3、，元素a、b、c、d、e和f依次通过栈s，一个元素出栈后即进入队列q，若6个元素出队的序列是b、d、c、f、e、a，则栈s的容量至少应该存多少个元素？ A.2 B.3 C.4 D.5 8. 设循环队列中数组的下标是0N-1，其队头队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为 。 A.r-f B.r-f-1 C.(r-f)N+1 D.(r-f+N)N 中第A中，B1.n(n+1)/2按列优先顺序压缩存放在一维数组A阶上三角矩阵n若将9. 一个非零元素a存于B数组的b中，则应存放到b中的非零元素a（1jn，1ij）i,j1k1,1的下标i、j与k的对应关系是 。

4、 A. i(i+1)/2+j B. i(i-1)/2+j D. j(j-1)/2+i C. j(j+1)/2+i 10. 一棵节点个数为n高度为h的m（m3）次树中，其分支数是 。 A.nh B.n+m C.n-1 D.h-1 11. 设森林F对应的二叉树为B，B中有m个节点，其根节点的右子树的节点个数为n，森林F中第一棵树的节点个数是 。 A.m-n B.m-n-1 C.n+1 D. 条件不足，无法确定 12. 一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为 。 A.CBEFDA B.FEDCBA C.CBEDFA D.不确定 13. 在一个具有n个顶点

5、的有向图中，构成强连通图时至少有 条边。 A.n B.n+l C.n-1 D.n/2 14. 对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个 。 A.由n-1条权值最小的边构成的子图 B.由n-l条权值之和最小的边构成的子图 C.由n-l条权值之和最小的边构成的连通子图 D.由n个顶点构成的极小连通子图，且边的权值之和最小 15. 对于有n个顶点e条边的有向图，采用邻接矩阵表示，求单源最短路径的Dijkstra算法的时间复杂度为 。 2) C.O(n D.O(ne) A.O(n) B.O(n+e) 16. 一棵高度为h的平衡二叉树，其中每个非叶子节点的平衡因子均为0，则该树的节点个

6、数是 。 h-1h-1h-1h-1 C.2D.2+1 A.2-1 B.2 17. 对线性表进行折半查找时，要求线性表必须 。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且节点按关键字有序排序 D.以链表方式存储，且节点按关键字有序排序 18. 假设有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行 次探测。 A.k-1 B.k C.k+1 D.k(k+1)/2 19. 以下排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是 。 A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 20. 以下排序方法中， 不需要进行关键字的比较。

7、 A.快速排序 B.归并排序 C.基数排序 D.堆排序41040 分）小题，每小题二、问答题（共分，共计1. 已知一棵度为m的树中有n个度为1的节点，n个度为2的节点，n个度为m21m的节点，问该树中有多少个叶子节点？（需要给出推导过程） 2. 设关键字集合D=1，12，5，8，3，10，7，13，9，试完成下列各题： （1）依次取D中各关键字，构造一棵二叉排序树bt； （2）如何依据此二叉树bt得到D的一个关键字递增序列； （3）画出在二叉树bt中删除12后的树结构。 3. 一个有n（n10）个整数的数组R1.n，其中所有元素是有序的，将其看成是一棵完全二叉树，该树构成一个堆吗？若不是，请给

8、一个反例；若是，请简要说明理由。 4. 若要在N个海量数据（超过十亿，不能一次全部放入内存）中找出最大的k个数（内存可以容纳k个数），最好采用什么数据结构和策略？请详细说明你采用的数据结构和策略，并用时间复杂度和空间复杂度来说明理由。 31030 分）三、算法设计题（共分，共计小题，每小题1. 设A=(a，a，a)，B=(b，b，b)是两个递增有序的线性表（其中n、mm1122n均大于1），且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放，设计一个尽可能高效的算法判断B是否为A的一个连续子序列，并分析你设计的算法的时间复杂度和空间复杂度。（10分） 2. 假设二叉树b采用二叉链存储

9、结构存储，试设计一个算法，求该二叉树中从根节点出发的一条最长的路径长度，并输出此路径上各节点的值。（10分） 3. 假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。（10分） ）参考答案“数据结构”考试试题（A所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写要求： 上姓名和学号。 1.530分）分，共计一、单项选择题（每小题5. C 3. A 4. C 1. D 2. B 10. C 8. D 7. B 6. B 9. D 15. C 12. A 13. A 11. A 14. D C 18. D 17. C 16. D 20

10、. 19. C 10303分）分，共计小题，每小题二、问答题（共的节点）的个数，则为叶子节点（即度为0n为总的节点个数，n1. 解：依题意，设0 有： +n+n+n+n=nm120m 2+nn度的总数，即，-1=n1+n又有：n-1=m12-1)n-(m n-2n-两式相减得：1=nm023m? =。+(m-1)n则有：n=1+n+2nn)(i?11?m203i2?i2. 答：（1）本题构造的二叉排序树如图10.20所示。 （2）D的有序序列为b的中序遍历次序，即：1、3、5、7、8、9、10、12、13。 t（3）为了删除节点12，找到其左子树中的最大节点10（其双亲节点为8），将该节点删除

11、并用10代替12，删除后的树结构如图10.21所示。 1 1 10 12 13 5 13 5 8 8 3 3 10 7 9 7 9 图10.20 一棵二叉排序树 图10.21 删除12后的二叉排序树 3. 答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。 以递增有序数组为例，假设数组元素为k、k、k是递增有序的，从中看出下标n12越大的元素值也越大，对于任一元素k，有kk，kk（inext,*q=B-next; while (p!=NULL & q!=NULL) /找两个单链表中第一个值相同的节点 if (p-datadata) p=p-next; else

12、if (p-dataq-data) q=q-next; else break; while (p!=NULL & q!=NULL & p-data=q-data) / 当两者值相等时同步后移p=p-next; q=q-next; 1 中节点比较完毕返回 /if (q=NULL) 当B return 1; else /否则返回0 return 0; 本算法的时间复杂度为O(m+n)，空间复杂度为O(1)。其中m、n分别为A、B单链表的长度。 2.（15分）解：由于二叉树中最长路径一定是从根节点到某个叶子节点的路径，可以求出所有叶子节点到根节点的逆路径，通过比较长度得出最长路径，可以采用多种解法。

13、算法中用形参maxpath数组存放最长路径，maxpathlen存放最长路径长度。 对应的算法如下：1解法void MaxPath(BTNode *b,ElemType maxpath,int &maxpathlen) /maxpathlen的初值为0 struct snode BTNode *node; /存放当前节点指针 int parent; /存放双亲节点在队列中的位置 QuMaxSize; /定义非循环队列 ElemType pathMaxSize; /存放一条路径 int pathlen; /存放一条路径长度 int front,rear,p,i; /定义队头和队尾指针 front

14、=rear=-1; /置队列为空队列 rear+; Qurear.node=b; /根节点指针进进队 Qurear.parent=-1; /根节点没有双亲节点 while (frontlchild=NULL & b-rchild=NULL) /*b为叶子节点 p=front; pathlen=0; while (Qup.parent!=-1) pathpathlen=Qup.node-data; pathlen+; p=Qup.parent; pathpathlen=Qup.node-data; pathlen+; if (pathlenmaxpathlen) /通过比较求最长路径 for (

15、i=0;ilchild!=NULL) /左孩子节点进队 rear+; Qurear.node=b-lchild; Qurear.parent=front; if (b-rchild!=NULL) /右孩子节点进队 rear+; Qurear.node=b-rchild; Qurear.parent=front; 本算法的时间复杂度为O(n)，空间复杂度为O(n)。 对应的算法如下：2解法void MaxPath1(BTNode *b,ElemType path,int pathlen, ElemType maxpath,int &maxpathlen) /pathlen和maxpathlen的

16、初值均为0 int i; if (b=NULL) if (pathlenmaxpathlen) /通过比较求最长路径 for (i=pathlen-1;i=0;i-) maxpathi=pathi; maxpathlen=pathlen; else pathpathlen=b-data; /将当前节点放入路径中 pathlen+; /路径长度增1 MaxPath1(b-lchild,path,pathlen,maxpath,maxpathlen); /递归扫描左子树 MaxPath1(b-rchild,path,pathlen,maxpath,maxpathlen); /递归扫描右子树 本算法

17、的时间复杂度为O(n)，空间复杂度为O(n)。 解法3：对应的算法如下： void MaxPath2(BTNode *b,ElemType maxpath,int &maxpathlen) /maxpathlen的初值为0 BTNode *StMaxSize; BTNode *p; ElemType pathMaxSize; /存放一条路径 int pathlen; /存放一条路径长度 int i,flag,top=-1; /栈顶指针置初值 if (b!=NULL) do while (b!=NULL) /将*b的所有左节点进栈 top+; Sttop=b; b=b-lchild; p=NUL

18、L; /p指向栈顶节点的前一个已访问的节点 flag=1; /设置b的访问标记为已访问过 while (top!=-1 & flag) b=Sttop; /取出当前的栈顶元素 if (b-rchild=p) /右孩子不存在或右孩子已被访问,访问之 if (b-lchild=NULL & b-rchild=NULL) /*b为叶子节点 pathlen=0; for (i=top;i=0;i-) pathpathlen=Sti-data; pathlen+; if (pathlenmaxpathlen) /通过比较求最长路径 for (i=0;irchild; /b指向右孩子节点 flag=0; /设置未被访问的标记 while (top!=-1); printf(); 3. （10分）解：采用深度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下： int visitedMAXV=0; DFSGraph(AG