2017年沈阳建筑大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 简述广义表属于线性结构的理由。
【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。
2． 一个长度为的升序序列S , 处在第「L/2」个位置的数为S 的中位数。例如，若序列Sl= （11，13, 15, 17，19），则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= （2, 4, 6, 8, 20）, 则S1和S2的中位数是11。现有两个等长升序序列A 和B ，试设计一个时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。
【答案】（1）算法的基本设计思想：分别求两个升序序列A 和B 的中位数，设为a 和b 。 ① 若a=b，则a 或b 即为所求的中位数。
② 否则，若a 所在序列B 的较大一半。若a>b，中位数只能出现（b ，a ）范围内，舍弃b 所在序列B 的较小一半，同时舍弃a 所在序列A 的较大一半。 ③在保留的两个升序序列中求出新的中位数a 和b ，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。 （2）用C 语言算法描述如下： //分别考虑奇数和偶数，保持两个子数组元素个数相等 // 若 元 素 个 数 为 奇 数 个 //舍弃A 中间点以前部分且保留中间点 //舍弃B 中间点以后部分且保留中间点 } //若元素个数为偶数个 //舍弃A 中间点及中间点以前部分 //舍弃B 中间点以后部分且保留中间点 //若元素个数为奇数个 //舍弃A 中间点以后部分且保留中间点 //舍弃B 中间点以前部分且保留中间点 //若元素个数为偶数个 //舍弃A 中间点以后部分且保留中间点 //舍弃B 中间点及中间点以前的部分 （3）说明算法的复杂性：算法的时间复杂度、空间复杂度分别是 3． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。 【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。 4． 已知有5个顶点的图G 如下图所示 请回答下列问题 （1）写出图G 的邻接矩阵A （行、列下标从0开始）。 （2）求什么？ 矩阵中位于0行3列元素值的含义是什么？ 非零元素的含义是 （3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则【答案】（1）邻接矩阵为 （2） 为： 0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。 （3） 中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为 m 的路径的条数。 5． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。 【答案】删除P 后 删除D 后