2017年武汉大学数据结构和数据库(同等学力加试)之数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次 创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？
（2）为快速找到文件，对于FCB ，是集中存储好，还是与对应的文件数据块连续存储好? 要求说明理由。
【答案】根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储，这与一次刻录光盘的存储方式相似。对于这样的系统，因为不需要随时添加或删除文件的内容，所以一次写入的文 件的大小是固定不变的，也是可预知的，而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地 址和文件的大小，便可以通过计算的方法找到文件的任何位置。文件若需要修改，则原文件作废，修改以后的文 件以新文件的形式重新写入，不会产生存储碎片，高效，高利用率。所以，如下作答。
（1）连续的数据块组织方式更合适，因为文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以 多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容，所以一次写入的文件的大小是固定不变的，也是可预知的。这样，只需要知道文件的起 始地址和文件的大小，便可以通过计算的方法访问文件的任意位置。
为定位文件数据块。需要在FCB 中设计相关描述字段有： <起始块号，块数>或者〈起始块号，结束块号>。
（2）将所有的FCB 集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问FCB 对应的块，可减少磁头移动和磁盘I/O访问次数。
2． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。
3．
已知一个整数序列
其中
则称x 为A 的主元素。
例如若存在
且则称5为主元素；
又如
则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中，请设计一个
尽可能高效的算法，找出A 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或
【答案】
（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num 是否是主元素。
算法可分为以下两步：
①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num 保存到c 中，记录Num 的出现次数为1; 若遇到的下一个整数仍等于Num ，则计数加1否则计数减1; 当计数减到0时，将遇到的下一个整数保存到c 中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
②判断c 中元素是否是真正的主元素，再次扫描该数组，统计c 中元素出现的次数，若大于则为主元素；否则，序列中不存在主元素。
（2）算法实现如下：
用来保存候选主元素，count 用来计数
设置A [0]为候选主元素
查找候选主元素
为A 中的候选主元素计数
处理不是候选主元素的情况
更换候选主元素
统计候选主元素的实际出现次数
确认候选主元素
或Java 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。
不存在主元素
，空间复杂度为O （1）（3）时间复杂度为O （n ）。
4． 设目标为模式为
（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）
5． 系统中有多个生产者进程和消费者进程，，共享用一个可以存1000个产品的缓冲区（初始为空）当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量
求写出完整的过程；并指出所用信号量的含义和初值
【答案】设置5个信号量
empty :表示缓冲区是否为空，初值为1000
full ： 表示缓冲区是否为满，初值为0
mutex 1：生产者之间的互斥信号，初值为1
mutex2：消费者之间的互斥信号，初值为1
available :当前消费者能否访问缓冲区，初值为1
定义变量in , out 分别为生产者和消费者进程所要使用的指针，指向下一个可用的缓冲区单元，MaXNum= 1000 为缓冲区的大小，count 标志当前消费者已经取的产品的数量，初值为0
生产者进程：
生产一个产品；
操作实现进程间的互斥和同步，要