2017年合肥工业大学科研机构和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研强化模拟题
● 摘要
目录
2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研强化模拟题（一） .. 2 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研强化模拟题（二） 10 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研强化模拟题（三） 17 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研强化模拟题（四） 27 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区850计算机科学与技术学科专业基础综合之数据结构考研强化模拟题（五） 35
一、填空题
1． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
2． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
3． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】的次数最小。总次数为
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测
4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为
5． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
6． 设广义表
则
是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
7． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
8． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机 9． 中缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
10．设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
对应的前缀式为_____，若
则后缀式
的
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
二、判断题
11．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ）
【答案】√
【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所
以该图的拓扑有序序列必定存在。
12．队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）
【答案】
【解析】队列是一种先入先出型结构，而栈才是先进后出的线性结构。
13．对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
【答案】√
，【解析】形状不同的两个二叉排序树（关键字集合相同）在中序遍历下是输出排好序的序列，所以顺序是一致的。
14．二元查找树的任何结点的左右子树都是二元查找树。（ ）
【答案】√
【解析】二元查找树也称作二元排序树。二元查找树的性质：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。
15．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
【答案】
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
16．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）
【答案】×
【解析】折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为与待排序记录的初始排列状态无关。
17．在初始数据表已经有序时，快速排序算法的时间复杂度为
【答案】×
【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为〇（n2）。
18．广义表
【答案】×
【解析】长度为1。因为只含一个元素即子表
（ ）
的长度是4。（ ）