2017年合肥工业大学科研机构和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研冲刺密押题
● 摘要
目录
2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研冲刺密押题（一） .. 2 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研冲刺密押题（二） 10 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研冲刺密押题（三） 18 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研冲刺密押题（四） 25 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研冲刺密押题（五） 34
一、填空题
1． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
2． 模式串
的next 函数值序列为_____。
【答案】01122312
3． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】
4． 假定查找有序表
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
5． 栈是_____的线性表，其运算遵循_____的原则。
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
编号，以rear 指示实际的队尾元素，现
要在此队列中插入一个新元素，新元素的位置是（ ）。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
6． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
7． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
8． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
9． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
【答案】2（N-1）
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。
10．建立索引文件的目的是_____。
【答案】提高查找速度
二、判断题
11．拓扑排序的有向图中，最多存在一条环路。（ ）
【答案】×
【解析】要进行拓扑排序，需要满足一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在 顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件, 所以拓扑排序的有向图中不能存在环路。
12．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
【答案】√
【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。
13．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
14．在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
15．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
【答案】行效率较低。
16．广义表
【答案】×
【解析】长度为1。因为只含一个元素即子表
17．通常使用队列来处理函数或过程的调用。（ ）
【答案】
【解析】经常使用栈来处理函数或过程的调用。
18．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
19．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为
【答案】
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操作的时间复杂度是
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执
的长度是4。（ ）
（ ）。