2017年大连海事大学X01数据结构考研复试核心题库
● 摘要
一、应用题
1． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有
为了
不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
2． 给出模式串
两头匹配的
在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下：
根据此定义，
可求解模式串
的next 和nextval 值如下：
3． 系统中有多个生产者进程和消费者进程，，共享用一个可以存1000个产品的缓冲区（初始为空）当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量
求写出完整的过程；并指出所用信号量的含义和初值
【答案】设置5个信号量
empty :表示缓冲区是否为空，初值为1000 full ：
表示缓冲区是否为满，初值为0
mutex 1：生产者之间的互斥信号，初值为1 mutex2：消费者之间的互斥信号，初值为1 available :当前消费者能否访问缓冲区，初值为1
定义变量in , out 分别为生产者和消费者进程所要使用的指针，指向下一个可用的缓冲区单元，
操作实现进程间的互斥和同步，要
MaXNum= 1000 为缓冲区的大小，count 标志当前消费者已经取的产品的数量，初值为0
生产者进程：
生产一个产品；
产品送入buffer （in ）;
消费者进程
取出产品buffer （out ）;
4． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
5． 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB , 主存（物理）地址空间大小为1MB , 页面大小为4KB ; Cache 采用直接映射方式，共8行；主存与Cache 之间交换的块大小为32B ，系 统运行到某一时刻时，页表的部分内容和Cache 的部分内容分别如题a 图、题b 所示：图中页框号及标记字段的内容为十六进制形式。
图
a
图b
请回答下列问题。
（1）虚拟地址共有几位，哪几位表示虚页号? 物理地址共有几位，哪几位表示页框号（物理页号）？
（2）使用物理地址访问Cache 时，物理地址应划分哪几个字段? 要求说明每个字段的位数及在物理地址中的位置。
（3）虚拟地址001C60H 所在的页面是否在主存中? 若在主存中，则该虚拟地址对应的物理地址是什么? 访问该地址时是否Cache 命中? 要求说明理由。
（4） 假定为该机配置一个4路组相联的TLB , 该TLB 共可存放8个页表项，若其当前内容 （十六进制）如题c 图所示，则此时虚拟地址024BACH 所在的页面是否在主存中? 要求说明理由。
题c 图TLB 的部分内容
【答案】（1）由于页面大小为4KB , 页内地址需要12位，所以虚拟地址24位，其中虚页号占12位；物理地址 20位，其中页框号（实页号）占8位。
（2）主存物理地址20位，从左至右应划分3个字段：标记字段、块号字段、块内地址字段。其中标记12 位，块号3位，块内地址5位。
（3）虚拟地址001C60H=0000 0000 0001 1100 0110 0000B，该虚拟地址的虚页号为001H ，查