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

一、算法设计题

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

。

【答案】算法如下:

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

n 为偶数时

r 最小值

("最大值) ；

2． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下:

在二叉树t 中査找结点值等于x 的结

点

结束

统计以t 为根结点的子树的叶结点数

n0

. 叶结点

输出并计数

结束

:

3． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。

【答案】算法如下:

判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论

中序遍历左子树

中序遍历的第一个结点不必判断

前驱指针指向当前结点

不是完全二叉树

中序遍历右子树

算法结束

判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回

false

若左右子树均为二叉

排序树

左子树中的最大值和右子树中

的最小值

不是二叉排序树

结束

求二叉树左子树的最大值

返回机器最小整数

求二叉树右子树的最小值

返回机器最大整数

4． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。

(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。

【答案】(1)满足条件的二叉树如下:

(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:

全局变量

从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .

中序遍历右子树

叶结点

中序遍历左子树

5． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)

【答案】算法如下:

待排序记录的个数

关键字由d 个分量组成

静态链域

记录的其他数据域

存放n 个记录

.

用队列表示桶，共m 个

进行基数排序，返回收集用的链头指针

将

进行d 趟排序

初始化桶

按关键字的第j 个分量进行分配

k 为桶的序号

将将

链到桶头

链到桶尾

链成一个静态链表

将初始链表的终端结点指针置空，P 指向链表的第一个结点

队列的头、尾指针

对

修改桶的尾指针