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

一、应用题

1． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。

图1

【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：

图2 图3

2． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：

（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；

（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。

【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：

图1

（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示：

图2

3． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？

【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元

，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）

元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小且分布没有规律。用十字链表作存储结构自然失去了随机

最差情况下是因此也失去存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为了随机存取的功能。

4． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

5． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？

【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，

每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序

列。

（2）最低位优先

先对最低位关键字

位关键字

序列参加排序，

但对法 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。

6． 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点； ②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点

请证明之；否则请举例说明。

【答案】题目中方法不一定能（或不能）求得最短路径。举例说明：

图（a ）

图（b ）

图（a ）中，假设初始顶点1到目标顶点4之间有一条边，权值x=2。显然图（a ）中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4, 即初始顶

点

显然， 一目标顶点4, 所经过的边的权值分别

为 ③重复步骤②，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，

因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最短路径。

图（b ）中，假设初始顶点为1、目标顶点为4, 欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。

7． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。