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

一、算法设计题

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． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1

//不论A[i]是’I'或’〇' ，指针i 均后移

//算法结束

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

【答案】算法如下:

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

4． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。

【答案】算法如下:

利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成

树

数组存放生成树

数组存放顶点是否找到最短路径

初始化, 设顶点信息就是编号

从v0开始，求其最小生成树

是尚未到最小生成树的顶点的集合

循环n －1次

顶点u 已找到最短路径下，下面修改相关顶点的最短路径

算法结束

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

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