2017年温州大学电子技术之数据结构考研复试核心题库
● 摘要
一、应用题
1． 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次 创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？
（2）为快速找到文件，对于FCB ，是集中存储好，还是与对应的文件数据块连续存储好? 要求说明理由。
【答案】根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储，这与一次刻录光盘的存储方式相似。对于这样的系统，因为不需要随时添加或删除文件的内容，所以一次写入的文 件的大小是固定不变的，也是可预知的，而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地 址和文件的大小，便可以通过计算的方法找到文件的任何位置。文件若需要修改，则原文件作废，修改以后的文 件以新文件的形式重新写入，不会产生存储碎片，高效，高利用率。所以，如下作答。
（1）连续的数据块组织方式更合适，因为文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以 多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容，所以一次写入的文件的大小是固定不变的，也是可预知的。这样，只需要知道文件的起 始地址和文件的大小，便可以通过计算的方法访问文件的任意位置。
为定位文件数据块。需要在FCB 中设计相关描述字段有： <起始块号，块数>或者〈起始块号，结束块号>。
（2）将所有的FCB 集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问FCB 对应的块，可减少磁头移动和磁盘I/O访问次数。
2． 解答问题。设有数据逻辑结构为：
（1）画出这个逻辑结构的图示。
（2）相对于关系R ，指出所有的开始结点和终端结点。
（3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。
（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。
【答案】
⑴如图1所示：
图1
（2）开始结点（入度为0）:
（3）拓扑序列：
规则：开始结点为
或之后，若遇多个入度为0的顶点，按顶点编号顺序选择。
（4）正向邻接表如图2所示，逆向邻接表如图3所示：
终端结点（出度为0）:
图2 正向邻接表
图3 逆邻接表
3． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。
（1）试指出判别给定序列是否合法的一般规则；
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定
序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。
（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。
4． 设LS 是一个线性表，若采用顺序存储结构，则在等概率的前提下，插
与
之间的概率
为入一个元素需要平均移动的元素个数是多少? 若元素插
在
【答案】需要分两种情况讨论：
，插入位置0..n ，则平均移动个数为（1）等概率（后插）
（2）若不等概率，则平均移动的元素个数为
则插入一个元素需要平均移动的元素个数又是多少？
5． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
6． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的
，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）
于表示栈号，x 为入栈值。
，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）
共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：
相关内容
相关标签