2017年中国人民公安大学安全工程823计算机学科专业基础综合[专业硕士]之数据结构考研强化模拟题
● 摘要
一、填空题
1． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
2． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
3． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
4． 完善算法：求KMP 算法.next 数组。
END ； 【答案】
5． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
6．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
7． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
8． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
9． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
10．深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
二、判断题
11．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
12．有n 个数顺序（依次）入栈，出栈序列有Cn 种，（ ）
【答案】
13．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
14．数组不适合作为任何二叉树的存储结构。（ ）
【答案】×
【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构是高效率的（存储密度大）。
15．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）
【答案】×
【解析】不一定。插入二叉排序树的原则：将新节点元素值与根结点元素值相比较，如小于 根结点元素值则插入到左子树口，否则插入到右子树中。所以就可能插在一个度为1的结点下面。
16．—个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）
【答案】√
【解析】树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。
17．在外部排序过程中，对长度为n 的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过
【答案】×
【解析】当输入文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段
18．循环队列也存在空间溢出问题。（ ）
【答案】
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
19．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（ ）
【答案】×
【解析】哈希文件是使用一个函数（算法）来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。
20．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）
【答案】×
【解析】折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为
与待排序记录的初始排列状态无关。
（ ）