数据结构考试题2.doc

《数据结构考试题2.doc》由会员分享，可在线阅读，更多相关《数据结构考试题2.doc（9页珍藏版）》请在三一文库上搜索。

1、要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题1.5分，20小题，共计30分）1. 以下数据结构中 属非线性结构。A.栈B.串C.队列D.平衡二叉树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-prior-prior;p-pr

2、ior=p-prior-prior;4. 设n个元素进栈序列是1、2、3、n，其输出序列是p1、p2、pn，若p1=3，则p2的值为 。A.一定是2B.一定是1C.不可能是1D.以上都不对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 d7. 设栈s和队列q的初始状态都为空，元素a、b、c、d、e和f依次通过栈s，一个元素出栈后即进入队

3、列q，若6个元素出队的序列是b、d、c、f、e、a，则栈s的容量至少应该存多少个元素？A.2B.3C.4D.58. 设循环队列中数组的下标是0N-1，其队头队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为 。A.r-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

4、.nhB.n+hC.n-1D.h-111. 设森林F对应的二叉树为B，B中有m个节点，其根节点的右子树的节点个数为n，森林F中第一棵树的节点个数是 。A.m-nB.m-n-1C.n+1D. 条件不足，无法确定12. 一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为 。A.CBEFDAB.FEDCBAC.CBEDFAD.不确定13. 在一个具有n个顶点的有向图中，构成强连通图时至少有 条边。A.nB.n+lC.n-1D.n/214. 对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个 。A.由n-1条权值最小的边构成的子图B.由n-l条权值之和最小的边

5、构成的子图C.由n-l条权值之和最小的边构成的连通子图D.由n个顶点构成的极小连通子图，且边的权值之和最小15. 对于有n个顶点e条边的有向图，求单源最短路径的Dijkstra算法的时间复杂度为 。A.O(n)B.O(n+e)C.O(n2)D.O(ne)16. 一棵深度为k的平衡二叉树，其每个非叶子节点的平衡因子均为0，则该树共有 个节点。A.2k-1-1B.2k-1C.2k-1+1D.2k-117. 对线性表进行折半查找时，要求线性表必须 。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且节点按关键字有序排序D.以链表方式存储，且节点按关键字有序排序18. 假设有k个关键字互为同义

6、词，若用线性探测法把这k个关键字存入哈希表中，至少要进行 次探测。A.k-1B.kC.k+1D.k(k+1)/219. 以下排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是 。A.堆排序B.冒泡排序C.直接插入排序D.快速排序20. 以下排序方法中， 不需要进行关键字的比较。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中各数

7、据，构造一棵二叉排序树bt；（2）如何依据此二叉树bt得到D的一个有序序列；（3）画出在二叉树bt中删除12后的树结构。3. 一个有n个整数的数组R1.n，其中所有元素是有序的，将其看成是一棵完全二叉树，该树构成一个堆吗？若不是，请给一个反例，若是，请说明理由。三、算法设计题（共计40分）1. 设A=(a1,a2,an)，B=(b1,b2,bm)是两个递增有序的线性表（其中n、m均大于1），且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放，设计一个尽可能高效的算法判断B是否为A的一个子序列，并分析你设计的算法的时间复杂度和空间复杂度。（15分）2. 假设二叉树b采用二叉链存储结构存

8、储，试设计一个算法，输出该二叉树中从根节点出发的第一条最长的路径长度，并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。（15分）3. 假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。（10分）四、附加题（10分）说明：附加题不计入本次期未考试总分，但计入本课程的总分。假设一个图G采用邻接表作为存储结构，设计一个算法，判断该图中是否存在回路。“数据结构”考试试题（A）参考答案要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题1.5分，共计30分）1. D2. B3.

