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

一、应用题

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

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

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

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

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

序列参加排序，

但对

法

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

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

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

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

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

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

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

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

图1

【答案】因为小为

因为

所以768和所以首址

大小为

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

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

其伙伴地址为

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

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

3． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：

4． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。

【答案】该二叉树如图所示：

图

5． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。

【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。

6． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？

（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？

（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？

1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（（2）G2最多n （n-l ）条边，最少n 条边。 （3）G3最多n （n-l ）条边，最少n-1条边。

7． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

（1）试问这种二叉树的结点总数是多少？ （2）试证明

。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。