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

一、填空题

1． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表

2． 已知二维数组

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

3． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

4． 已知一循环队列的存储空间为，其中n ＞m ，队头和队尾指针分别为front 和rear ，

中插入值为item 的元素，如该元素已在哈希表中，报告出错。 中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。 则此循环队列判满的条件是_____ 【答案】

5． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

6． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

7． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。

8． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

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

【答案】9

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

10．有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)

【答案】3个

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

二、判断题

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

【答案】×

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

12．在任何情况下，归并排序都比简单插入排序快。（ ）

【答案】×

【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。

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

【答案】 ×

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

14．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路) 。

【答案】√

【解析】采用深度优先搜索算法主要是通过设置标志位可以判断出一个有向图中是否有环。采用拓扑排序算法，如果能够构成一个拓扑排序，则有向图中没有环，否则，有向图中有环。

15．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）

【答案】×

【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。

16．倒排文件是对次关键字建立索引。（ ）

【答案】√

【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表) ，将所有具有相同次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。

17．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）

【答案】√

【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。

18．哈希表的平均查找长度与处理冲突的方法无关。（ ）

【答案】×

【解析】常见的处理冲突的方法:开放地址法；再哈希法；链地址法；建立一个公共的溢出区。选取不同的处理冲突的方法，哈希表的平均查找长度可能不同。

19．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）

【答案】×

【解析】例如起泡排序是稳定排序，将4， 3， 2，1按起泡排序排成升序序列，第一趟变成3， 2，1，4，此 时3就朝向最终位置的相反方向移动。