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

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）。