2017年浙江农林大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 如果两个串含有相等的字符，能否说它们相等？
【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。
2． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。
【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：
3． 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次 创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？
（2）为快速找到文件，对于FCB ，是集中存储好，还是与对应的文件数据块连续存储好? 要求说明理由。
【答案】根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储，这与一次刻录光盘的存储方式相似。对于这样的系统，因为不需要随时添加或删除文件的内容，所以一次写入的文 件的大小是固定不变的，也是可预知的，而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地 址和文件的大小，便可以通过计算的方法找到文件的任何位置。文件若需要修改，则原文件作废，修改以后的文 件以新文件的形式重新写入，不会产生存储碎片，高效，高利用率。所以，如下作答。
（1）连续的数据块组织方式更合适，因为文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以 多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容，所以一次写入的文件的大小是固定不变的，也是可预知的。这样，只需要知道文件的起 始地址和文件的大小，便可以通过计算的方法访问文件的任意位置。
为定位文件数据块。需要在FCB 中设计相关描述字段有： <起始块号，块数>或者〈起始块号，结束块号>。
（2）将所有的FCB 集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问FCB 对应的块，可减少磁头移动和磁盘I/O访问次数。
4． 画出对算术表达式求值时操作数栈和运算符栈的变化过程。
【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式
表所示。
表 操作数栈和运算符找的变化过程 求值，过程如
5． 索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？
【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM 文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。
6． 某主机的MAC 地址为00-15-C5-C1-5E-28, IP 地址为10.2.128.100 （私有地址）。题a 图是网络拓扑，题b 图是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASCII 码内容。
题a 图网络拓扑