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

一、算法设计题

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

【答案】算法如下:

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

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

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

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

//分解原链表

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

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

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

【答案】算法如下:

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

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

3． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

【答案】算法如下:

//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表

//pa, pb 分别是链表la 和lb 的工作指针

//la作为结果链表的头指针，先将结果链表初始化为空

//当两链表均不为空时

//将pa 的后继结点暂存于

r

//将pa 结点链于结果表中，同时逆置

//恢复pa 为当前待比较结点

//将pb 的后继结点暂存于

r

//将pb 结点链于结果表中，同时逆置

//恢复pb 为当前待比较结点

//避免再对pa 写下面的While 语句

//算法Union 结束

4． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

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

递减序输出二叉排序树t 中所有左子树为空右子树非空的结点数据域的值

(2)非递归算法如下:

递减序输出二叉排序树t 中所有左子树为空、右子树非空的结点的数据域的值

S 是二叉排序树结点指针的栈，容量足够大

沿右分支向下

去左分支

算法结束

5． 己知L 为链表的头结点地址，表中共有m(m＞3) 个结点，从表中第i 个结点(l＜i ＜m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。

【答案】算法如下:

//L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置

//p是工作指针，初始指向第二结点(已假定i ＞

l) //pre是前驱结点指针，最终指向第i ﹣i 个结点

//计数器

//查找第i 个结点

//査找结束，P 指向第i 个结点

//暂存第i 个结点的指针

//p指向第i ＋l 个结点，准备逆置

//上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置

//暂存P 的后继结点

+

//逆置P 结点

//P恢复为当前待逆置结点