9、A4. C5. B6. B7. B8. D9. D10. C11. A12. A13. A14. D15. C16. D17. C18. D19. C20. C二、问答题（共3小题，每小题10分，共计30分）1. 解：依题意，设n为总的节点个数，n0为叶子节点（即度为0的节点）的个数，则有：n=n0+n1+n2+nm又有：n-1=度的总数，即，n-1=n11+n22+nmm两式相减得：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、1

10、0、12、13。（3）为了删除节点12，找到其左子树中的最大节点10（其双亲节点为8），将该节点删除并用10代替12，删除后的树结构如图10.21所示。图10.20 一棵二叉排序树 图10.21 删除12后的二叉排序树3. 答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为k1、k2、kn是递增有序的，从中看出下标越大的元素值也越大，对于任一元素ki，有kik2i，kik2i+1（inext,*q=B-next;while (p!=NULL & q!=NULL)/找两个单链表中第一个值相同的节点if (p-datadata)p=

11、p-next;else if (p-dataq-data)q=q-next;elsebreak;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分）解：由于二叉树中最长路径一定是从根节点到某个叶子节点的路径，可以求出所有叶子节点到根节点的逆路径，通过比较长度得出最长路径，可以采用多种解法。算法中用形

12、参maxpath数组存放最长路径，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;/置队列为空队列re

13、ar+;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 (i=0;ilchild!=NULL)/左孩子节点进队rear+;Qurear

14、.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的初值均为0int i;if (b=NULL)if (pathlenmaxpathlen)/通过比较求

15、最长路径for (i=pathlen-1;i=0;i-)maxpathi=pathi;maxpathlen=pathlen;elsepathpathlen=b-data;/将当前节点放入路径中pathlen+;/路径长度增1MaxPath1(b-lchild,path,pathlen,maxpath,maxpathlen);/递归扫描左子树MaxPath1(b-rchild,path,pathlen,maxpath,maxpathlen);/递归扫描右子树本算法的时间复杂度为O(n)，空间复杂度为O(n)。解法3：对应的算法如下：void MaxPath2(BTNode *b,ElemType

16、 maxpath,int &maxpathlen)/maxpathlen的初值为0BTNode *StMaxSize;BTNode *p;ElemType pathMaxSize;/存放一条路径int pathlen;/存放一条路径长度int i,flag,top=-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

17、-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(n);本算法的时间复杂度为O(n)，空间复杂度为O(n)。3. （10分）解：采用深度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下

18、：int visitedMAXV=0;DFSGraph(AGraph *G)int i,j=1;/用j记录连通分量的序号for (i=0;in;i+)if (visitedi=0)printf(第%d个连通分量节点序列:,j+);DFS(G,i);/调用前面的深度优先遍历算法采用广度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：int visitedMAXV=0;BFSGraph(AGraph *G)int i,j=1;/用j记录连通分量的序号for (i=0;in;i+)if (visitedi=0)printf(第%d个连通分量节点序列:,j+);BFS(G,i);/调用前面的

19、广度优先遍历算法四、附加题（10分）说明：附加题不计入本次期未考试总分，但计入本课程的总分。假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在回路。解：采用深度优先遍历方法，从顶点v出发，对每个访问的顶点w做标记（visitedw=1）。若顶点w（先访问）和i（后访问）均已访问过，表示从顶点w到顶点i存在一条路径。当从顶点i出发遍历，发现顶点i到顶点w有一条边时，表示存在一个回路（该回路上包含顶点w和i）。算法Cycle(G,v,has)从顶点v出发判断图G中是否存在回路，has是布尔值，初始调用时置为false，执行后若为true表示有回路，否则表示图G中没有回路。对应的算法如下：void Cycle(AGraph *G,int v,bool &has)/调用时has置初值falseArcNode *p;int w;visitedv=1;/置已访问标记p=G-adjlistv.firstarc;/p指向顶点v的第一个邻接点while (p!=NULL)w= p-adjvex;if (visitedi=0)/若顶点w未访问,递归访问它Cycle(G,w,has);else/又找到了已访问过的顶点说明有回路has=true;p=p-nextarc;/找下一个邻接点