2017年上海大学数据结构与应用算法之数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。
（1）试指出判别给定序列是否合法的一般规则；
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。
（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。
2． 证明：置换选择排序法产生的初始归并段的长度至少为m （m 是所用缓冲区的长度）。
【答案】证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，
，缓以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时（即初始归并段）
冲区中m 个元素中除最小元素之外，其他m-1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。证毕。
3． 设LS 是一个线性表，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少? 若元素插
在
【答案】需要分两种情况讨论：
，插入位置0..n ，则平均移动个数为（1）等概率（后插）
（2）若不等概率，则平均移动的元素个数为
4． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
与
之间的概率
为则插入一个元素需要平均移动的元素个数又是多少？
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
（3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图2所示：
图2
5． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式
给出它的next 函数值及next 函数的修正值nextval 之值。
【答案】KMP 算法的时间复杂性是p 的next 和nextval 值分别为01112212321和01102201320。
6． 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？
【答案】（1）数据类型的定义
数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整
，其操作有加、减、乘、除、型、实型、字符型等。整型值的范围（对具体机器都应有整数范围）
求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。
（2）抽象数据类型的定义
“抽象数据类型（ADT ）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部
如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。
（3）两者的不同
请
抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。
（4）抽象数据类型的主要特点
，而是向“科学”迈进了一步。 抽象数据类型的出现使程序设计不再是“艺术”
（5）使用抽象数据类型的好处
使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提
，而不必了解实现细节。 供接口）
7． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：
（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。
（2）当n=7时，给出一个最好情况的初始排序的实例。
（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。
（4）当n=7时，给出一个最坏情况的初始排序的实例。
【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为
以此类推，
总共进行
需2次，共10次即可。
（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。
（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为
n=7时，最坏情况下的比较次数为21次。
（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。
8． 已知有5个顶点的图G 如下图所示
所以当的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。
（2）求矩阵中位于0行3列元素值的含义是什么？
非零元素的含义是（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则