2018年北京市培养单位植物研究所408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。
【答案】算法如下:
将满二叉树的后序序列转为前序序列，
标。
根结点
左子树或右子树的结点数
将左子树前序序列转
为后序序列
将右子树前序序列转为
后序序列
2． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。
【答案】算法如下:
//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为
//p和q 分别是链表A 和B 的工作指针
//pre为A 中p 所指结点的前驱结点的指针
//A
链表中当前结点指针后移
//B链表中当前结点指针后移
//处理A , B 中元素值相同的结点，
应刪除 //删除结点
第 2 页，共 36 页
是序列初始和最后结点的下
3． 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈，容量足够大，栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下，査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
4． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。
【答案】算法如下:
//head是带头结点的单链表的头指针
//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间
//循环到仅剩头结点
第 3 页，共 36 页
//pre为元素最小值结点的前驱结点的指针
//P为工作指针
//记住当前最小值结点的前驱
//输出元素最小值结点的数据
//删除元素值最小的结点，释放结点
空间
//释放头结点
5． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
在后半部分继续进行划分
在前半部分继续进行划分
) 小元素。
二、应用题
6． 简述广义表属于线性结构的理由。
【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性:在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。
7． 输入一个正整数序列(53，17，12，66，58，70，87，25，56，60) ，试完成下列各题。
(1)按次序构造一棵二叉排序树BS 。
(2)依此二叉排序树，如何得到一个从大到小的有序序列？
第 4 页，共 36 页