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

一、算法设计题

1． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。

(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。

【答案】(1)满足条件的二叉树如下:

(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:

全局变量

从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .

中序遍历右子树

叶结点

中序遍历左子树

2． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

【答案】算法如下:

根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标

申请结点

是根

在中序序列中，根结点将树分成左右

子树

无左子树

递归建立左子树

无右子树

第 2 页，共 33 页

和是两个序列首、尾

递归建立右子树

结束:

3． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。

【答案】算法如下:

r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储

本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后

当前元素是红色

当前元素是白色

当前元素是蓝色

4． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。

【答案】算法如下:

//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面

//设链表有头结点

//q指向待处理结点

//P记数据域值最大的结点

//将P 摘下

//插人P 结点

5． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。

【答案】算法如下:

//本算法将无符号十进制整数m 转换为十六进制整数

第 3 页，共 33 页

本算法的递归描述如下:

//本算法将无符号十进制整数m 转换为十六进制整数

二、应用题

6． 画出对算术表达式表所示。

表 操作数栈和运算符栈的变化过程

F 求值时操作数栈和运算符栈的变化过程。

F 求值，过程如

【答案】设操作数栈是opnd ，运算符栈是optt ，对算术表达式

第 4 页，共 33 页