2017年北京科技大学550数学综合考试之数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。 【答案】（1）满足条件的二叉树如图1所示：
图1
（2）满足条件的二叉树如图2所示：
图2
2． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。
【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。
3． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。
4． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。
【答案】各种排序算法稳定性的归纳如图所示：
图
5． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。
图 存储映像7K 意图
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】
（1）算法的基本设计思想：
①分别求出strl 和str2所指的两个链表的长度m 和n ;
②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第
个结点；若
则使q 指向链表中的第
表尾的长度相等。
③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。
请设计一
个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字
或JA V A 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度。
则使p 指向链
个结点，即使指针p 和q 所指的结点到
（2）用C 语言算法描述如下：
两个指针同步向后移动
（3）参考答案的时间复杂度为：
或
其中m 、n 分别为两个链表的
长度。
6． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则
因
且k 为整数，故k=5，即
最少5-路归并完成排序。
7． 给出模式串在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下：
根据此定义，
可求解模式串
的next 和nextval 值如下：
返回共同C 缀的起始点
8． 已知有5个顶点的图G 如下图所示
请回答下列问题