2017年重庆工商大学数据结构(C语言)复试实战预测五套卷
● 摘要
一、应用题
1． 设目标为模式为
（1）计算模式p 的nextval 函数值；
（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。
【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。
（2）利用KMP （改进的nextval ）算法，每趟匹配过程如下：
第一趟匹配：
abcab （i=5, j=5）
第二趟匹配：
abc （i=7，j=3）
第三趟匹配：
a （i=7，j=l）
第四趟匹配：
（成功）abcabaa （i=15，j=8）
2． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？
【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。
3． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插
第 2 页，共 33 页
入适当位置。
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 。
通信代码：
第 3 页，共 33 页 B 中有y 个辩论者每取出一个邮件，初始代码：
从A 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入B 的信箱；
从B 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入A 的信箱；
5． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：
（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；
（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。
【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：
第 4 页，共 33 页
相关内容
相关标签