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

一、填空题

1． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

2． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

3． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为

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

【答案】93

【解析】对于上三角矩阵，将

5． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

6． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

7． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

在B 代入得93。

8． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

9． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】n （n-l ）/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。

10．顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

二、判断题

11．2，... ，n , 输出序列是栈的输入序列是1，

【答案】

若则有： （ ）【解析】出栈序列不一定满足比如1进栈，然后出栈，

12．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 【答案】

【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。

13．栈和队列都是限制存取点的线性结构。（ ） 【答案】

14．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）

【答案】×

【解析】不一定。插入二叉排序树的原则：将新节点元素值与根结点元素值相比较，如小于

根结点元素值则插入到左子树口，否则插入到右子树中。所以就可能插在一个度为1的结点下面。

15．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）

【答案】×

【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。

16．堆是满二叉树。（ ）

【答案】×

【解析】堆的定义：

n 个关键字序列

且

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

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

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

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

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

【答案】√

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

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

【答案】√

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

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

【答案】√

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

20．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ）

【答案】√

【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。

21．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易増加闲置空间的碎片。

（ ）

【答案】√

【解析】最佳适配法：将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法：从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。