2018年北京大学深圳研究生院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
2． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
【答案】算法如下:
在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置
否则返回-1表示失败
元素序号
结束
，查找失败的平均查找
期望值分析:在等概率情况下，则查找成功的平均查找长度为等，则查找成功时和关键字比较的个数的期望值约为。
3． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
4． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。
【答案】算法如下:
//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反
//空链表
//奇数序号结点在L1中
//偶数序号
结点逆置插入到L2中
//置L1
表尾
5． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。
【答案】算法如下:
将满二叉树的后序序列转为前序序列，
长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相
是序列初始和最后结点的下
标。
根结点
左子树或右子树的结点数
将左子树前序序列转
为后序序列
将右子树前序序列转为
后序序列
二、应用题
6． (1)判定起泡排序的结束条件是什么？
(2)请简单叙述希尔排序的基本思想。 (3)将下列序列调整成堆(堆顶为最小值) 。
(4)在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。
【答案】(1)至多进行n －1趟起泡排序，或一趟起泡排序中未发生交换(即已有序) 时，结束排序。
(2)希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将待排序的记录划分成几组(缩小增量分组) ，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。
(3)13，24，33，65，70，56，48，92，80，112
(4)采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次(两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15次。将冠军的叶结点改为最
大值，均与兄弟比较，共4次选出亚军) 。
7． 已知一个整数序列
且又如要求:
(1)给出算法的基本设计思想。 (2)根据设计思想, 采用C 或
或Java 语言描述算法, 关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
, 其中
, 则称x 为A 的主元素。例如
, 若存在
, 则称5为主元素;
则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中,
请设计一个尽可能高效的算法, 找出A 的主元素。若存在主元素, 则输出该元素; 否则输出-1。