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

一、填空题

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

【答案】顺序存储结构

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

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

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

3． 已知二维数组

为1000的连续存储区域时

，

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为：

4． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

5． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为

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

【答案】单链表；双链表；（动态）链表；静态链表

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

7． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

第 2 页，共 54 页 中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。

8． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

9． 在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

10．从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶

个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；

树每个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

二、判断题

11．堆是满二叉树。（ ）

【答案】×

【解析】堆的定义：

n 个关键字序列

且

且 称为堆，当且仅当该序列满足如下性质（简称为堆性质）：

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

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

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

12．二维以上的数组其实是一种特殊的广义表。（ ）

【答案】√

【解析】广义表是线性表的推广。广义表中的元素还有可能是广义表。对于维数大于二的数组，它在某一维上的元素还是数组。符合广义表的定义，因此二维以上的数组其实是一种特殊的广义表。

第 3 页，共 54 页

13．倒排文件的目的是为了多关键字查找。（ ）

【答案】√

【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为：多重表文件和倒排文件。

14．归并排序辅助存储为

【答案】×

【解析】归并排序的辅助存储是

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

【答案】×

【解析】外部排序方法：按可用内存大小，将外存上含n 个记录的文件分成若干长度为z 的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串（run ）。对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序（产生初始归并段）所需的时间

存信息读写的时间内部归并所需的时间

16．B-树中所有结点的平衡因子都为零。（ ）

【答案】√

【解析】一棵m 阶的B-树，如果不为空，则所有的叶子结点都出现在同一层次上，所以B-树总的所有结点的平衡因子都为零。

17．在初始数据表已经有序时，快速排序算法的时间复杂度为

【答案】×

【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为〇（n2）。

18．串长度是指串中不同字符的个数。（ ） 【答案】

【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。

19．二叉树是一般树的特殊情形。（ ）

【答案】×

第 4 页，共 54 页 （ ） 外 （ ）