2017年国防科学技术大学F0606数据结构与算法考研复试核心题库
● 摘要
一、应用题
1． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式
给出它的next 函数值及next 函数的修正值nextval 之值。
【答案】KMP 算法的时间复杂性是
01102201320。
2． S 是字符数组
，p 的next 和nextval 值分别为01112212321和请中存放的是该字符串的有效长度，
假设中字符串的内容为
说明下列程序的功能及执行结果。
【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。
3． 请回答下列关于堆（Heap ）的一些问题：
（1）堆的存储表示是顺序的还是链接的？
（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？
【答案】（1）堆的存储是顺序的。
（2）最大值元素一定是叶结点，在最下两层上。
（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下：
由于第i 层上的结点数至多是以它为根的二叉树的深度为则调用次筛选算法时总共进行的关键字比较次数不超过下式之值：
4． 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？
【答案】（1）数据类型的定义
数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整
，其操作有加、减、乘、除、型、实型、字符型等。整型值的范围（对具体机器都应有整数范围）
求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。
（2）抽象数据类型的定义
“抽象数据类型（ADT ）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部
如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。
（3）两者的不同
抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。
（4）抽象数据类型的主要特点
，而是向“科学”迈进了一步。 抽象数据类型的出现使程序设计不再是“艺术”
（5）使用抽象数据类型的好处
使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提
，而不必了解实现细节。 供接口）
5． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求
真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
6． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。
（1）试指出判别给定序列是否合法的一般规则；
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。
（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序
两头匹配的
列BAC ，使用SSXXSX 操作序列。
7． 某程序中有如下循环代码段p :
P 起始地址 为0804 8100H，对应的汇编代码和机器代码如下表所示
假设编译时变量sum 和i 分别分配在寄存器R1和R2中。常量N 在寄存器R6中，数组A 的首地址在寄存器R3中，程序段
执行上述代码的计算机M 采用32位定长指令字，其中分支指令Bne 采用如下格式，
Op 为操作码：Rs 和Rd 为寄存器编号：OFFSET 为偏移量，用补码表示。请回答下列问题，并说明理由。
（1）M 的存储器编址单位是什么？
（2）已知sll 指令实现左移功能，数组A 中每个元素占多少位？
（3）表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式，当前PC 内容为bne 指令地址，通过分析表中指令地址和bne 指令内容，推断出bne 指令的转移目标地址计算公式。
（4）若M 采用如下“按序发射、按序完成”的5级指令流水线：IF （取指）、ID （译码及
，且硬件不采取任何转发措施，分取数）、EXE （执 行）、MEM （访存）、WB （写回寄存器）
支指令的执行均引起3个时钟周期阻塞，则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1 的执行不会因为与指令5的数据相关而发生阻塞？
【答案】（1）由题可知，指令为32为即4个字节，而程序执行时是以4为间隔逐条取指令的，故可知M 的存储器是采用字节编址。
（2）32位，因为sll 中实现左移，而（R2） <<2 R4即左移两位就是乘以4，所以是
位
（3）由Bne 的指令格式可知其OFFSET 为指令的后16位，而Bne 的机器码码为1446 FFFAH，所以Bne 的OFFSET 为FFFAH 即-6。
由题可知Bne 采用相对寻址方式，故有效地址
为当前Bne 指令的地址
即而取完Bne 而PC 的值指令后
，
而要跳转到指令1的地址08048100H ，两者相差了18H 也
就是24个字节，而OFFSET 是-6, 故转移目标地址计算公式为（PC ）