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

一、应用题

1． 请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列(例如0-2-7-9-11) 表示进行作业的路径。

完成此工程的关键路径是(A)完成此工程所需的最少天数为(B)天，此工程中具有最大充裕天数的事件是(C)，充裕天数是(D)。关键路径上的事件的充裕天数是(E)。

图

【答案】A.0-2-6-9-11；B.20；C. 事件顶点1、5和7各充裕两天；D.4天；E.0

2． 下列广义表，可以唯一对应一棵二叉树的有（ ）。并归纳出唯一对应的条件。

(1)(A(B(D，E) ，C(F)))

(2)(A(B(D，E) ，C))

(3)(A)

(4)(A(B(C，D(E))))

(5)（ ）

【答案】唯一对应一棵二叉树的有(2)、(3)和(5)。唯一对应的条件:空表、只有一个元素的表、每个子表个数是零或是2的表。

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

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

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

【答案】根据题目所给条件, 文件系统为一级目录结构, 文件的数据一次性写入磁盘, 已写入的

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

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

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

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

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

4． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。

【答案】证明:根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点:叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点:叶结点或仅有左子树的结点。命题得证。

5． 带权图(权值非负，表示边连接的两顶点间的距离) 的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法:

①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；

②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点

③重复步骤②，直到

请证明之；否则请举例说明。

【答案】题目中方法不一定能(或不能) 求得最短路径。举例说明:

图

(a)

; 是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，

图(b)

图(a)中，假设初始顶点1到目标顶点4之间有一条边，权值x ＝2。显然图(a)中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4,

即初始顶点

显然，

短路径。

图(b)中，假设初始顶点为1、目标顶点为4, 欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。

一目标顶点4, 所经过的边的权值分别为。大于2。因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最

二、算法设计题

6． 给定nxm 矩阵并设

设计一算法判定x 的值是否在A 中，要求时间复杂度

为O(m＋n) 。

【答案】算法如下:

//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中

//flag是成功査到x 的标志

//假定x 为整型

(“矩阵A 中无

算法search 结束。

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

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

【答案】算法如下:

非递归删除以r 为根的二叉排序树

栈，容量足够大，栈中元素是二叉排序树结点的指针

元素\n"，x) ；