2018年辽宁省培养单位沈阳自动化研究所408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
第 2 页，共 39 页
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
算法结束
2． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下:
//s和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作成功返回1，否则返回0表示失败
//检査参数及置换后的长度的合法性
//若S 串被替换的子串长度小于t 串长度，则S 串部分右移
//S串中被替换子串的长度小于t 串的长度
//将t 串复制到S 串的适当位置
//算法结束
//本算法是串的置换操作，将串S 中所有非空串t 相等且不重叠的子串用V 代替
//判断S 是否有和t 相等的子串
//串S 中包含和t 相等的子串
//creat操作是将串常量(此处为空串) 赋值给
temp
//求串t 和s 的长度
//用串v 替换t 形成部
分结果
//将串s 中串后的部分形成新的s 串
//求串s 的长度
//在新s 串中再找串t 的位置
//将串temp 和剩余的串s 连接后再赋值给s
}//if结束
//算法结束
第 3 页，共 39 页
3． 已知一具有n
个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递
归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。
【答案】算法如下:
由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树
和
为栈，容量足够大
初始化
取出栈顶数据
在中序序列中査等于
.
根结点的值
无左子树
将建立左子树的数据入栈
无右子树
右子树数据入
结束
:
4． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
的结点
分別是中序序列和后序序列第一和最后元素的下标，初始调用时
，
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
第 4 页，共 39 页
的双亲结点