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

一、算法设计题

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

【答案】算法如下:

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

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

【答案】算法如下:

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

树

数组存放生成树

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

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

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

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

循环n －1次

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

算法结束

3． 假设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)算法如下:

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

打印根结点值

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

输出左栝号

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

若右子树不空，输出逗号

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

输出右括号

4． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

【答案】算法如下:

//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性

//题目要求下标从1开始

//对分査找元素x 的插入位置

//元素后移

//将元素x 插人

算法结束

设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。

时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。

5． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。

【答案】算法如下:

//A是的矩阵，本算法求矩阵A 中的马鞍点