2018年曲阜师范大学信息科学与工程学院859数据结构[专业硕士]考研强化五套模拟题
● 摘要
一、算法设计题
1． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素
在C 中的存放位置下标的公式。
//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置
//算法结束
2． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
第 2 页，共 57 页
和B 的
【答案】算法如下:
(”最长重复子串的长度为
.//算法结束
，在串中的位置，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
3． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。
【答案】算法如下:
顺序表中记录个数
关键字
该关键字在顺序表中的下标
索引表的一项
关键字
记录中的其他数据
给有m 个记录的顺序表seq 建立索引表
index
监视哨
关键字放入正确位置
第i 个记录的下标
4． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。
【答案】算法如下:
将满二叉树的后序序列转为前序序列，
标。
根结点
左子树或右子树的结点数
将左子树前序序列转
为后序序列
将右子树前序序列转为
第 3 页，共 57 页
是序列初始和最后结点的下
后序序列
5． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。
【答案】算法如下:
二路插入排序的算法
辅助存储
插人后部
折半査找插入位置
移动元素
插入有序位置
插入前部
移动元素
将序列复制回去
6． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。
串被确认的最大长度
【答案】算法如下:
第 4 页，共 57 页
中关键字分二路分别按序插入到辅助向量
前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分