2018年三峡大学计算机与信息学院936数据结构[专业硕士]考研基础五套测试题
● 摘要
一、算法设计题
1． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。
【答案】算法如下:
根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标
申请结点
是根
在中序序列中，根结点将树分成左右
子树
无左子树
递归建立左子树
无右子树
递归建立右子树
结束:
2． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
第 2 页，共 38 页
和是两个序列首、尾
求左子树表示的子表达式的值
求右子树表示的子表达式的值
3． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
査询成功，值域为x 的结点的count 增
1
4． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类PASCAL 语言编写时间复杂度为0(m＋n) 的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。
【答案】算法如下:
＝大于非零元素个数的某个常量
//本算法实现以三元组表存储的各有m 和n 个非零元素两个稀疏矩阵相加，结果放到A 中
//L，p 为A ，B 三元组表指针，k 为结果三元组表榫针(下标
)
第 3 页，共 38 页
//行号不等时，行号大者的三元组为结果三元组表中一项
//A中当前项为结
果项
//B中当前项为结果
当前项
//行号相等时，比较列号
//结束行号相等时的处理
//结束行号比较处理
//结果三元组表的指针前移(减
1)
//结束WHILE 循环。
//处理B 的剩余部
分
//处理A 的剩余部
分
//稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数＜m ＋
n
//三元组前移，使第一个三元组的下标
为
1
//修改结果三元组表中非零元素个数
//结束addmatrix
5． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。
(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。
【答案】(1)满足条件的二叉树如下:
(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:
全局变量
第 4 页，共 38 页