2017年华东交通大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。
（1）若使用一级页表的分存储管理方式，逻辑地址结构为：
则页的大小是多少字节？页表最大占用多少字节？
（2）若使用二级页表的分存储管理方式，逻辑地址结构为：
设逻辑地址为LA ，请分别给出其对应的页目录号和表索引达式。
（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为00008000H ，其长度为8KB ，被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存0020 0000H 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。
【答案】
（1）因为页内偏移量是12位所以页大小为4KB 页表项数为页表索引可表示为：
表项，所以第8个页表项的物理地址=页表起始地
址
如下图所示。
该一级页表最大为 页表项的字节
数（2）页目录号可表示为：（3）代码页面1的逻辑地址为0000 8000H, 表明其位于第8个页处，对应页表中的第8个页
2． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。
（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述
n
【答案】
（1）6个表的合并顺序如下图所示。
个不等长升序表的合并策略，并说明理由。
对应于合并过程的哈夫曼树
根据上图中的哈夫曼树，6个序列的合并过程为：
第1次合并：表A 与表B 合并，生成含45个元素的表AB ;
第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ;
第3次合并：表D 与表E 合并，生成含110个元素的表DE ;
第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ;
第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。
由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：
第1次合并：最多比较次数= 10+35-1=44;
第2次合并：最多比较次数=45+40-1 = 84;
第3次合并：最多比较次数=50+60-1 = 109;
第4次合并：最多比较次数=85+110-1 = 194;
第5次合并：最多比较次数= 195+200-1 = 394; 比较的总次数最多为：44+84+109+194+394 = 825。
（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。
3． 请回答下列关于堆（Heap ）的一些问题：
（1）堆的存储表示是顺序的还是链接的？
（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其
具有最大值的元素可能在什么地方？
（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？
【答案】（1）堆的存储是顺序的。
（2）最大值元素一定是叶结点，在最下两层上。
（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下：
由于第i 层上的结点数至多是以它为根的二叉树的深度为则调用次筛选算法时总共进行的关键字比较次数不超过下式之值：
4． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则因且k 为整数，故k=5，即最少5-路归并完成排序。
5． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为
小为
因为所以768和所以首址大小为互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回其伙伴地址为512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：