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

一、算法设计题

1． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；

。其中，data 存放结点的值；lc 、rc 为指向左、

右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。

【答案】算法如下:

先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在

设P 指向二叉树的根结点

结束

在中序线索二叉树T 中,, 求给定值为x 的结点的

后继结点

首先在T 树上査找给定值为x 的结点，由p 指向

' 若P 的右标志为1, 则P 的rc 指针指向其后继

结点P 的右子树中最左边的结点是结点P 的中序后继

结库

.

2． 试编写一算法对二叉树按前序线索化。

【答案】算法如下:

设置前驱

对以线索链表为存储结构的二叉树BT 进行前序线索化

设置左线索

设置前驱的右线索

为建立右链做准备

前驱后移

第 2 页，共 33 页

左子树前序线索化

右子树前序线索化

结束

3． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

4． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。

【答案】算法如下::

打印从根结点bt 到结点p 之间路径上的所有结点

.

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

是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同

步

根结点就是所找结点

左子女入栈，并置标记

找到结点P , 栈中元素均为结点P 的祖先

从根结点到P 结点的路径为

沿左分支向下

本题不要求输出遍历序列，

这里只出栈

沿右分支向下

结束算法

为叶结点

第 3 页，共 33 页

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

从根结点到P 结点的路径为

输出从根到叶子q 的路径上的所有袓先

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

【答案】算法如下:

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

统计度为1的结点的个数

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

出队，访问结点

度为1的

结点

非空左子女入队

非空右子女入队

返回度为1的结点的个数

二、应用题

6． 调用下列C 函数f(n)，回答下列问题:

(1)试指出f(n)值的大小，并写出，f(n)值的推导过程；

(2)假定n ＝5, 试指出，f(5)值的大小和执行，f(5)时的输出结果。 C 函数:

【答案】(1)第一层FOR 循环判断n ＋1次，往下执行n 次，第二层FOR 执行次数为(n＋(n﹣1) ＋(n﹣2) ＋... ＋1) ，第三层循环体受第一层循环和第二层循环的控制，其执行次数如表所示。

执行次数

第 4 页，共 33 页