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

一、填空题

1． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

2． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

3． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。 【答案】

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

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

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

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

【答案】方便运算

6． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

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

【答案】n

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

8． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____

，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））

【答案】归并；堆

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

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

10．线性表

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为

用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

二、判断题

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

【答案】√

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

12．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ）

【答案】×

【解析】哈希表的结点中可以包括指针，指向其元素。如哈希链表。

13．倒排文件的目的是为了多关键字查找。（ ）

【答案】√

【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为：多重表文件和倒排文件。

14．在待排数据基本有序的情况下，快速排序效果最好。（ ）

【答案】×

【解析】在待排数据基本有序的情况下，插入排序效果最好。

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

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

【答案】×

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

17．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）

【答案】×

【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

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

【答案】×

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

19．强连通分量是无向图的极大强连通子图。（ ）

【答案】×

【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。

20．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ） 【答案】

【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。

21．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）

【答案】√

【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

22．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（ ）

【答案】×

【解析】哈希文件是使用一个函数（算法）来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。