2022年数据结构考试题4.docx

《2022年数据结构考试题4.docx》由会员分享，可在线阅读，更多相关《2022年数据结构考试题4.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 要求： 全部的题目的解答均写在答题纸上,需写清晰题目的序号；每张答题纸都要写上姓名和学号；一、单项挑选题（每道题2 分,共 20 小题,共计 40 分）1. 某算法的空间复杂度为O1,就；A.该算法执行不需要任何帮助空间B.该算法执行所需帮助空间大小与问题规模 n 无关C.该算法执行不需要任何空间D.该算法执行所需全部空间大小与问题规模 n 无关2. 在长度为 n 的次序表中插入一个元素,对应算法的时间复杂度为；A.O1 B.Olog 2n C.O n D.O n 2 3. 设线性表中有 n 个元素,以下运算中,在单链表上实现要比在次序表上实现

2、效率更高；A.删除指定位置元素的后一个元素B.在最终一个元素的后面插入一个新元素名师归纳总结 - - - - - - -C.次序输出前k 个元素D.交换第 i 个元素和第n- i+1 个元素的值（ i=1,2, , n）4. 以下数据结构中元素之间为非线性关系的是；A.栈B.队列C.线性表D.以上都不是5. 如一个栈用数组data1.n储备,初始栈顶指针top 为 n+1,就以下元素x 进栈的正确操作是；A.top+;datatop=x; B.datatop=x;top+; C.top- ;datatop=x; D.datatop=x;top - ; 6. 如某循环队列有队首指针front 和

3、队尾指针rear,在队不满时进队操作仅会改变；A.front B.rear C.front 和 rear D.以上都不队7. 设循环队列中数组的下标是0N- 1,其队头、 队尾指针分别为f 和 r（f 指向队首元素的前一位置,r 指向队尾元素） ,就其元素个数为；A.r- fB.r- f- 1 C.r- fN+1 D.r- f+NN8. 设树 T 的度为 4,其中度为1、2、3、4 的结点个数分别为4、2、1、1,就 T 中的叶子结点个数是；A.5 B.6 C.7 D.8 9. 一棵哈夫曼树中共有199 个结点,它用于多少个字符的编码；A.99 B.100 C.101 D.199 10. 设森

4、林 F 中有 4 棵树,第 1、2、3、4 棵树的结点个数分别为a、b、c、d,将森林第 1 页,共 7 页精选学习资料 - - - - - - - - - F 转换为一颗二叉树B,就二叉树B 根结点的左子树上的结点个数是；A.a- 1 B.a；C. a+b+cD.b+c+d11. 以下关于图的表达中,正确选项. 回路是简洁路径. 储备稀疏图,用邻接矩阵比邻接表更省空间. 如有向图中存在拓扑序列,就该图不存在回路A. 仅B. 仅、；C. 仅D. 仅、12. 以下关于有向图的说法中,正确选项A.强连通图是任何顶点到其他全部顶点都有边B.完全有向图肯定是强连通图C.有向图中任一顶点的入度等于出度D

5、.有向图边集的子集和顶点集的子集可构成原有向图的子图13.无向图的邻接矩阵是一个；C.上三角矩阵D.对角矩阵A.对称矩阵B.零矩阵14. 假如从无向图的任一顶点动身进行一次广度优先遍历即可拜访全部顶点,就该图肯定是；A.完全图 B.连通图 C.有回路 D.一棵树15. 用 Dijkstra 算法求一个带权有向图 G 中从顶点 0 动身的最短路径,在算法执行的某时刻, S=0,2,3,4 ,下一步选取的目标顶点可能是；A.顶点 2 B.顶点 3 C.顶点 4 D.顶点 7 16. 哈希表中显现冲突是指；A. 两个元素具有相同的序号B. 两个元素的关键字不同,而其他属性相同C. 数据元素过多D.

6、两个元素的关键字不同,而对应的哈希函数值（储备地址）相同17. 适合于折半查找的数据组织方式是；A.以链表储备的线性表 C.以链表储备的有序线性表B.以次序表储备的任意线性表 D.以次序表储备的有序线性表18. 对有 n 个记录的表进行直接插入排序,在最好情形下需比较 次关键字；A.n- 1 B.n+1 C.n/2 D.nn- 1/2 19. 如数据元素序列 11,12,15,7,8,9,23,1,5 是采纳以下排序方法之一得到的其次趟排序后的结果,就该排序算法只能是；A.冒泡排序 B.直接插入排序 C.挑选排序 D.二路归并排序20. 对一组数据 25,84,21,47,15,27,68,3

7、5,20 进行排序,前 第 1 趟： 20,15,21,25, 47,27,68,35,84 3 趟的排序结果如下：名师归纳总结 - - - - - - -第 2 页,共 7 页精选学习资料 - - - - - - - - - 第 2 趟： 15,20,21,25, 35,27,47,68,84 第 3 趟： 15,20,21,25, 27,35,47,68,84 就所采纳的排序方法是；C.二路归并排序D.快速排序A.简洁挑选排序B.希尔排序二、问答题（共 4 小题,共计 35 分）1. （10 分）对于如图1 所示的带权无向图,直接给出利用普里姆算法（从顶点0 开头构造）和克鲁斯卡尔算法构造

