2018年山东大学数据结构考研真题.doc

发布时间：2022-09-16 发布人：admin 分类：说明书资料大小：0.06M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2018 年山东大学数据结构考研真题一、简答题（每小题 6 分，共 30 分） 1.对于散列表，请回答下列问题（1）什么是散列表的负载因子? （2）在线性开型寻址散列表中实现删除时，如果只是把删除元素所在的桶置空，会出现什么问题?给出一种你的解决办法。 2.给出一组关键字（Q，H，C，Y，P，A，M，S，R，D，F，X），按关键字递增顺序，使用直接选择排序算法进行排序，写出第二趟排序结果。 3.前序序列为 A，B，C，D 的二叉树，中序序列可能是 D，A，B，C 吗?二叉树的层次遍历序列为 ABCDEFGHIJ，中序遍历序列为 DBGEHJACIF，写出该二叉树的前序遍历序列。 4.某二叉搜索树（二叉排序树）的层次遍历序列为（30，20，50，10，60，70），该二叉搜索树是不是完全二叉树?为什么? 5.已知图的邻接矩阵如下，写出从顶点 0 出发的深度优先遍历序列。

二、应用题（每题 10 分，共 60 分） 1.一个班级有 15 个学生，使用 1、2、3、…、14、15 作为学号。（i，，j）表示学生 i 和学生 j 参加了同一个兴趣小组。对给出的集合 S={（1，2），（6，9），（15，7），（1，6）}，请基于模拟指针设计数据结构表示集合 S 中的兴趣小组，并罗列 S 中所有的兴趣小组。 2.有 n 个猴子围成一圈，按顺时针编号，分别为 1 到 n。现打算从中选出一个大王。经过协商，决定选大王的规则如下∶从第一个开始顺时针报数，报到 m 的猴子出圈，紧接着从下一个又从 1 顺时针循环报数，..，如此下去，最后剩下来的就是大王。请设计数据结构并描述如何选出大王。 3.什么是优先队列，什么是堆?为什么使用堆描述优先队列比使用线性逻辑描述优先队列更好?什么情况下使用左高树描述优先队列比使用堆描述优先队列更好? 4.设一 3 序（阶）B-树，从空树开始，按序列{20，30，50，52，60，68，70}顺序依次插入关键码，画出得到的 B-树∶在得到的 B-树中删除 50 和 68，画出每一次删除后的 B-树。 5. 若无向图 G 的顶点度数的最小值大于或等于 2，证明 G 必然存在环路。 6.用 Dijkstra 算法求下图中 vl 到其余各顶点的最短路径，给出过程。

三、算法题（每题 20 分，共 60 分） 1.线性表用单链表存储，请设计单链表类 Chain 的一成员函数 simpleselectsorlklist（），实现简单选择排序算法，并分析算法复杂度。 2.设二叉树采用链式存储结构，定义结点结构为（leftchild，data，rightchild），其中 data 为元素的值，leftchild 和 rightchild 分别表示指向左子结点的指针和指向右子结点的指针，root 为指向根的指针。试编写算法，求给定二叉树上从根节点到叶子节点的一条路径长度等于树的深度减一的路径（即列出从根节点到该叶子节点的节点序列），若这样的路径存在多条，则输出路径终点在"最左"的一条。要求叙述算法思想并给出算法实现，分析算法的时间复杂性。 3.已知无向图以邻接表存储，试编写算法删除边（i，j）。

分享到：

赞收藏

资料库

2018年山东大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料