2018年北京市培养单位自动化研究所408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
2． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。
【答案】定义队列:
//循环队列占m 个存储单元
//rear指向队尾元素，length 为元素个数
(1)设cq 是seQueue 类型变量，则当(2)队列的初始化:
//cq为循环队列，本算法进行队列初始化
//算法结束 (3)队列的插入:
//cq是已如上定义的循环队列，本算法将元素x 入队
//队满
.
//计算插入元素位置
//将元素x 入队列
//修改队列长度
//算法结束
//cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素
//队空
；//出队元素位置
//修改队列长度
//返回队头元素
//算法结束
3． 结点类型和存储结构如下:
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下:
对存储在数组R 中的记录进行排序
初始化
时队列空，当 时队列满。
(4)队列的删除:
设R[0]作监视哨，Max 是该类型最大元
素
初始假定第一个元素有序
前驱
第一个元素
査找第i 个元素的序号
将笫i 个元素链入静态链表
4． 已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
5． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
（ ）
//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个
) 是大根堆。
) 调整为大根堆；
调成大堆
其中n 表示随后输入英语单