2017年中国石油大学(北京)地球物理与信息工程学院955数据结构[专业硕士]考研强化模拟题
● 摘要
一、填空题
1． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
2． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的
数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。
【答案】①1; 1; f （m ，n －1）; n ②9
3． 当两个栈共享一存储区时，栈利用一维数组
当栈1空时
，
【答案】为_____，栈2空时
， 表示，两栈顶指针为则为_____，栈满时为_____。 【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
4． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
5． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，
关键字最多。
6． 线性表
【答案】（n －1）/2 用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为
7． 模式串
8． 中缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
9． 已知如下程序段：
语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。
【答案】（1）n ＋1
（2）n
（3）n （n ＋3）/2
（4）n （n ＋l ）/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。
10．一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
的next 函数值序列为_____。 【答案】01122312 对应的前缀式为_____，若则后缀式的
二、判断题
11．哈夫曼树无左右子树之分。（ ）
【答案】×
【解析】哈夫曼树就是一棵二叉树。
12．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ） 【答案】
【解析】队列只在下端（队尾）增加，在上端（队头）减少。
13．内排序要求数据一定要以顺序方式存储。（ ）
【答案】×
【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。
14．无环有向图才能进行拓扑排序。（ ）
【答案】√
【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。
15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
，使其n 个元素的最大（小）【解析】堆排序：基本思想先将原始序列构造成一个堆（初始堆）
值处于序列的第一个位置；然后交换序列第一个元素与最后一个元素的位置。
16．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ） 【答案】
函数，函【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个
数本身包含了模式串的局部匹配信息。
17．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
18．取线性表的第i 个元素的时间同i 的大小有关。（ ） 【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。