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

一、算法设计题

1． 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。

【答案】算法如下:

//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称

//i记下结点个数，s 是字符栈

//P是链表的工作指针，指向待处理的当前元素

//链表前一半元素入栈

//恢复最后的i 值

//若n 是奇数，后移过中心结点

//测试

是否中心对称

//链表中心对称

//链表不中心对称

//算法结束

2． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。

图

【答案】算法如下:

递增序输出二叉排序树中结点的值，滤去重复元素

中序遍历左子树

是当前访问结点的前驱，调用本算法时初值为

null

记重复元素，调用

本算法时初值为

前驱后移

中序遍历右子树

结束算法

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

【答案】算法如下:

//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列

//本算法将两链表合并成一个按元素值递减次序排列的单链表

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

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

//当两链表均不为空时

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

r

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

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

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

r

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

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

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

//算法Union 结束

4． 假设以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 均后移

//算法结束

5． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。

【答案】算法如下:

//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反

//空链表

//奇数序号结点在L1中