2017年江西科技师范大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 证明：置换选择排序法产生的初始归并段的长度至少为m （m 是所用缓冲区的长度）。
【答案】证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，
，缓以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时（即初始归并段）
冲区中m 个元素中除最小元素之外，其他m-1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。证毕。
2． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：
（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。
（2）当n=7时，给出一个最好情况的初始排序的实例。
（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。
（4）当n=7时，给出一个最坏情况的初始排序的实例。
【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为
以此类推，
总共进行
需2次，共10次即可。
（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。
（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为
n=7时，最坏情况下的比较次数为21次。
（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。
3． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】（1）动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容
量为
则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空
（若）
，
如内存大小为
间”
或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若）。
第 2 页，共 40 页 的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各所以当空间。起始地址为P ，
大小为的内存块，其伙伴的起始地址为：
（2）和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
4． 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为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位。
第 3 页，共 40 页
（2）主存物理地址20位，从左至右应划分3个字段：标记字段、块号字段、块内地址字段。其中标记12 位，块号3位，块内地址5位。
（3）虚拟地址001C60H=0000 0000 0001 1100 0110 0000B，该虚拟地址的虚页号为001H ，查
，表明此页在主存中，页框号为04H , 对应的20位页表可以发现，虚页号1对应的有效位为“1”
物理地址是04C60H = OOOOOlOOllOOOllOOOOOB。
访问该地址时，Cache 不命中，因为Cache 采用直接映射方式，对应的物理地址应该映射到Cache 的第3行 中，其有效位为1，标记值
不命中。
（4） 虚拟地址024BACH = 000000100100101110101100B ，虚页号为024H ，TLB 中存放8个页表项，采用4路组相联，即TLB 分为2组，每组4个页表项。12位虚页号字段中最低位作为组索引，其余11位为标记位。 现在最低位为0, 表明选择第0组，11位的标记为012H ，根据标记可以知道TLB 命中，所在的页面在主存中。 因为如果在TLB 中查到了页表项，即TLB 命中，说明所在页一定命中
5． 对下面的关键字集，（物理地址高12位）故访问该地址时Cache 若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。
【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为
哈希函数，哈希函数为
（2）哈希表如表所示：
表 哈希表
（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，
当其哈希地址为时的查找次数。本例中
（4）算法如下：
第 4 页，共 40 页 用除留余数法设计 故查找失败和查找成功时的平均查找长度分别为：