2022年数据结构考试题2 .pdf

《2022年数据结构考试题2 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构考试题2 .pdf（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;

2、 D.p- next=p- prior - prior;p - prior=p - prior - prior; 4. 设 n 个元素进栈序列是1、2、3、n，其输出序列是p1、p2、 、pn，若 p1=3，则 p2的值为。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

3、d 7. 设栈 s 和队列 q 的初始状态都为空，元素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 9. 若将 n 阶上三角矩阵A 按列优先顺序压缩存放在一维数组B1.n(n+1)/2 中， A 中第精选学习资料 - - - -

4、- - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页一个非零元素a1,1存于 B 数组的 b1中，则应存放到bk中的非零元素ai,j（ 1in，1j i）的下标 i、j 与 k 的对应关系是。A. jii2)1(B. jii2) 1(C. ijj2)1(D. ijj2)1(10. 一棵节点个数为n 的 m（ m 3）次树中，其分支数是。A.nh B.n+h C.n- 1 D.h-1 11. 设森林 F 对应的二叉树为B， B 中有 m 个节点，其根节点的右子树的节点个数为n，森林 F 中第一棵树的节点个数是。A.m -n B.m- n- 1 C.n+1 D. 条件

5、不足，无法确定12. 一棵二叉树的先序遍历序列为ABCDEF ，中序遍历序列为CBAEDF ，则后序遍历序列为。A.CBEFDA B.FEDCBA C.CBEDFA D.不确定13. 在一个具有n 个顶点的有向图中，构成强连通图时至少有条边。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 条边的有向图，求单

6、源最短路径的Dijkstra 算法的时间复杂度为。A.O(n) B.O(n+e) C.O(n2) D.O(ne) 16. 一棵深度为k 的平衡二叉树，其每个非叶子节点的平衡因子均为0，则该树共有个节点。A.2k-1- 1 B.2k-1C.2k-1+1 D.2k- 1 17. 对线性表进行折半查找时，要求线性表必须。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且节点按关键字有序排序D.以链表方式存储，且节点按关键字有序排序18. 假设有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行次探测。A.k- 1 B.k C.k+1 D.k(k+1)/2 精选学习

7、资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页19. 以下排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是。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 ，试完成下列各题

8、：（1）依次取 D 中各数据，构造一棵二叉排序树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 的一个子序列， 并分析你设计的算法的

9、时间复杂度和空间复杂度。（15 分）2. 假设二叉树b 采用二叉链存储结构存储，试设计一个算法，输出该二叉树中从根节点出发的第一条最长的路径长度，并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。（15 分）3. 假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。（10 分）四、附加题（ 10 分）说明： 附加题不计入本次期未考试总分，但计入本课程的总分。假设一个图G 采用邻接表作为存储结构，设计一个算法，判断该图中是否存在回路。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页

10、，共 9 页“数据结构”考试试题（A）参考答案要求： 所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题1.5 分，共计 30 分）1. D 2. B 3. A 4. C 5. B 6. B 7. B 8. D 9. D 10. C 11. A 12. A 13. A 14. D 15. C 16. D 17. C 18. D 19. C 20. C 二、问答题（共 3 小题，每小题 10 分，共计 30 分）1. 解： 依题意，设n为总的节点个数，n0为叶子节点（即度为0 的节点）的个数，则有：n=n0+n1+n2+nm又有： n- 1=

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

12、.21 删除 12 后的二叉排序树3. 答： 该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。以递增有序数组为例，假设数组元素为k1、k2、kn是递增有序的，从中看出下标越大的元素值也越大，对于任一元素ki，有 kik2i，kik2i+1（ inext,*q=B-next; while (p!=NULL & q!=NULL) / 找两个单链表中第一个值相同的节点 if (p-datadata) p=p-next; else if (p-dataq-data) q=q-next; else break; while (p!=NULL & q!=NULL & p-da

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

14、xPath(BTNode *b,ElemType maxpath,int &maxpathlen) /maxpathlen的初值为 0 struct snode BTNode *node; / 存放当前节点指针int parent; / 存放双亲节点在队列中的位置 QuMaxSize; / 定义非循环队列精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页ElemType pathMaxSize; / 存放一条路径int pathlen; / 存放一条路径长度int front,rear,p,i; / 定义队头和队尾指针front=r

15、ear=-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 (i=

16、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的初

17、值均为 0 int i; if (b=NULL) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页 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); / 递归扫描左子树MaxP

18、ath1(b-rchild,path,pathlen,maxpath,maxpathlen); / 递归扫描右子树 本算法的时间复杂度为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 whi

19、le (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=0;i-) pathpathlen=Sti-data; pathlen+; if (pathlenm

20、axpathlen) / 通过比较求最长路径 for (i=0;irchild; /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;in;i+) if (visitedi=0) printf(第%d个连通分量节点序列:,j+); DFS(G,i); /

21、 调用前面的深度优先遍历算法 采用广度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：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); / 调用前面的广度优先遍历算法 四、附加题（ 10 分）说明： 附加题不计入本次期未考试总分，但计入本课程的总分。假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在回路。解： 采用深度优先遍历方法，从顶点 v 出发， 对

22、每个访问的顶点w 做标记 （visitedw=1 ） 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页若顶点 w（先访问）和i（后访问）均已访问过，表示从顶点w 到顶点 i 存在一条路径。当从顶点 i 出发遍历，发现顶点i 到顶点 w 有一条边时，表示存在一个回路（该回路上包含顶点 w 和 i） 。算法 Cycle(G,v,has)从顶点 v 出发判断图G 中是否存在回路，has是布尔值，初始调用时置为false，执行后若为true 表示有回路，否则表示图G 中没有回路。对应的算法如下：void Cycle(AGraph *G,

23、int v,bool &has) / 调用时 has 置初值 false ArcNode *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; /找下一个邻接点 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页