数据结构考试题2

1、要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题1.5分，20小题，共计30分）1. 以下数据结构中 属非线性结构。A.栈B.串C.队列D.平衡二叉树2. 以下算法的时间复杂度为 。void func(int n)int i=0,s=0;while (s<=n)i+;s=s+i;A. O(n)B. O()C. O(nlog2n)D. O(log2n)3. 在一个双链表中，删除p所指节点（非首、尾节点）的操作是 。A.p->prior->next=p->next;p->next->prior=p-&

2、gt;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->prior->prior;p->prior=p->prior->prior;4. 设n个元素进栈序列是1、2、3、n，其输出序列是p1、p2、pn，若p1=3，则p2的值为 。A.一定是2B.一定是1C.不可能是1D.以上都不对5. 在数据处理过程中常需要保存一些中间数据，如果要实现后保

3、存的数据先处理，则应采用 来保存这些数据。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 d7. 设栈s和队列q的初始状态都为空，元素a、b、c、d、e和f依次通过栈s，一个元素出栈后即进入队列q，若6个元素出队的序列是b、d、c、f、e、a，则栈s的容量至少应该存多少个元素？A.2B.3C.4D.58. 设循环队列中数组的下标是0N-1，其队头队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为 。A.r-

4、fB.r-f-1C.(r-f)N+1D.(r-f+N)N9. 若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B1.n(n+1)/2中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素ai,j（1in，1ji）的下标i、j与k的对应关系是 。A. B. C. D. 10. 一棵节点个数为n的m（m3）次树中，其分支数是 。A.nhB.n+hC.n-1D.h-111. 设森林F对应的二叉树为B，B中有m个节点，其根节点的右子树的节点个数为n，森林F中第一棵树的节点个数是 。A.m-nB.m-n-1C.n+1D. 条件不足，无法确定12. 一棵二叉树的先序遍历序列为ABC

5、DEF，中序遍历序列为CBAEDF，则后序遍历序列为 。A.CBEFDAB.FEDCBAC.CBEDFAD.不确定13. 在一个具有n个顶点的有向图中，构成强连通图时至少有 条边。A.nB.n+lC.n-1D.n/214. 对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个 。A.由n-1条权值最小的边构成的子图B.由n-l条权值之和最小的边构成的子图C.由n-l条权值之和最小的边构成的连通子图D.由n个顶点构成的极小连通子图，且边的权值之和最小15. 对于有n个顶点e条边的有向图，求单源最短路径的Dijkstra算法的时间复杂度为 。A.O(n)B.O(n+e)C.O(n2)D.O(

6、ne)16. 一棵深度为k的平衡二叉树，其每个非叶子节点的平衡因子均为0，则该树共有 个节点。A.2k-1-1B.2k-1C.2k-1+1D.2k-117. 对线性表进行折半查找时，要求线性表必须 。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且节点按关键字有序排序D.以链表方式存储，且节点按关键字有序排序18. 假设有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行 次探测。A.k-1B.kC.k+1D.k(k+1)/219. 以下排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是 。A.堆排序B.冒泡排序C.直接插入排序D.快速排序20

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

8、，请说明理由。三、算法设计题（共计40分）1. 设A=(a1,a2,an)，B=(b1,b2,bm)是两个递增有序的线性表（其中n、m均大于1），且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放，设计一个尽可能高效的算法判断B是否为A的一个子序列，并分析你设计的算法的时间复杂度和空间复杂度。（15分）2. 假设二叉树b采用二叉链存储结构存储，试设计一个算法，输出该二叉树中从根节点出发的第一条最长的路径长度，并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。（15分）3. 假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序

9、列。（10分）四、附加题（10分）说明：附加题不计入本次期未考试总分，但计入本课程的总分。假设一个图G采用邻接表作为存储结构，设计一个算法，判断该图中是否存在回路。“数据结构”考试试题（A）参考答案要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题1.5分，共计30分）1. D2. B3. A4. C5. B6. B7. B8. D9. D10. C11. A12. A13. A14. D15. C16. D17. C18. D19. C20. C二、问答题（共3小题，每小题10分，共计30分）1. 解：依题意，设n为总的节点个数，n

