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

一、应用题

1． 阅读下面的算法，说明算法实现的功能。

【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。

2． 如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

3． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求

真子串？且为最大真子串？

【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。

4． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？

【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

5． 对下面的关键字集若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。

【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为

第 2 页，共 38 页 两头匹配的用除留余数法设计

哈希函数，哈希函数为

（2）哈希表如表所示：

表 哈希表

（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，

当其哈希地址为时的查找次数。本例中

（4）算法如下：

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

第 3 页，共 38 页 故查找失败和查找成功时的平均查找长度分别为：

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

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

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

//座椅数，也是最多排队的储户数

//定义信号量

//储户进程

//先获得排队机

//若还有座椅则取号

//取号，占用座椅等待叫号

//告知系统储户加1

//释放排队机

//若没有座椅了，则不取号

//不取号，释放排队机

//离开

//并发调度无限循环

//叫号

//需要获得排队机的控制权

//将等候的顾客数减1

//提供柜员服务

//释放排队机

//为储户服务

第 4 页，共 38 页 //等待储户的柜员资源

//排队等待服务的储户数量

//对排队机操作的互斥量

//在座椅上休息等待的储户数

//等待柜员叫号

//进入窗口被服务