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

一、填空题

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

【答案】的次数最小。总次数为

2． 假定查找有序表

【答案】

表

平均查找次数为。

3． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构(网状结构)

4． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

5． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有

检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

。

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

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

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

6． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

7． 栈是_____的线性表，其运算遵循_____的原则。

【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出

8．

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

【答案】5；96

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

以它构造一棵哈夫曼树，则树高为_____，带权路径长度

9．

线性表

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

10．设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。

【答案】15 【解析】当

时，100n2>2n，而，

2n

时，100n ＜2

用数组表示，假定删除表中任一元素的概率相同，则删除一个元

素平均需要移动元素的个数是_____。

二、判断题

11．循环队列也存在空间溢出问题。（ ）

【答案】 √

【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。

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

【答案】×

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

。

13．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）

【答案】 ×

【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。

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

【答案】√

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

15．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的

【答案】 √

【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为

16．AOE 网一定是有向无环图。（ ）

【答案】×

【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。

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

【答案】×

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

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

【答案】√

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

19．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）

【答案】√

【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。

个结点在第k 层的任一位置上。（ ）