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

一、填空题

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

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

)

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

的值在

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

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

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

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

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

选具有最小权值的候选边

第 2 页，共 72 页

中

图不连通，出错处理

修改候选边集合

【答案】(1)

(2)

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

的边为止。

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

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

3． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。

4． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

5． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。

6．

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

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

第 3 页，共 72 页

是连通图

，

，v ，

直到

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

加入集合

，同时将并入

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

在B

7． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)

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

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

8． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

。当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为

一个元素时，此时堆的元素个数最少，元素个数为。

9． 设数组数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

(1)存放该数组至少需要的单元数是_____；

(2)存放数组的第8列的所有元素至少需要的单元数_____； (3)数组按列存储时，元素A[5，8]的起始地址是_____。 【答案】270；27；2204

【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。

10．以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

第 4 页，共 72 页