2017年沈阳理工大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）于表示栈号，x 为入栈值。
，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）
共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：
2． 设目标为
模式为
（1）计算模式p 的nextval 函数值；
（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。 （2）利用KMP （改进的nextval ）算法，每趟匹配过程如下： 第一趟匹配：abcab （i=5, j=5） 第二趟匹配：abc （i=7，j=3） 第三趟匹配：a （i=7，j=l） 第四趟匹配：
（成功）abcabaa （i=15，j=8）
第 2 页，共 33 页
3． 简述广义表属于线性结构的理由。
【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。
4． 在改进了的（无回溯）字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。
{在模式P 中求nextval 数组的值
}
算法中第4行有
第六行中也有
两处比较语句相同。请分析说明此两处比较
语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？
【答案】第4行的
语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则
语句的意义是，当第J 个字符在模式匹配中失
指针J 和K 均増加1，继续比较。第6行的
配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K
个字符失配时的下一个（即
）。该算法在最坏情况下的时间复杂度
5． 设中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少； （2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。 【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
（关键字各字符编码之和）
五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现
：
要求用哈希（Hash ）方法将它们存入具有10个位置的表
第 3 页，共 33 页
6． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。
图 存储映像7K 意图
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】
（1）算法的基本设计思想：
①分别求出strl 和str2所指的两个链表的长度m 和n ;
②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第
个结点；若
则使q 指向链表中的第
表尾的长度相等。
③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。
（2）用C 语言算法描述如下：
两个指针同步向后移动
（3）参考答案的时间复杂度为：
或
第 4 页，共 33 页
请设计一
个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字
或JA V A 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度。
则使p 指向链
个结点，即使指针p 和q 所指的结点到
返回共同C 缀的起始点
其中m 、n 分别为两个链表的
相关内容
相关标签