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

一、算法设计题

1． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。

【答案】算法如下:

全局变量链表头指针

将

若bt 不空

中序遍历左子树

叶结点

第一个叶结点

生成头结点

头结点的左链空，右链指向第一个结点

第一个叶结点左链指向头结点，pre 指向当前叶结点

中序遍历右子树

最后一个叶结点的右链置空(链表结束标记

)

结束

；

2． 己知字符串S1中存放一段英文，写出算法format(s1，s2，s3，n) ，将其按给定的长度n 格式化成两端对齐的字符串S2，其多余的字符送S3。

【答案】算法如下:

//将字符串si 拆分成字符串S2和字符串S3，要求字符串S2长度为n 且两端对齐

//滤掉s1左端空格

("字符串s1为空串或空格串\n")；exit(0)；

}

//字符串S1向字符串S2中

复制

(”字符串s1没有

个有效字符\n"，n) ；exit(0)；}

第 2 页，共 38 页

树中的所有叶结点链成带头结点的双链表

当前叶结点链入双链表

//若最后一个字符为空格，

则需向后找到第一个非空格字符

//P指针也后退

//往后査找一个非空格字符作为串S2的尾字

符

("s1串没有

//字符串s2最后一个非空字符

//置S2字符串结束标记

//将s1串其余部分送字符串

S3

//置串S3结束标记

3． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。

【答案】算法如下:

判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论

中序遍历左子树

中序遍历的第一个结点不必判断

前驱指针指向当前结点

不是完全二叉树

中序遍历右子树

算法结束

判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回

false

若左右子树均为二叉

排序树

左子树中的最大值和右子树中

的最小值

不是二叉排序树

结束

求二叉树左子树的最大值

第 3 页，共 38 页

个两端对齐的字符串exit(0)；

}

返回机器最小整数

求二叉树右子树的最小值

返回机器最大整数

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． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

【答案】算法如下:

在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，

第 4 页，共 38 页