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

一、填空题

1． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。

【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

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

【答案】

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

3． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

4． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

②执行程序，f （6，4）=_____。 【答案】①1; 1; f （m ，n －1）; n ②9

5． 在哈希函数中，P 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

6． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

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

（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

〔始顶点号，终顶点号，权值）

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

的值在〈limits •h>中

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

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

//生成树的边结点

//边的起点与终点

//边上的权值

//最小生成树定义

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

//初始化最小生成树

T

//依次求MST 的候选边

//遍历当前候选边集合

//选具有最小权值的候选边

//图不连通，出错处理

//修改候选边集合

【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图

，是N

上最小生成树边的集合。算法从属于

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

【答案】

【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行

E T 开始，重复执行下述操作：在所有u

属于

加入集合

同时将

并入

v

直到

的边（u ，v ）属于E

中找一条代价最小的边为止。