2017年沈阳建筑大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？
【答案】朴素的模式匹配度达到
时间复杂度是
KMP 算法有一定改进，时间复杂
主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配
时，KMP 算法的优点更为突出。
2． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？
【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）
元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小
且分布没有规律。用十字链表作存储结构自然失去了随机
最差情况下是
因此也失去
存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为
了随机存取的功能。
3． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。
（1）试指出判别给定序列是否合法的一般规则；
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。
（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。
4． 阅读下列算法，指出算法A 的功能和时间复杂性。
【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。
时间复杂度：0（n ）。
5． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有
为了
不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
6． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。
7． 组织待检索文件的倒排表的优点是什么？
【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名（因通常的查询是从关键字查到记录）。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。
8． 写出下面算法中带标号语句的频度。
设k 的初值等于1。
【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）
两头匹配的
语句执行n 次，所以频度是n 。
（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。
（3）这是循环体语句，共执行了n 次，所以频度是n 。
，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）
一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。
（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。
（6）这是循环体语句，共执行了n －1次，所以频度是n －1。
二、算法设计题
9． 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下：
构造的哈希表如图所示：
相关内容
相关标签