2018年郑州大学产业技术研究院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。
【答案】算法如下:
按递减次序输出二叉排序树结点的值
是元素为二叉树结点指针的栈，容量足够大
沿右子树向下
结束
2． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。
【答案】算法如下:
//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为
//p和q 分别是链表A 和B 的工作指针
//pre为A 中p 所指结点的前驱结点的指针
//A
链表中当前结点指针后移
//B链表中当前结点指针后移
//处理A , B 中元素值相同的结点，
应刪除 //删除结点
3． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。
(1)编写用前序遍历树中每个结点的非递归算法；
(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:
全局变量
递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为
1)
是桟s 的栈顶指针，栈容量足够大
访问根结点，设虚结点
以0表示
右子女的下标位置入
栈
沿左子女向下
取出栈顶元素
结束
(2)算法如下:
打印最大序号叶结点的全部袓先
找最大序号叶结点，该结点存储时在最后
的双亲结点
f
从结点c 的双亲结点直到根结点，
路径上所有结点均为祖先结点
逆序输出，最老的祖先最后输出
结束
4． 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈，容量足够大，栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下，査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
5． 已知一具有n
个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递
归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。
【答案】算法如下:
由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树
和
为栈，容量足够大
初始化
取出栈顶数据
在中序序列中査等于
.
根结点的值
无左子树
将建立左子树的数据入栈
无右子树
右子树数据入
分別是中序序列和后序序列第一和最后元素的下标，初始调用时
，
的结点