2022年2022年数据结构考试题8

1、精选学习资料 - - - 欢迎下载要求： 全部的题目的解答均写在答题纸上,需写清晰题目的序号；每张答题纸都要写上姓名和学号；一.单项挑选题（挑选最精确的一项,共15 小题,每道题2 分,共计 30 分）1. 数据结构为指；a. 一种数据类型b. 数据的储备结构c. 一组性质相同的数据元素的集合d. 相互之间存在一种或多种特定关系的数据元素的集合2. 以下算法的时间复杂度为；void funint nint i=1、s=0; while i<=ns+=i+100; i+;a. onb. on c. onlog 2nd. olog 2n3. 在一个长度为n 的有序次序表中删除其中第一个元素值

2、为x 的元素时,在查找元素x 时采纳二分查找方法,此时删除算法的时间复杂度为；a. onb. onlog 2n2c. on d. on 4. 如一个栈采纳数组s0.n- 1 存放其元素,初始时栈顶指针为n,就以下元素x 进栈的正确操作为；a.top+;stop= x;b.stop= x;top+;c.top- ;stop= x;b.stop= x;top- ;5. 设环形队列中数组的下标为0 n - 1,其队头.队尾指针分别为front 和 rear（ front指向队列中队头元素的前一个位置,rear 指向队尾元素的位置）,就其元素个数为；a. rear - frontb. rear - f

3、ront - 1c. rear- front n+1d. rear - front+n n6. 如用一个大小为6 的数组来实现环形队列,队头指针front 指向队列中队头元素的 前一个位置,队尾指针rear 指向队尾元素的位置；如当前rear 和 front 的值分别为0 和 3,当从队列中删除一个元素,再加入两个元素后,rear 和 front 的值分别为；a. 1 和 5b. 2 和 4c. 4 和 2d. 5 和 1精品学习资料精选学习资料 - - - 欢迎下载7. 一棵高度为h（ h 1）的完全二叉树至少有个结点；a. 2 h-1b. 2hc. 2h+1d. 2 h-1+18. 设一棵

4、哈夫曼树中有999 个结点,该哈夫曼树用于对个字符进行编码；a. 999c. 500b. 499d. 5019. 一个含有n 个顶点的无向连通图采纳邻接矩阵储备,就该矩阵肯定为；a.c.对称矩阵稀疏矩阵b.d.非对称矩阵稠密矩阵10. 设无向连通图有a. e nc. e=n- 1n 个顶点e 条边,如满意b. e<n- 1d. 2 e n,就图中肯定有回路；11. 假如从无向图的任一顶点动身进行一次广度优先遍历即可拜访全部顶点,就该图肯定为；a. 完全图b.连通图c.有回路d. 一棵树12. 设有 100 个元素的有序表, 用折半查找时, 不胜利查找时最大的比较次数为；a. 25b. 5

5、0c. 10d. 713. 从 100 个元素确定的次序表中查找其中某个元素（关键字为正整数）,假如最多只进行 5 次元素之间的比较,就采纳的查找方法只可能为；a. 折半查找b.次序查找c.哈希查找d. 二叉排序树查找14. 有一个含有n（ n>1000）个元素数据序列,某人采纳了一种排序方法对其按关键字递增排序,该排序方法需要关键字比较,其平均时间复杂度接近最好的情形,空间复杂度为 o1 ,该排序方法可能为；a. 快速排序c.二路归并排序b.堆排序d. 都不适合15. 对一个线性序列进行排序,该序列采纳单链表储备,最好采纳排序方法；a. 直接插入排序b.希尔排序精品学习资料精选学习资料

6、 - - - 欢迎下载c.快速排序d. 都不适合二.问答题（共3 小题,每道题10 分,共计 30 分）1. 假如对含有n（ n>1 ）个元素的线性表的运算只有4 种：删除第一个元素；删除最终一个元素；在第一个元素前面插入新元素；在最终一个元素的后面插入新元素,就最好使用以下哪种储备结构,并简要说明理由；（ 1）只有尾结点指针没有头结点指针的循环单链表（ 2）只有尾结点指针没有头结点指针的非循环双链表（ 3）只有头结点指针没有尾结点指针的循环双链表（ 4）既有头结点指针也有尾结点指针的循环单链表2. 对于一个带权连通无向图g,可以采纳prim 算法构造出从某个顶点v 动身的最小生成树,问

7、该最小生成树为否肯定包含从顶点v 到其他全部顶点的最短路径；假如回答为, 请予以证明；假如回答不为,请给出反例；3. 有一棵二叉排序树按先序遍历得到的序列为：12、5、2、8、6、10、16、15、18、20 ；回答以下问题：（ 1）画出该二叉排序树；（ 2）给出该二叉排序树的中序遍历序列；（ 3）求在等概率下的查找胜利和不胜利情形下的平均查找长度；三.算法设计题（共3 小题,共计40 分）1.（ 15 分）假设二叉树b 采纳二叉链储备结构,设计一个算法void findparentbtnode*b、elemtypex、btnode*&p 求指定值为x 的结点的双亲结点p；提示,根结点

