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

一、填空题

1． 线性表

【答案】（n －1）/2

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

2． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

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

【答案】

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

4． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n

个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）若

是边，则

的值等于_____，若

不是边，则

的值是一个比任

何边的权，矩阵的对角线元素全为0。

（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若

【答案】（1）

已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边

（3）算法结束时，相邻矩阵中的元素指出最小生成树的

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

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

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

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

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

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

7． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

8． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。 9． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；

首

先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。

【答案】

10．表达式

【答案】

的后缀表达式是_____。

二、判断题

11．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为

【答案】

（ ）。

【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是

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

【答案】

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

13．无环有向图才能进行拓扑排序。（ ）

【答案】√

【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。

14．静态链表就是一直不发生变化的链表。（ ）

【答案】

【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。

15．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）

【答案】√

【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。

16．若一个广义表的表头为空表，则此广义表亦为空表。（ ）

【答案】×

【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。

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

【答案】

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

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

【答案】×

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

19．数组是同类型值的集合。（ ）

【答案】×

【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。