《数据结构考试题2（2020年整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构考试题2（2020年整理）.pdf（9页珍藏版）》请在金锄头文库上搜索。
1、 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-n
2、ext=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 d
3、 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 中第 2 一个非零元素 a
4、1,1存于 B 数组的 b1中，则应存放到 bk中的非零元素 ai,j（1in，1ji） 的下标 i、j 与 k 的对应关系是 。 A. j ii + + 2 ) 1( B. j ii + 2 ) 1( C. i jj + + 2 ) 1( D. i jj + 2 ) 1( 10. 一棵节点个数为 n 的 m（m3）次树中，其分支数是 。 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. 条件不足，无法确定 12.
5、 一棵二叉树的先序遍历序列为 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-1 C.2k-1+1 D.2k-1 17. 对线性表进行折半查找时，要求线性表必须 。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且节点按关键字有序排序 D.以链表方式存储，且节点按关键字有序排序 18. 假设有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入哈希表中， 至少要进行 次探测。 A.k-1 B.k C.k
7、+1 D.k(k+1)/2 3 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，试完成下列各题： （1）依次取 D 中各数据，构造一棵二叉
8、排序树 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 采用邻接表作为存储结构，设计一个算法，判断该图中是否存在回路。 4 “数据结构”考试试题（A）参考答案 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。
10、每张答题纸都要写 上姓名和学号。 一、单项选择题（每小题 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=度的总数，即，n-1=n1 1+n2 2+nm m 两式相减得：1=n0-n2-2n3-(
11、m-1)nm 则有：n0=1+n2+2n3+(m-1)nm= = + m i i ni 2 ) 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.21 删除 12 后的二叉排序树 3. 答：该数组一定构成一
12、个堆，递增有序数组构成一个小根堆，递减有序数组构成一 个大根堆。 以递增有序数组为例，假设数组元素为 k1、k2、kn是递增有序的，从中看出下标 越大的元素值也越大，对于任一元素 ki，有 kik2i，kik2i+1（inext,*q=B-next; while (p!=NULL else if (p-dataq-data) q=q-next; else break; while (p!=NULL q=q-next; if (q=NULL) /当 B 中节点比较完毕返回 1 return 1; else /否则返回 0 return 0; 本算法的时间复杂度为 O(m+n)，空间复杂度为 O(
13、1)。其中 m、n 分别为 A、B 单链表 的长度。 2.（15 分）解：由于二叉树中最长路径一定是从根节点到某个叶子节点的路径，可以 求出所有叶子节点到根节点的逆路径，通过比较长度得出最长路径，可以采用多种解法。 算法中用形参 maxpath数组存放最长路径，maxpathlen 存放最长路径长度。 解法 1：对应的算法如下： void MaxPath(BTNode *b,ElemType maxpath,int /存放当前节点指针 int parent; /存放双亲节点在队列中的位置 QuMaxSize; /定义非循环队列 6 ElemType pathMaxSize; /存放一条路径 i
14、nt pathlen; /存放一条路径长度 int front,rear,p,i; /定义队头和队尾指针 front=rear=-1; /置队列为空队列 rear+; Qurear.node=b; /根节点指针进进队 Qurear.parent=-1; /根节点没有双亲节点 while (frontlchild=NULL pathlen=0; while (Qup.parent!=-1) pathpathlen=Qup.node-data; pathlen+; p=Qup.parent; pathpathlen=Qup.node-data; pathlen+; if (pathlenmaxpa
15、thlen) /通过比较求最长路径 for (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 if (b=NULL) 7 if (pathlenmaxpathlen) /通过比较求最长路径 for (i=pathlen-1;i=0;i-) maxpathi=pathi; maxpathlen=pathlen; else pathpathlen=b-data; /将当前节点放入
