2018年北京市培养单位国家天文台864程序设计之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
2． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
3． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
4． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)
【答案】算法如下:
待排序记录的个数
关键字由d 个分量组成
静态链域
记录的其他数据域
存放n 个记录
.
用队列表示桶，共m 个
进行基数排序，返回收集用的链头指针
将
进行d 趟排序
初始化桶
按关键字的第j 个分量进行分配
k 为桶的序号
将将
链到桶头
链到桶尾
链成一个静态链表
将初始链表的终端结点指针置空，P 指向链表的第一个结点
队列的头、尾指针
对
修改桶的尾指针
扫描下一个记录
找第一个非空的桶
为收集链表的头指针，t 为尾指针
连接非空桶
本趟收集完毕，将链表的终端结点指针置空
5． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为: