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

一、应用题

1． 设散列表为数分别为

：

注：％是求余数运算中，函数码序列为

（2）计算搜索成功的平均搜索长度

表示颠倒十进制数x 的各位，如

即表的大小为

其

等。若插入的关键

，现采用双散列法解决冲突。散列函数和再哈希函

（1）试画出插入这8个关键码后的哈希表；

【答案】（1）插入这8个关键码后的哈希表如表所示：

表 插入关键字后的哈希表

（2）

2． 在改进了的（无回溯）字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。

{在模式P 中求nextval 数组的值

}

算法中第4行有

第六行中也有

两处比较语句相同。请分析说明此两处比较

语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？

【答案】第4行的

语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则

语句的意义是，当第J 个字符在模式匹配中失

指针J 和K 均増加1，继续比较。第6行的

配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K

个字符和第J 个字符相等，则下个与主串匹配的字符是第K

个字符失配时的下一个（即

）。该算法在最坏情况下的时间复杂度

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

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

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

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

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

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

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

则调用

次筛选算

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

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

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：

图2

5． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号 机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

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

【答案】（1）互斥资源：取机号，故设一个互斥信号量mutex 。

（2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。空座位的有、 无影响等待顾客数量，顾客的有、无决定两营业员是否能开始服务。另外，顾客获得空座位后，需要等待叫号和被服务，顾客与营业员就服务何时开始有同步关系。设信号量teller ，customer 和mutex 初值分别为0，0和1，设waiting 为整型量，表示排队的储户数量，其初始为0, 表示顾客初始时为0, 最大不超过10 （10把座椅），各进程的具体实现如下所示：