2017年云南财经大学算法与数据结构考研复试核心题库
● 摘要
一、应用题
1． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。
第一趟：12，23，35，16，25，36， 19，21，16， 47
第二趟：12，16，23，35，16，25，36， 19，21，47
第三趟：12，16，23，16，25，35， 19，21，36， 47
第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47
第五趟：12，16，16，19，23，25，21，35， 36， 47
第六趟：12，16，16，19，21， 23，25，35， 36， 47
第七趟：12，16，16，19，21，23，25，35， 36， 47
2． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为
小为
因为所以768和所以首址大小为互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回其伙伴地址为512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：
图2 回收后该伙伴系统的状态图
3． 设散列表为数分别为
：
注：％是求余数运算
中，函数
码序列为
（2）计算搜索成功的平均搜索长度表示颠倒十进制数x 的各位，如 即表的大小为 其等。若插入的关键
，现采用双散列法解决冲突。散列函数和再哈希函（1）试画出插入这8个关键码后的哈希表；
【答案】（1）插入这8个关键码后的哈希表如表所示：
表 插入关键字后的哈希表
（2）
4． 在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
【答案】不一定相邻。哈希地址为的关键字，和为解决冲突形成的探测序列f 的同义词，都争夺哈希地址i 。
5． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】（1）动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容
量为
则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空
（若）
，
如内存大小为
间”
或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若）。 空间。起始地址为P ，
大小为的内存块，其伙伴的起始地址为：（2）和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
6． 请求分页管理系统中，假设某进程的页表内容如下表所示:
页面大小为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 。