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

一、填空题

1． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

2． 在单链表中设置头结点的作用是_____。

【答案】方便运算

3． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】O(1)；O(n)

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

4． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择；完全二叉树；；O(1)；满足堆的性质

5． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree是有n 个分量的一维数组，放顶点的入度，

(3)函数crein 用于记算顶点入度；

(4)有三个函数

回1，否则0) 。

第 2 页，共 43 页 其含义为数据data 入栈，出栈和测试栈是否空(不空返

("图有回路") ;

【答案】

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度

减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

6． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

7． 组成串的数据元素只能是_____。

【答案】字符

8． 在哈希函数中，p 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

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

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

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

10．在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

二、判断题

11．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）

【答案】×

【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找

第 3 页，共 43 页

算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

12．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）

【答案】×

【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。

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

【答案】√

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

14．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）

【答案】 ×

【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例:假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。

15．排序算法中的比较次数与初始元素序列的排列无关。（ ）

【答案】×

【解析】这个要看是哪个排序算法，比如快速排序，初始序列为有序的情况比较的次数就相对于无序的多。

16．二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点(X)的值；其右子树根结点的值大于等于该结点(X)的值，则此二叉树一定是二叉排序树。（ ）

【答案】×

【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点; 其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。

17．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）

【答案】 ×

【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。

第 4 页，共 43 页