当前位置：问答库＞考研试题

一、填空题

1． 线性表

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为

2． 已知如下程序段：

用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

语句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。

3． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

4． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】

5． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）

【答案】3个

【解析】以3, 4先出栈的序列有34521、34215、34251共3个。

6．

每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是

中序序列是

前庁序列是_____。 【答案】

【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。

7． 空格串是指_____，其长度等于_____。

【答案】由空格字符（值32）所组成的字符串；空格个数

8． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

9． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

10．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）

.

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的

二、判断题

11．文件系统采用索引结构是为了节省存储空间。（ ）

【答案】×

【解析】是为了缩短查找的时间，牺牲了一部分存储空间。

12．在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）

【答案】×

【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转

13．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）

【答案】×

【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。

14．一个广义表可以为其他广义表所共享。（ ）

【答案】√

【解析】因为广义表中的元素还可能是表，所以对于一个广义表可以为其他广义表所共享。

15．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ） 【答案】

函数，函【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个

数本身包含了模式串的局部匹配信息。

16．抽象数据类型与计算机内部表示和实现无关。（ ） 【答案】

【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。

17．有n 个数顺序（依次）入栈，出栈序列有Cn 种

，

（ ） 【答案】

18．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ） 【答案】

【解析】队列只在下端（队尾）增加，在上端（队头）减少。

19．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）

【答案】×

【解析】折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为

与待排序记录的初始排列状态无关。