2018年北京邮电大学网络技术研究院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 已知一具有n
个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递
归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。
【答案】算法如下:
由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树
和
为栈，容量足够大
分別是中序序列和后序序列第一和最后元素的下标，初始调用时
，
初始化
取出栈顶数据
在中序序列中査等于
.
根结点的值
无左子树
将建立左子树的数据入栈
无右子树
的结点
右子树数据入
结束
:
2． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回false 。
【答案】算法如下:
//la是结点的元素为整数的单链表。本算法判断从第二结点开始
//毎个元素值是否等干其序号的平方减去其前驱的值，如是返回true ；否则，返回
false
//P是工作指针，初始指向链表的第二项
//pre是p 所指结点的前驱指针
//i是la 链表中结点的序号，初始值为
2
//结点值间的关
系符合题目要求
//当前结点的值不等于其序号的平方减去前驱的值
//未查到表尾就结束了
//成功返回
//算法结束
//假设无头结点，初始P 指向第一元素结点
//初始p ﹣＞next 指向第二项
//失败
//成功
3． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(
) 改造为(
【答案】算法如下:
//本算法将线性表
//q指向a 1结点
//r记住a l 结点的指
针
//先将a 1结点放到正确位置
//从a 2结点开始
) 。
改造为
//暂存后继
//对称放置
//恢复待处理结点
4． 已知深度为h 的二叉树，以一维数组应的算法。
【答案】算法如下:
计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度
记叶结点数
若结点无孩子，则
是叶子
存储在数组后一半的元素是叶结点
5． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。
【答案】算法如下:
//设工作指针pa 和pb ；
//结果表中当前合并结点的前驱的指针
//交集并入结果表中
//释放结点空
间
//释放结点空间
//释放结点空间
//置链表尾标记
作为其存储结构，试编写一算法，求该二叉
树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相