2018年中国科学技术大学计算机科学与技术学院834软件工程基础[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:
{二叉树根结点的指针}
【答案】算法如下:
生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写
)
是二叉树结点指针的一维数组，容量足够大
一维数组最后元素的下标
元素或虚结点
根结点
双亲结点和子女结点用指针链上
结束
2． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
结束本题
3． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下:
//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回
//对应字符相等，指针后移
4． 己知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如:
第一个数组为:4，12，28 第二个数组为:1，7，9，29，45 输出结果为:
第一个数组
第二个数组
【答案】算法如下:
//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中 //使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列
.
" 交换A[m﹣1]和
B[0]
//寻找A[m﹣1]的插入位置
//寻找B[0]的插入位置
算法结束
5． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
二、应用题