2018年大连理工大学管理与经济学部408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。
【答案】算法如下:
//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾
//申请结点空间
//将s 结点链入队尾
//rear指向新队尾
//rear是带头结点的循环链队列的尾指针
//本算法执行出队操作，成功输出队头元素；否则给出出错信息
//s指向队头元素
//队头元素出队
//空队列
2． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
3． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
4． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。
【答案】算法如下:
判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论
中序遍历左子树
中序遍历的第一个结点不必判断
前驱指针指向当前结点
不是完全二叉树
中序遍历右子树
算法结束
判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回
false
若左右子树均为二叉
排序树
左子树中的最大值和右子树中
的最小值
不是二叉排序树
结束
求二叉树左子树的最大值
返回机器最小整数
求二叉树右子树的最小值
返回机器最大整数
5． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
的双亲结点