10、0为叶子节点（即度为0的节点）的个数，则有：n=n0+n1+n2+nm又有：n-1=度的总数，即，n-1=n1×1+n2×2+nm×m两式相减得：1=n0-n2-2n3-(m-1)nm则有：n0=1+n2+2n3+(m-1)nm=。2. 答：（1）本题构造的二叉排序树如图10.20所示。（2）D的有序序列为bt的中序遍历次序，即：1、3、5、7、8、9、10、12、13。（3）为了删除节点12，找到其左子树中的最大节点10（其双亲节点为8），将该节点删除并用10代替12，删除后的树结构如图10.21所示。图10.20 一棵二叉排序树 图10.21 删除12后的二叉

11、排序树3. 答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为k1、k2、kn是递增有序的，从中看出下标越大的元素值也越大，对于任一元素ki，有ki<k2i，ki<k2i+1（i<n/2），这正好满足小根堆的特性，所以构成一个小根堆。3. 有一棵二叉排序树按先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20)。回答以下问题：（1）画出该二叉排序树。（2）给出该二叉排序树的中序遍历序列。（3）求在等概率下的查找成功和不成功情况下的平均查找长度。三、算法设计题（共计40分）1.（15分）解：

12、采用二路归并思路，用p、q分别扫描有序单链表A、B，先找到第一个两者值相等的节点，然后在两者值相等时同步后移，如果B扫描完毕返回1，否则返回0。对应的算法如下：int SubSeq(LinkList *A,LinkList *B)LinkList *p=A->next,*q=B->next;while (p!=NULL && q!=NULL)/找两个单链表中第一个值相同的节点if (p->data<q->data)p=p->next;else if (p->data>q->data)q=q->next;elsebrea

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

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

15、ar.node=b;/根节点指针进进队Qurear.parent=-1;/根节点没有双亲节点while (front<rear)/队列不为空front+;b=Qufront.node;/队头出队列if (b->lchild=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 (pathl

16、en>maxpathlen)/通过比较求最长路径for (i=0;i<pathlen;i+)maxpathi=pathi;maxpathlen=pathlen;if (b->lchild!=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 MaxPath

17、1(BTNode *b,ElemType path,int pathlen,ElemType maxpath,int &maxpathlen)/pathlen和maxpathlen的初值均为0int i;if (b=NULL)if (pathlen>maxpathlen)/通过比较求最长路径for (i=pathlen-1;i>=0;i-)maxpathi=pathi;maxpathlen=pathlen;elsepathpathlen=b->data;/将当前节点放入路径中pathlen+;/路径长度增1MaxPath1(b->lchild,path,path

18、len,maxpath,maxpathlen);/递归扫描左子树MaxPath1(b->rchild,path,pathlen,maxpath,maxpathlen);/递归扫描右子树本算法的时间复杂度为O(n)，空间复杂度为O(n)。解法3：对应的算法如下：void MaxPath2(BTNode *b,ElemType maxpath,int &maxpathlen)/maxpathlen的初值为0BTNode *StMaxSize;BTNode *p;ElemType pathMaxSize;/存放一条路径int pathlen;/存放一条路径长度int i,flag,to

19、p=-1;/栈顶指针置初值if (b!=NULL)dowhile (b!=NULL)/将*b的所有左节点进栈top+;Sttop=b;b=b->lchild;p=NULL;/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>

20、;=0;i-)pathpathlen=Sti->data;pathlen+;if (pathlen>maxpathlen)/通过比较求最长路径for (i=0;i<pathlen;i+)maxpathi=pathi;maxpathlen=pathlen;top-;p=b;/p指向刚才访问的节点elseb=b->rchild;/b指向右孩子节点flag=0;/设置未被访问的标记 while (top!=-1);printf("n");本算法的时间复杂度为O(n)，空间复杂度为O(n)。3. （10分）解：采用深度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：int visitedMAXV=0;DFSGraph(AGraph *G)int i,j=1;/用j记录连通分量的序号for (i=0;i<G->n;i+)if (visitedi=0)printf("第%d个连通分量节点序列:",j+);DFS(G,i);/调用前面的深度优先遍历算法采用广度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：int visitedMAXV=0;BFSGrap