2017年杭州电子科技大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式
给出它的next 函数值及next 函数的修正值nextval 之值。
【答案】KMP 算法的时间复杂性是p 的next 和nextval 值分别为01112212321和01102201320。
2． 请求分页管理系统中，假设某进程的页表内容如下表所示:
请
页面大小为4KB ，一次内存的访问时间是100ns ，一次快表（TLB ）的访问时间是10ns ，处
，进程的驻留集大小固定为2, 采理一次缺页的平均时间为108ns （已含更新TLB 和页表的时间）
用最近最少使用置换算法（LRU ）和局部淘汰策略。假设①TLB 初始为空；②地址转换时先访问TLB , 若TLB 未命中，再访问页表（忽略访问页表之后的TLB 更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列请问：
（1）依次访问上述三个虚地址，各需多少时间? 给出计算过程。
（2）基于上述访问序列，虚地址1565H 的物理地址是多少? 请说明理由。
【答案】⑴
页面大小为4KB ，因此，虚地址的低12位是页内偏移，其余高位是页号。
访问虚地址2362H , 虚页号为2，页内偏移362H 。查找TLB , TLB 初始为空，未命中，耗时10ns ; 访问页表，2号页面所在页框号为254H ，耗时100ns ; 计算得到的物理地址254362H ，访问内存，耗时100ns 。因此，总共用时
访问虚地址1565H ，虚页号为1, 页内偏移565H 。查找TLB ，未命中，耗时10ns ; 访问页表，有效位是0，未命中，耗时100m ; 产生缺页中断，进行缺页中断处理，耗时108m ; 采用LRU 置换算法，虚页1装入页帧号101H , 缺页中断处理完后，再次访问页表，命中，耗时100m ; 计算得到物理地址101565H ，再次访问内存，耗时100ns 。因此，总共用时
访问虚地址25A5H ，虚页号为2, 页内偏移5A5H 。查找TLB , 命中，耗时10ns ; 虚页2对应的页帧为254H ，因此计算得物理地址为2545A5H , 访问内存，耗时100ns 。因此，
总共用时
（2）当访问虚地址1565H 时，产生缺页中断，合法驻留集为2, 必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H 的对应的页框号为101H ，故可知虚地址1565H 的物理地址为101565H 。
3． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。
【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。
4． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的
，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）
于表示栈号，x 为入栈值。
，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）
共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：
5． 阅读下列算法，指出算法A 的功能和时间复杂性。
【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。
时间复杂度：0（n ）。
6． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。
（1）画出可利用空间表的初始状态。
（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
（3）画出在回收3个占用块之后可利用空间表的状态。
【答案】（1）因为可利用空间表的初始状态图如图1所示：
图1 可利用空间表的初始状态
（2）当用户申请大小为23的内存块时，因但没有大小为的块，只有大小为的块，
故将
的块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块再分裂成两个
大小为
的块。又将其中大小为的一块挂到可利用空间表上，
另一块再分裂成两个大小为的
块。其中一块的块挂到可利用空间表上，
另一块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块分给用户（地址0〜31）。如此下去，最后每个用户得到的存储空间的起始地址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。
图2 每个用户得到的存储空间的起始地址