2017年复旦大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。
【答案】n 个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j 趟起泡排序要进行次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排
2． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则因且k 为整数，故k=5，即最少5-路归并完成排序。
3． 证明任一结点个数为n 的二叉树的高度至少为0 （logn ）。
【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n 个结点的二叉树的最低高度是h ，则n 应满足
虑h 是整数. 则有即任一结点个数为n 的二叉树的高度至少为
4． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求
真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
5． 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目的是什么？ 并指出树和二叉树的主要区別。
【答案】（1）基本目的
序结束，下面语句段说明了标记flag 的使用。
。解此不等式，并考 两头匹配的
树的孩子兄弟链表表示法和二叉树的二叉链表表示法本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
（2）主要区别
一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制：三是二叉树允许为空，树一般不允许为空（有些书上考虑到与二叉树的转换，允许树为空）。
6． 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点； ②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点
请证明之；否则请举例说明。
【答案】题目中方法不一定能（或不能）求得最短路径。举例说明：
图（a ）
图（b ）
图（a ）中，假设初始顶点1到目标顶点4之间有一条边，权值x=2。显然图（a ）中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4, 即初始顶
点
显然， 一目标顶点4, 所经过的边的权值分别
为 ③重复步骤②，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，
因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最短路径。
图（b ）中，假设初始顶点为1、目标顶点为4, 欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。
7． 解答问题。设有数据逻辑结构为：
（1）画出这个逻辑结构的图示。
（2）相对于关系R ，指出所有的开始结点和终端结点。
（3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。 （4）分别画出该逻辑结构的正向邻接表和逆向邻接表。
【答案】
⑴如图1所示：
图1
（2）开始结点（入度为0）:
（3）拓扑序列：
规则：开始结点为
或之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 （4）正向邻接表如图2所示，逆向邻接表如图3所示：
终端结点（出度为0）:
图2 正向邻接表
图3 逆邻接表
相关内容
相关标签