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

一、算法设计题

1． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

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

【答案】算法如下:

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

假定权值为整型

建立顶点向量

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

束算法运行

申请结点

弧结点中权值域

算法结束

第 2 页，共 36 页

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

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

【答案】算法如下:

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

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

沿左分枝向下

出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间

在二叉排序树T 中删除所有小于等于x

的结点

根结点的值小于等于

x

删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止

沿根结点左分支向下，査小干等于x 的结点

q 记P 的双亲

结点的值小于等于

x

再査原P 的右子树中小于等于x 的结点

4． 已知一具有n

个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递

归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。

【答案】算法如下:

由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树

和

第 3 页，共 36 页

分別是中序序列和后序序列第一和最后元素的下标，初始调用时

，

为栈，容量足够大

初始化

取出栈顶数据

在中序序列中査等于

.

根结点的值

无左子树

将建立左子树的数据入栈

无右子树

右子树数据入

结束

:

的结点

5． 写出算法，求出中序线索二叉树中给定值为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 的中序后继

结库

.

第 4 页，共 36 页