2017年信阳师范学院计算机学科专业基础综合之数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD （Rl ）, R0”的功能为（R0）+（（R1））－（R1）, 即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。
图
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
表
【答案】执行阶段每个节拍（时钟周期）的功能和有效控制信号见下表。
表
2． 已知两个各包含IV 和M 个记录的排好序的文件能在时间内合并为一个包含个记录的排好序的文件。当有多于两个排好序的文件要被合并在一起时，只需重复成对地合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现有文件，FI ，F2，F3，F4，F5，各有记录数为20，30，10，5和30，试找出记录移动次数最少的合并步骤。
，【答案】类似最优二叉树（哈夫曼树）可先合并含较少记录的文件，后合并较多记录的文件，
使移动次数减少，如图所示的哈夫曼树。
图
3． 设目标为模式为
（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）
4． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。
【答案】（1）满足条件的二叉树如图1所示：
图1
（2）满足条件的二叉树如图2所示：
图2
5． 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次 创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？
（2）为快速找到文件，对于FCB ，是集中存储好，还是与对应的文件数据块连续存储好? 要求说明理由。
【答案】根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储，这与一次刻录光盘的存储方式相似。对于这样的系统，因为不需要随时添加或删除文件的内容，所以一次写入的文 件的大小是固定不变的，也是可预知的，而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地 址和文件的大小，便可以通过计算的方法找到文件的任何位置。文件若需要修改，则原文件作废，修改以后的文 件以新文件的形式重新写入，不会产生存储碎片，高效，高利用率。所以，如下作答。
（1）连续的数据块组织方式更合适，因为文件的数据一次性写入磁盘，已写入的文件不可修