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

一、算法设计题

1． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

【答案】算法如下:

//串用一维数组s 存储，本算法求最长重复子串，返回其长度

//index记最长的串在s 串中的开始位置，max

记其长度

//length记局部重复子串长度，i 为字符数组下标

//上一个重复子串结束

//当前重复子串长

度大，则更新

max

//初始化下一重复子串的起始位置和长度

(”最长重复子串的长度为

.//算法结束

，在串中的位置

，max ，index) ；

时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。

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

【答案】算法如下:

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

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

3． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(

) 改造为(

【答案】算法如下:

//本算法将线性表

//q指向a 1结点

//r记住a l 结点的指

针

//先将a 1结点放到正确位置

//从a 2结点开始

//暂存后继

//对称放置

//恢复待处理结点

4． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

) 。

改造为

//交集元素并入结果表

//置结果链表尾

5． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。

【答案】算法如下:

L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符

//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表

//建立三个链表的头结点

//置三个循环链表为空表

//分解原链表

//L指向待处理结点的后继

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

二、应用题

6． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素, 各表中元素按升序排列。要求通过5次两两合并, 将6个表最终合并成1个升序表, 并在最坏情况下比较的总次数达到最小。请回答下列问题。

(1)给出完整的合并过程, 并求出最坏情况下比较的总次数。 (2)根据你的合并过程, 描述

个不等长升序表的合并策略, 并说明理由。

【答案】(1)6个表的合并顺序如下图所示。