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

一、填空题

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

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

2． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；（动态）链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

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

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

4． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。

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

【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。

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

6． 已知二维数组

为1000的连续存储区域时，

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为：

中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。

7． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

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

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

【答案】归并；堆

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

【答案】克鲁斯卡尔

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

10．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法

，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）

中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ）

{ if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/

{ （2） ;

if （node->rflag）（3）;

else {do t=*x；;

while （*x==node ）;

*x=t;

}

}

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

二、判断题

11．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）

【答案】×

【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。

12．负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）

【答案】√

【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素：哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。

13．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）

【答案】×

【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。

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

【答案】×

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

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

【答案】×

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

16．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）

【答案】×

【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。

17．静态链表就是一直不发生变化的链表。（ ） 【答案】

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

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

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