2018年郑州大学联合培养单位黄淮学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈，容量足够大，栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下，査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
2． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
【答案】算法如下:
3． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
结束本题
4． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。
【答案】算法如下:
//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个
数，初始为
//p和q 分别是链表A 和B 的工作指针
//pre为A 中p 所指结点的前驱结点的指针
//A
链表中当前结点指针后移
//B链表中当前结点指针后移
//处理A , B 中元素值相同的结点，
应刪除 //删除结点
5． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
二、应用题