8、出的最小生成树的结果（留意：按求解的次序给出最小生成树的全部边,每条边用i ,j表示）；1 1 7 4 3 0 5 2 6 4 图 1 5 2 3 8 G 一个带权无向图2. （ 10 分 ） 假 设 一 棵 二 叉 排 序 树 的 关 键 字 为 单 个 字 母 , 其 后 序 遍 历 序 列 为 ACDBFIJHGE ,回答以下问题：（1）画出该二叉排序树； （ 6 分）（2）求在等概率下的查找胜利的平均查找长度；（2 分）（3）求在等概率下的查找不胜利的平均查找长度；（2 分）3. （8 分）已知序列 15,5,16,2,25,8,20,9,18,12 ,给出采纳二路归并排序法对该序列作

9、 升序排序时的每一趟的结果；4. （7 分）简要回答以下关于堆排序中堆的一些问题：（1）通常堆采纳次序仍是链式储备结构？（3 分）（2）设有一个小根堆, 即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字；其中具有最大关键字的结点可能在什么地方？（4 分）三、算法设计题（共 2 小题,共计 25 分）1. （10 分）某带头结点的非空单链表typedef struct node int data; struct node *next; LinkNode; L 中全部元素为整数,结点类型定义如下：设计一个尽可能高效的算法,将全部小于零的结点移到全部大于等于零的结点的前面；2. （15 分）假

10、设二叉树中有n 个结点,每个结点值为单个字符,而且全部结点值均不相同,采纳二叉链储备结构储备,其结点类型定义如下：名师归纳总结 - - - - - - -第 3 页,共 7 页精选学习资料 - - - - - - - - - typedef struct node char data; struct node *lchild,*rchild; BTNode; 请完成以下任务：（1）设计一个算法,在二叉树 b 中查找 x 结点（指结点值为 x 的结点）,如找到该结点,返回其地址,否就返回 NULL ；给出你设计的算法的时间复杂度；（8 分）（2）设计一个算法,利用（1）小题设计的算法输出二叉树

11、b 中 x 结点的全部子孙结点值；（ 7 分）名师归纳总结 - - - - - - -第 4 页,共 7 页精选学习资料 - - - - - - - - - “ 数据结构” 考试试题（A）参考答案一、单项挑选题（每道题 2 分,共 20 小题,共计 40 分）1. B 2. C 3. A 4. D 5. C 6. B 7. D 8. D 9. B 10. A 11. C 12. B 13. A 14. B 15. D 16. D 17. D 18. A 19. B 20. D 二、问答题（共 4 小题,共计 35 分）1. （10 分） 答案：利用普里姆算法从顶点0 动身构造的最小生成树为：0

12、,1 ,0,3,1,2,2,5,5,4 ,（5 分）；利用克鲁斯卡尔算法构造出的最小生成树为：分）；说明： 次序错误不给分；2. （10 分） 答案：（ 1 ） 该 二 叉 排 序 树 的 后 序 遍 历 序 列 为0,1 ,0,3,1,2,5,4,2,5 ,（5ACDBFIJHGE , 就 中 序 遍 历 序 列 为ABCDEFGHIJ ,由后序序列和中序序列构造的二叉排序树如图 2 所示；（6 分）E A B D F G H J C I 图 2 一棵二叉排序树（2）ASL 胜利=11+2 2+4 3+2 4+1 5/10=3 ；（2 分）（3）ASL 不胜利 =63+3 4+2 5/11=

13、40/11=3.64 ；（2 分）3. （8 分） 答案：采纳二路归并排序法排序的各趟结果如图3 所示；（每趟 2 分）名师归纳总结 - - - - - - -第 5 页,共 7 页精选学习资料 - - - - - - - - - 排序前 : 15,5, 16,2, 25,8, 20,9, 18,12 length=1:5, 15,2, 16,8, 25,9, 20,12,18 length=2:2, 5,15, 16,8, 9, 20,25,12,18 length=4:2, 5,8, 9, 15,16,20,25,12,18 length=8:2, 5,8, 9, 12,15,16,18,

14、20,25 排序后 : 2, 5,8, 9, 12,15,16,18,20,25 图 3 各趟排序结果4. （7 分） 答案：（1）通常堆采纳次序储备结构；（3 分）（2）小根堆中具有最大关键字的结点只可能显现在叶子结点中；由于最小堆的最小关键字的结点必是根结点,而最大关键字的结点由偏序关系可知,只有叶子结点可能是最大 关键字的结点； （4 分）三、算法设计题（共 2 小题,共计 25 分）1. （10分） 答案：void MoveLinkNode *&L LinkNode *p=L-next,*pre=L; /跳过小于 0 的结点 while p.=NULL & p-datanext; wh

15、ile p.=NULL if p-datanext=p-next; / 从链表中删除 *p 结点p-next=L-next; / 将 *p 结点插入到头结点之后L-next=p; p=pre-next; /p指向 *pre之后结点, pre不变 else pre=p; / 如 *p 结点值不小于0 /pre、p 同步后移一个结点p=p-next; 2. （15 分） 答案：（1）（ 7 分）BTNode *FindxBTNode *b,char x / / 在二叉树b 中查找 x 结点 BTNode *p; if b=NULL return NULL; 名师归纳总结 - - - - - - -

16、第 6 页,共 7 页精选学习资料 - - - - - - - - - else if b-data=x return b; p=Findxb-lchild,x; if p.=NULL return p; return Findxb-rchild,x; 算法的时间复杂度为 O n（1 分）；（2）（ 7 分）void SonsBTNode *b,char x / 输出 x 结点的子孙,初始时b 指向 x 结点 if b.=NULL if b-data.=x printf%c ,b-data; Sonsb-lchild,x; Sonsb-rchild,x; void OutSonsBTNode *b,char x /输出二叉树b 中 x 结点的全部子孙结点值 BNode *p= Findxb,x; if p.=NULL Sonsp,x; 名师归纳总结 - - - - - - -第 7 页,共 7 页