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

一、应用题

1． 请回答下列关于堆（Heap ）的一些问题：

（1）堆的存储表示是顺序的还是链接的？

（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？

（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？ 【答案】（1）堆的存储是顺序的。

（2）最大值元素一定是叶结点，在最下两层上。

（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下： 由于第i 层上的结点数至多是

以它为根的二叉树的深度为

则调用

次筛选算

法时总共进行的关键字比较次数不超过下式之值：

2． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。

图1

【答案】因为小为

因为

所以768和所以首址

大小为

互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址

将其插入可利用空间表中。回

其伙伴地址为

512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：

图2 回收后该伙伴系统的状态图

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

【答案】（1）最高位优先（MSD ）法

先对最高位关键字进行排序，将序列分成若干子序列，

每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字列。

（2）最低位优先先对最低位关键字位关键字

序列参加排序，

但对

法

进行排序，然后对高一级关键字

进行排序，依次重复，直至对最高

进行排序，按值不同再分成若干更小的子序列，依

次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序

排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个

排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序

时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。

4． 请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天 数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。

完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。

图1

【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0

5． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度，并简要说明理由。 为T （m ，n ）。估算最优的T （m , n ）

【答案】最优的T （m ，n ）是D （n ）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度。一般情况下，

6． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求真子串？且为最大真子串？

【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有

为了

不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。 7． 设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。

【答案】n 个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j 趟起泡排序要进行

次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排

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

序结束，下面语句段说明了标记flag 的使用。

两头匹配的

图1

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