当前位置：问答库＞考研试题

一、应用题

1． 某文件系统为一级目录结构, 文件的数据一次性写入磁盘, 已写入的文件不可修改, 但可多次创建新文件。请回答如下问题。

(1)在连续、链式、索引三种文件的数据块组织方式中, 哪种更合适? 要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？

(2)为快速找到文件, 对于FCB , 是集中存储好, 还是与对应的文件数据块连续存储好? 要求说明理由。

【答案】根据题目所给条件, 文件系统为一级目录结构, 文件的数据一次性写入磁盘, 已写入的文件不可修改, 但是可以多次创建新文件, 我们得知该文件系统是不能修改原文件的, 只能将修改后的文件按新文件来存储, 这与一次刻录光盘的存储方式相似。对于这样的系统, 因为不需要随时添加或删除文件的内容, 所以一次写入的文件的大小是固定不变的, 也是可预知的, 而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地址和文件的大小, 便可以通过计算的方法找到文件的任何位置。文件若需要修改, 则原文件作废, 修改以后的文件以新文件的形式重新写入, 不会产生存储碎片, 高效, 高利用率。所以, 如下作答。

(1)连续的数据块组织方式更合适, 因为文件的数据一次性写入磁盘, 已写入的文件不可修改, 但是可以多次创建新文件, 我们得知该文件系统是不能修改原文件的, 只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容, 所以一次写入的文件的大小是固定不变的, 也是可预知的。这样, 只需要知道文件的起始地址和文件的大小, 便可以通过计算的方法访问文件的任意位置。

为定位文件数据块。需要在FCB 中设计相关描述字段有:

<起始块号, 块数>或者<起始块号, 结束块号>。

(2)将所有的FCB 集中存放, 文件数据集中存放。这样在随机查找文件名时, 只需访问FCB 对应的块, 可减少磁头移动和磁盘访问次数。

2． 已知两个各包含IV 和M 个记录的排好序的文件能在0(N+M)时间内合并为一个包含N+M个记录的排好序的文件。当有多于两个排好序的文件要被合并在一起时，只需重复成对地合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现有文件，FI ，F2，F3，F4，F5，各有记录数为20，30，10，5和30，试找出记录移动次数最少的合并步骤。

【答案】类似最优二叉树(哈夫曼树) ，可先合并含较少记录的文件，后合并较多记录的文件，使移动次数减少，如图所示的哈夫曼树。

图哈夫曼树

3． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？

【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便，但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定:当

当时，lchild 指向左子树，当时，Ichild 指向前驱；当时，rchild 指向右子树，时，rchild 指向后继。这样，在线索二叉树(特别是中序线索二叉树) 上遍历就消除了递归，也不使用栈(利用后序线索二叉树查后继仍需要栈) 。

4． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示(如SXSX) 。

(1)试指出判别给定序列是否合法的一般规则；

(2)两个不同合法序列(对同一输入序列) 能否得到相同的输出元素序列? 如能得到，请举列说明。

【答案】(1)通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。

(2)可以得到相同的输出元素序列。例如，输入元素为A ，B ，C ，则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。

5． 简述广义表属于线性结构的理由。

【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性:在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。

二、算法设计题

6． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。

【答案】算法如下:

建立有向图的十字链表存储结构

假定权值为整型

建立顶点向量

当输入i 、j 、v 之一为0时，结

束算法运行

申请结点

弧结点中权值域

算法结束

7． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。

【答案】算法如下:

在用邻接表方式存储的无向图g 中，删除边(i,

j)

删顶点i 的边结点(i, j) , pre 是前驱指针

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

8． 设排序二叉树中结点的结构为下述三个域构成:

Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。

【答案】算法如下: