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

一、填空题

1． 假定查找有序表

【答案】

表

平均查找次数为。

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

【答案】2

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

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

【答案】93

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

4． 阅读下列程序说明和程序，填充程序中的_____。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:

(1)把根结点放入堆栈。

(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。

第 2 页，共 60 页

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【解析】折半查找时每个的次数如表所示:

在B

【答案】

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。

5． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。

【答案】2(n－1)

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。

6． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。

【答案】操作系统文件；数据库

7． 已知一循环队列的存储空间为则此循环队列判满的条件是_____

【答案】

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

【答案】选择；完全二叉树；

9．

给定一组数据WPL 的值为_____。

【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树:

；O(1)；满足堆的性质

以它构造一棵哈夫曼树，则树高为_____，带权路径长度，其中n ＞m ，队头和队尾指针分别为front 和rear ，

10．对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

第 3 页，共 60 页

二、判断题

11．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）

【答案】√

【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。

12．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）

【答案】×

【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。

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

【答案】×

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

14． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）

【答案】 ×

【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。

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

【答案】×

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

16．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）

【答案】 √

【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。

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

【答案】√

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

18．一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（ ）

【答案】 ×

第 4 页，共 60 页

。（ ）