2018年辽宁省培养单位沈阳自动化研究所408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
2． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
结束本题
3． 起泡排序算法是把大的元素向上移(气泡的上浮) ，也可以把小的元素向下移(气泡的下沉；请给出上浮和下沉过程交替的起泡排序算法。
【答案】算法如下:
相邻两趟向相反方向起泡的起泡排序算法，
起泡的上下界
设不发生交换
以上向下起泡
有交换，修改标志
change
修改界
气泡下沉，小元素上浮(向左
)
修改下界
4． 己知L 为链表的头结点地址，表中共有m(m＞3) 个结点，从表中第i 个结点(l＜i ＜m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。
【答案】算法如下:
//L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置
//p是工作指针，初始指向第二结点(已假定i ＞
l) //pre是前驱结点指针，最终指向第i ﹣i 个结点
//计数器
//查找第i 个结点
//査找结束，P 指向第i 个结点
//暂存第i 个结点的指针
//p指向第i ＋l 个结点，准备逆置
//上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置
//暂存P 的后继结点
+
//逆置P 结点
//P恢复为当前待逆置结点
//计数器增
1
//将原第i 个结点的后继指针指向原第m 个结点
5． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。
【答案】算法如下:
利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成
树
数组存放生成树
数组存放顶点是否找到最短路径
初始化, 设顶点信息就是编号
从v0开始，求其最小生成树
是尚未到最小生成树的顶点的集合
循环n －1次
顶点u 已找到最短路径下，下面修改相关顶点的最短路径
算法结束
二、应用题
相关内容
相关标签