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

一、应用题

1． 在

树和

树中查找关键字时，有什么不同？

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关

【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。

字后，要继续查到最下层结点，得到查找成功与否的结论。另外，键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

2． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题：

（1）画出哈希表示意图；

（2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示：

表 哈希示意图

（2）查找关键字63时，由于63比较。

（3）查找关键字60时，由于（4）

3．

设与记录

对应的关键字分别是

进行交换。

之前全部记录

（其

的关键字一定

如果存在

和

使得

且

哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，

为关键字，用

线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）

成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括为

又因

在

之前且

则

故

即说明

和

【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极

是反序；设对于

和

）中关键字最大为

，故经过起泡排序前i-2次比较后，

必定交换，证毕。

和Rf 为反序，由此可知

4． 有A 、B 两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方B 的信箱最多放N 提出的新问题组成一个邮件放入对方的邮箱中，设A 的信箱最多放M 个邮件，个邮件。初始时 A 的信箱中有x 个邮件邮件数减1. 。

A 、B 两人操作过程：

从A 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入B 的信箱；

从B 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入A 的信箱；

当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。 当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。

请添加必要的信号量和P 、V （或wait signed ）操作，以实现上述过程的同步，要求写出完整过程，并说明信号量的含义和初值。

【答案】首先定义两个互斥信号量：mutexA 和mutexB , 初始时为1，分别用来实现对A 的邮箱和B 的邮箱的互斥使用；然后针对A 的邮箱再定义两个信号量emptyA 和fullA ，

初值分别为

和X ，分别表示信箱中仍能存放信的数量和已经存放的信的数量，同理设置emptyB 和fullB , 初值为

和y 。

通信代码：

从A 的信箱中取出一个邮件；

B 中有y 个辩论者每取出一个邮件，

初始代码：

回答问题并提出一个新问题；

将新邮件放入B 的信箱；

从B 的信箱中取出一个邮件；

回答问题并提出一个新问题；

将新邮件放入A 的信箱；

5． S 是字符数组

，

中存放的是该字符串的有效长度，

假设

中字符串的内容为

说明下列程序的功能及执行结果。

【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。

6． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。

（1）按次序构造一棵二叉排序树BS 。

（2）依此二叉排序树，如何得到一个从大到小的有序序列？