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

一、填空题

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

【答案】顺序

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

2． —个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

3． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

4． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n (n－1) /2

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。

5． 已知如下程序段:

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

6． 索引顺序文件既可以顺序存取，也可以 _____存取。

【答案】随机

7． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。

8． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态) 链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

9． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

10．一个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

在B

二、判断题

11．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）

【答案】 ×

【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。

12．堆是满二叉树。（ ）

【答案】×

【解析】堆的定义:

n 个关键字序列称为堆，当且仅当该序列满足如下性质(简称为堆性质) :

①②且且

小根堆:满足第①种情况的堆；

大根堆:满足第②种情况的堆。

因此并不能保证堆是满二叉树。

13．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）

【答案】√

【解析】从哈希表删除一个记录，不是将这个记录的位置置空，而是设置一个标记，标记这个元素是无效的了。

14．二叉树中序线索化后，不存在空指针域。（ ）

【答案】×

【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

15．抽象数据类型与计算机内部表示和实现无关。（ ）

【答案】 √

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

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

【答案】×

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

17．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）

【答案】 √

【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

18．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）

【答案】×