2017年重庆大学数据结构与算法(同等学力等加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求
真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
2． 请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天
数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）
表示进行作业的路径。
完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充
，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。
两头匹配的
图1
【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0
3． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。
【答案】（1）内部排序中的归并排序是在内存中进行的归并排序，辅助空间为外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。
（2）因为归并的趟数
部排序的效率。
其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都可减少归并趟数。应用中通过败者树进行多（k ）路平衡归并和置换一选择排序减少m ，来提高外
4． 设阶稀疏矩阵A 有t 个非零元素，其三元组表示为
表示A 才有意义？
的个存储单元，用二维数组存储时占用
试问：非零元素的个数t 达到什么程度时用，共占用三元组表
元组）时，用【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三个单元，
只有当表示A 才有意义。解不等式得
5． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？
【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元
，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）
元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小且分布没有规律。用十字链表作存储结构自然失去了随机
最差情况下是因此也失去存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为了随机存取的功能。
6． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。
（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述
n
【答案】
（1）6个表的合并顺序如下图所示。
个不等长升序表的合并策略，并说明理由。
对应于合并过程的哈夫曼树
根据上图中的哈夫曼树，6个序列的合并过程为：
第1次合并：表A 与表B 合并，生成含45个元素的表AB ;
第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ;
第3次合并：表D 与表E 合并，生成含110个元素的表DE ;
第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ;
第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。
由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比
较的总次数计算如下：
第1次合并：最多比较次数= 10+35-1=44;
第2次合并：最多比较次数=45+40-1 = 84;
第3次合并：最多比较次数=50+60-1 = 109;
第4次合并：最多比较次数=85+110-1 = 194;
第5次合并：最多比较次数= 195+200-1 = 394; 比较的总次数最多为：44+84+109+194+394 = 825。
（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。
7． （1）对于有向无环图，叙述求拓扑有序序列的步骤；
（2）对于图1，写出它的四个不同的拓扑有序序列。
图1
【答案】（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。
2）在图中删除该顶点及所有以它为尾的弧。
3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
（2）拓扑有序序列如图2: