2018年北京师范大学政府管理学院986软件基础数据结构考研仿真模拟五套题
● 摘要
一、应用题
1． 设某文件经内排序后得到100个初始归并段(初始顺串) ，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则，因，且k 为整数，故k=5，即最少5-路归并可以完成排序。
2． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素, 各表中元素按升序排列。要求通过5次两两合并, 将6个表最终合并成1个升序表, 并在最坏情况下比较的总次数达到最小。请回答下列问题。
(1)给出完整的合并过程, 并求出最坏情况下比较的总次数。
(2)根据你的合并过程, 描述个不等长升序表的合并策略, 并说明理由。
【答案】(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 的有序表, 最坏情况下需要比较
的总次数计算如下:
第1次合并:最多比较次数
第2次合并:最多比较次数; ;
第 2 页，共 25 页 次, 故最坏情况下比较
第3次合并:最多比较次数
第4次合并:最多比较次数
第5次合并:最多比较次数
比较的总次数最多为:; ; ; 。
(2)各表的合并策略是:在对多个有序表进行两两合并时, 若表长不同, 则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想, 依次选择最短的两个表进行合并, 可以获得最坏情况下最佳的合并效率。
3． 某请求分页系统的局部页面置换策略如下:系统从0时刻开始扫描, 每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计) , 本轮没有被访问过的页框将被系统回收, 并放入到空闲页框链尾, 其中内容在下一次被分配之前不被清空。当发生缺页时, 如果该页曾被使用过且还在空闲页框链表中, 则重新放回进程的驻留集中; 否则, 从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销, 初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P 依次访问的<虚拟页号, 访问时刻>是:
。
请回答下列问题。
(1)访问<0, 4>时, 对应的页框号是什么？
(2)访问<1, 11>时, 对应的页框号是什么? 说明理由。
(3)访问<2, 14>时, 对应的页框号是什么? 说明理由。
(4)该策略是否适合于时间局部性好的程序? 说明理由。
【答案】(1)页框号为21。因为起始驻留集为空, 而0页对应的页框为空闲链表中的第三个空闲页框, 其对应的页框号为21。
(2)页框号为32。理由:因11>10故发生第三轮扫描, 页号为1、3的页框32、15在第二轮已处于空闲页框链表中, 此刻1页又被重新访问, 因此应被重新放回到驻留集中。其页框号为32。
(3)页框号为41。理由:因为第2页从来没有被访问过, 它不在驻留集中, 因此从空闲页框链表中取出链表头的页框41, 页框号为41。
(4)适合。理由:如果程序的时间局部性越好, 从空闲页框链表中重新取回的机会越大, 该策略的优势越明显。
4． 将算术表达式转化为二叉树。
【答案】该算术表达式转化的二叉树如图所示。
第 3 页，共 25 页
图
5． 假定某计算机的CPU 主频为80MHz , CPI 为4, 并且平均每条指令访存
之间交换的块大小为168, Cache 的命中率为次, 主存与Cache , 存储器总线宽度为32位。请回答下列问题。
(1)该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下, 主存带宽至少达到多少才能满足CPU 的访存要求？
(2)假定在Cache 缺失的情况下访问主存时, 存在
式, 磁盘
少是多少？
(3)CPU和DMA 控制器同时要求使用存储器总线时, 哪个优先级更高? 为什么？
(4)为了提高性能, 主存采用4体交叉存储模式, 工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns , 则该主存能提供的最大带宽是多少？
【答案】(1)平均每秒CPU 执行的指令数为:
平均每秒Cache 缺失的次数为:
为
:。
在不考虑DMA 传输的情况下, 主存带宽至少达到
(2)平均每秒钟“缺页”异常次数为:
均每秒磁盘DMA 请求的次数至少为:
得不到及时响应,
传输数据可能会丢失。 。 次; 。 才能满足CPU 的访存要求。 , 故MIPS 数为20; 接口的数据缓冲寄存器为32位, 则磁盘的缺页率, 则CPU 平均每秒产生多少接口平均每秒发出的DMA 请求次数至次缺页异常? 若页面大小为4KB , 每次缺页都需要访问磁盘, 访问磁盘时DMA 传送采用周期挪用方当Cache 缺失时, CPU 访问主存, 主存与Cache 之间以块为单位传送数据, 此时, 主存带宽因为存储器总线宽度为32位, 所以, 每传送32位数据, 磁盘控制器发出一次DMA 请求, 故平(3)CPU和DMA 控制器同时要求使用存储器总线时, DMA 请求优先级更高; 因为若DMA 请求(4)4体交叉存储模式能提供的最大带宽为:
第 4 页，共 25 页
相关内容
相关标签