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

一、算法设计题

1． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

【答案】算法如下:

在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，

将其

插入到二叉排序树中

f 指向当前结点的査找值为x 的结点，

双亲

无值为x 的结点，插入之

査询成功，值域为x 的结点的count 增

1

2． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

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

【答案】算法如下:

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

j)

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

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

4． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。

【答案】算法如下:

层次遍历二叉树，并统计度为1的结点的个数

统计度为1的结点的个数

是以二叉树结点指针为元素的队列

出队，访问结点

度为1的

结点

非空左子女入队

非空右子女入队

返回度为1的结点的个数

5． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:

{二叉树根结点的指针}

【答案】算法如下:

生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写

)

是二叉树结点指针的一维数组，容量足够大

一维数组最后元素的下标

元素或虚结点

根结点

双亲结点和子女结点用指针链上

结束

二、应用题

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

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

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

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