2018年北京市培养单位材料科学与光电技术学院864程序设计之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
//字符串结尾标记
//结束算法InvertStore
2． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
在b 数组中起始下标为
”，1，
k)
b 中连续的相等元素构成的子序列称为平台。试设计算法，
3． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
4． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
结束本题
5． 已知一具有n
个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递
归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。
【答案】算法如下:
由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树
和
为栈，容量足够大
分別是中序序列和后序序列第一和最后元素的下标，初始调用时
，
初始化
取出栈顶数据
在中序序列中査等于
.
根结点的值
无左子树
将建立左子树的数据入栈
无右子树
的结点
右子树数据入
结束
:
二、应用题