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

一、算法设计题

1． 写出一个递归算法来实现字符串逆序存储。

【答案】算法如下:

//字符串逆序存储的递归算法

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

2． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

顺序存储结构的线性表描述为:

线性表可能达到的最大长度}；

【答案】算法如下:

//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值

//当査找失败时，low ＝high ＋

1

//结束对分査找函数

//本过程生成顺序表

L

//顺序表L 初始化

//设x ＝9999时退出输入

//去查找x 元素

//不同元素才插入

//插入元素x ，线性表长度增

1

//结束过程creat

3． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

4． 当一棵有n(

) 个结点的二叉树按顺序存储方式存储在

中时，试写一个算法，求

出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

中，本算法求结点i 和j 的最近公共祖先结点的值

下标为i 的结点的双亲结点的下标

下标为j 的结点的双亲结点的下标

所査结点的最近公共祖先的下标是

整型

5． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下:

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

(“最长平台长度

在b 数组中起始下标为

”，1，

k)

，值是

设元素类型为

b 中连续的相等元素构成的子序列称为平台。试设计算法，

二、应用题

6． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度为T(m，n) 。估算最优的T(m，n) ，并简要说明理由。

【答案】最优的T(m，n) 是D(n)。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度。一般情况下，

7． 已知一个整数序列, 其中

且又如要求:

(1)给出算法的基本设计思想。 (2)根据设计思想, 采用C 或

或Java 语言描述算法, 关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

【答案】(1)算法的策略是从前向后扫描数组元素, 标记出一个可能成为主元素的元素Num 。然后重新计数, 确认Num 是否是主元素。

算法可分为以下两步:

, 若存在

, 则称5为主元素;

, 则称x 为A 的主元素。例如

则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中,

请设计一个尽可能高效的算法, 找出A 的主元素。若存在主元素, 则输出该元素; 否则输出-1。