首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有31个长度不等的初始归并段,其中8段长度为2;8段长度为3;7段长度为5;5段长度为12;3段长度为20(单位均为物理块)。在最佳5-路归并方案下,则总的读/写外存的次数为( )。
已知有31个长度不等的初始归并段,其中8段长度为2;8段长度为3;7段长度为5;5段长度为12;3段长度为20(单位均为物理块)。在最佳5-路归并方案下,则总的读/写外存的次数为( )。
admin
2019-12-10
40
问题
已知有31个长度不等的初始归并段,其中8段长度为2;8段长度为3;7段长度为5;5段长度为12;3段长度为20(单位均为物理块)。在最佳5-路归并方案下,则总的读/写外存的次数为( )。
选项
A、400
B、500
C、600
D、800
答案
D
解析
判断是否需要补充空归并段。如何判断?设度为0的结点有n
0
个,度为m的结点有n
m
个,则对严格m叉树有n
0
=(m-1)n
m
+1,由此可以得出n
m
=(n
0
-1)/m-1。
(1)如果(n
0
-1)mod(m-1)=0,则说明这n
0
个叶子结点(初始归并段)正好可以构造m叉归并树。此时,内结点有n
m
个。
(2)如果(n
0
-1)mod(m-1)=u≠0,则说明这n
0
个叶子结点,其中有u个结点多余,不能被包含在m叉归并树内。为了构造包含所有n
0
个初始归并段的m叉归并树,应在原有的n
m
个内结点中再增加一个内结点。它在归并树中代替了一个叶子结点的位置,被代替的叶子结点加上刚才多出的u个叶子结点,再加上m-u-1个空归并段,就可以建立归并树。
按照以上步骤:因为(31-1)mod(5-1)≠0,所以需要增设空归并段。需要增设5-2-1=2个空归并段。接下来就比较简单了,仿造赫夫曼树的构造方法,来构造5-路最佳归并树,如图3-11所示。
从图3-11中可以算出(带有方框的结点表示原数据结点):
WPL=(2×8+3×8+5×2)×3+(5×5+12×5+20×1)×2+20×2=400
则总的读/写外存的次数为:400×2=800。
转载请注明原文地址:https://kaotiyun.com/show/Db3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
在操作系统中,P,V操作是一种()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
随机试题
焊缝中的氧有哪些危害?
下列关于I/O设备的叙述,错误的是________。
岛叶外侧是
某外商独资企业因经营期满而进入清算,清算组从成立至清算终结前实施的哪些行为是违法的?()
食品营养标签制作的第一个环节是食品样品的收集和处理。
请认真阅读下列材料,并按要求作答。请根据上述材料完成下列任务:说一说马蒂斯的作品给你的印象是什么?(10分)
执行如下SQL语句后SELECT*FROMstockINTODBFstockORDER8Y单价有如下SQL语句CREATEVIEWstockviewASSELECT*FROMstockWHERE交易所="深
ASuccessStoryAt19,BenWayisalreadyamillionaire,andoneofagrowingnumberofteenagerswhohave【C1】______theirfo
WetsuitAwetsuitis【T1】______whowantto【T2】______.Wetsuitsareusuallywornbyswimmers,divers,or【T3】______.Wetsuitsh
Followingthepatternshowninthenumbersequencebelow,whatisthemissingnumber?1827?125216
最新回复
(
0
)