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

一、算法设计题

1． 假设K1，... ，Kn 是n 个关键词，试解答：

(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树。

(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立如图所示的二叉查找树。

图

该二叉查找树的嵌套括号表示结构为:B(A，D(C，E)) 。 【答案】(1)算法如下:

在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针

f

以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树

不再插入相同值结点

.

申请结点空间

根结点

左子女

右子女

结束算法 (2)算法如下:

以嵌套括号表示结构打印二叉排序树

打印根结点值

左子女和右子女中至少有一个不空

输出左栝号

输出左子树的嵌套括号表示

若右子树不空，输出逗号

输出右子树的嵌套括号表示

输出右括号

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

【答案】算法如下:

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

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

。

【答案】算法如下:

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

n 为偶数时

r 最小值

("最大值

) ；

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

【答案】算法如下::

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

.

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

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

步

根结点就是所找结点

左子女入栈，并置标记

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

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

沿左分支向下

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

这里只出栈

沿右分支向下

结束算法

为叶结点

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

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

5． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。

(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。

(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。

【答案】(1)算法如下:

按关键字第一个字母在字母表中的顺序输出各关键字

哈希地址

1~26

设哈希表初始值为null