8、的双亲为 null ,如在二叉树b 中未找到值为x 的结点, p 亦为 null ；2. （ 10 分）假设一个有向图g 采纳邻接表储备；设计一个算法判定顶点i 和 顶点j（ ij ）之间为否相互连通,假设这两个顶点均存在；3.（ 15 分）有一个含有n 个整数的无序数据序列,全部的数据元素均不相同,采纳整数数组 r0.n- 1 储备,请完成以下任务：（ 1）设计一个尽可能高效的算法,输出该序列中第k（ 1k n）小的元素,算法中给出适当的注释信息；提示：利用快速排序的思路；（ 2）分析你所设计的求解算法的平均时间复杂度,并给出求解过程；精品学习资料精选学习资料 - - - 欢迎下载“数据结构

9、”考试试题（a ）参考答案要求： 全部的题目的解答均写在答题纸上,需写清晰题目的序号；每张答题纸都要写上姓名和学号；一.单项挑选题（共15 小题,每道题2 分,共计 30 分）1.d2.b3.a4. c5. d6. b7. a8. c9. a10. a11. b12. d13.c14.b15.a二.问答题（共3 小题,每道题10 分,共计 30 分）1. 答：此题答案为（3）,由于实现上述4 种运算的时间复杂度均为o1 ；2. 答：不为；如图1 所示的图g 从顶点0 动身的最小生成树如图2 所示,而从顶点0到顶点的2 的最短路径为02,而不为最小生成树中的012；00686441212图 1

10、一个带权连通无向图g图 2 图 g 的一棵最小生成树3. 答：（ 1）先序遍历得到的序列为：12、5、2、8、6、10、16、15、18、20 ,中序序列为一个有序序列,所以为：2、5、6、8、10、12、15、16、18、20 ,由先序序列和中序序列可以构造出对应的二叉 树,如图3 所示； 4 分（ 2）中序遍历序列为：2、5、6、8、10、12、15、16、18、20 ；4 分（ 3）asl 成 功 =1 ×1+2×2+4×3+3×4/10=29/10 ； 1 分asl 不胜利 =5 ×3+6 ×4/11=39/11 ；1 分12

11、精品学习资料精选学习资料 - - - 欢迎下载52861016151820精品学习资料精选学习资料 - - - 欢迎下载图 3三.算法设计题（共3 小题,共计40 分）1.（ 15 分）解：算法如下：void findparentbtnode *b、elemtype x、btnode *&pif b.=null精品学习资料精选学习资料 - - - 欢迎下载if b->data=x p=null;else if b->lchild.=null && b->lchild->data=x p=b;else if b->rchild.=null &

12、amp;& b->rchild->data=xp=b;elsefindparentb->lchild、x、p; if p=nullfindparentb->rchild、x、p;else p=null;2. （ 10 分）解：算法如下：int visitedmaxv;void dfsalgraph *g、int v/ 深度优先遍历算法arcnode *p;visitedv=1;/ 置已拜访标记p=g->adjlistv.firstarc;/p指向顶点 v 的第一个邻接点 while p.=nullif visitedp->adjvex=0/ 如p-&

13、gt;adjvex 顶点未拜访 、递归拜访它dfsg、p->adjvex;p=p->nextarc;/p指向顶点 v 的下一个邻接点bool dfstravealgraph *g、int i、int jint k;bool flag1=false、flag2=false; for k=0;k<g->n;k+visitedk=0;dfsg、i;/从顶点 i开头进行深度优先遍历 if visitedj=1flag1=true;for k=0;k<g->n;k+ visitedk=0;dfsg、j;/从顶点 j开头进行深度优先遍历if visitedi=1flag

14、2=true;if flag1 && flage2return true;精品学习资料精选学习资料 - - - 欢迎下载elsereturn false;精品学习资料精选学习资料 - - - 欢迎下载3.（ 15 分）（ 1）采纳快速排序的算法如下：（ 12 分）int quickselectint r、int s、int t、int k/在rs.t 序列中找第 k 小的元素精品学习资料精选学习资料 - - - 欢迎下载int i=s、j=t; int tmp;if s<t/区段内至少存在2个元素的情形tmp=rs;/用区段的第 1个记录作为基准while i.=j/从区

15、段两端交替向中间扫描、直至 i=j 为止while j>i && rj>=tmpj-;/从右向左扫描 、 找第 1个小于 tmp 的rjri=rj;/将rj 前移到 ri 的位置 while i<j && ri<=tmpi+;/从左向右扫描 、 找第 1个大于 tmp 的rirj=ri;/将ri 后移到 rj 的位置ri=tmp;if k-1=i return ri;else if k-1<i return quickselectr、s、i-1、k;/在左区段中递归查找 else return quickselectr、i+1、t、k;/在右区段中递归查找else if s=t && s=k-1/区段内只有一个元素且为rk-1 return rk-1;void minkint r、int n、int k/输出整数数组 r0. n-1中第 k 小的元素if k>=1 &&