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

一、算法设计题

1． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

2． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。

【答案】算法如下:

//设整数序列存于数组a 中，共有n 个，本算法求解其最大值

3． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下:

在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回

确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情况

返回第一邻接点，

第 2 页，共 40 页 取第一个边结点

和中必有一个等于

i

4． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。

【答案】算法如下:

在中序线索树t 上，求结点p 的双亲结点q

暂存

找P 的中序最右下的结点

顺右线索找到q 的后继(P的袓先结点

)

若后继是头结点，则转到根结点

根结点无双亲

找最右结点的过程中回找到

P

结束FFA

5． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的(以其中之一为0标志结束) ，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。

提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。

【答案】算法如下:

建立有向图的邻接表存储结构

输入顶点信息

题目要求两顶点之一为0表示结束

准备到左子树中找

P 二、应用题

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

(1)在连续、链式、索引三种文件的数据块组织方式中, 哪种更合适? 要求说明理由。为定位文

第 3 页，共 40 页

件数据块。需要在FCB 中设计哪些相关描述字段？

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

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

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

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

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

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

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

排序有各种方法，如插入排序、快速排序、堆排序等。

设一数组中原有数据如下:15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。（ ）排序的结果为:12，13，15，18，20，60

（ ）排序的结果为:13，15，18，12，20，60

（ ）排序的结果为:13，15，20，18，12，60

（ ）排序的结果为:12，13，20，18，15，60

【答案】①快速排序②起泡排序③直接插入排序④堆排序

8． 解答问题。设有数据逻辑结构为:

(1)画出这个逻辑结构的图示。

(2)相对于关系R ，指出所有的开始结点和终端结点。

(3)分别对关系R 中的开始结点，举出一个拓扑序列的例子。

(4)分别画出该逻辑结构的正向邻接表和逆向邻接表。

第 4 页，共 40 页