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

一、填空题

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

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

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

请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:

left 指向其左孩子，

【答案】

3． 外排序的基本操作过程是_____和_____。

【答案】生成有序归并段(顺串) ；归并

4． 应用prim 算法求解连通网络的最小生成树问题。

(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值

)

left 指向其前驱；，

right 指向其后继。

，

right 指向其右孩子，，

，

(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在

图的顶点数，应由用户定义

用二维数组作为邻接矩阵表示

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

选具有最小权值的候选边

图不连通，出错处理

修改候选边集合

【答案】(1)

(2)

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于

中

是连通图

，

，v ，

直到

，开始，重复执行下述操作:在所有u 属于

加入集合

，同时将并入

的边为止。

属于E 中找一条代价最小的边

5． 空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

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

检索和_____检索。

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

7． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。

8． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

a 中存放待排序的关键字

【答案】

【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。