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

一、算法设计题

1． 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中(注:按层从上到下，由左到右) 。

【答案】算法如下:

是结点在一维数组中的编

号

队列，容量足够大

本算法将二叉树的二叉链表存储结构转换为顺序存储结构

seq

初始化，#代表虚结点

根结点入队

存入顺

序存储结构

左

子女入队

右

子女人队

2． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

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

【答案】算法如下:

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

中序遍历左子树

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

前驱指针指向当前结点

不是完全二叉树

中序遍历右子树

算法结束

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

false

若左右子树均为二叉

排序树

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

的最小值

不是二叉排序树

结束

求二叉树左子树的最大值

返回机器最小整数

求二叉树右子树的最小值

返回机器最大整数

4． 输入一个字符串，内有数字和非数字字符，如:akl23x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a 中，例如123放入a[0]，456放入a[l]，...... 。编程统计其共有多少个整数，并输出这些数。

【答案】算法如下:

（ ）

//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数

//整数存储到数组a ，i 记整数个数

//从左到右读入字符串

//'#'是字符串结束标记

//是数字字符

//数初始化

//拼数

//若拼数中输入了’#’，则不再输入

//输入非数字且非#时，继续输入字符

("共有

个整数，它们是:

)

//每10个数输出在一行上

//算法结束

5． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。

【答案】算法如下:

以后序遍历算法求以二叉树表示的算术表达式的

值

.

求左子树表示的子表达式的值

求右子树表示的子表达式的值