首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有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-08-10
66
问题
已知有31个长度不等的初始归并段,其中8段长度为2;8段长度为3;7段长度为5;5段长度为12:3段长度为20(单位均为物理块)。在最佳5-路归并方案下,则总的读/写外存的次数为( )。
选项
A、400
B、500
C、600
D、800
答案
D
解析
固定解题思路:
判断是否需要补充空归并段。如何判断?设度为O的结点有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—9所示。
从图3—9中可以算出(带有方框的结点表示原数据结点): 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/4wCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于罗马奴隶制,下列说法不正确的是()。
1950年2月14日,周恩来代表中国与苏联签订的条约是()。
三国同盟和三国协约两大军事集团最终形成的时间是()。
当甲午中日战争正在进行时,恩格斯就预言:“中日战争意味着古老中国的终结,意味着它的整个经济基础全盘地却是逐渐地革命化。”这里的“革命化”指的是()。
1946年3月5日,英国前首相丘吉尔在富尔敦发表了(),发出第一个明白无误的“冷战”信号。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
通常通信信道的带宽越大,在数据传输中失真将会()。
快速排序最易发挥其长处的情况是()。
实现一个经典的“读者一写者”算法时,若当前临界区中有读者访问,写者再来时必须在临界区外面等候,如果其后读者源源不断地到达,按策略他们均可以进入临界区,始终保持临界区中有读者访问,那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题,我们修改访问策略,
某计算机的主存地址空间大小为256MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下:假定int类型数据用32位补码表示,程序
随机试题
分布到直肠和肛管的动脉来源于()
下列哪一或哪些选项不属于人权的基本存在形式?()
项目财务分析的取价原则有()。
某服装厂厂房为一栋六层钢筋混凝土建筑物,厂房一层是裁床车间,二层是手缝和包装车间及办公室,三至六层是成衣车间。厂房一层原有4个门,后2个门被封死,1个门上锁,仅留1个门供员工上下班进出。厂房内唯一的上下楼梯平台上堆放了杂物仅留0.8m宽的通道供员工通行。半
通过公开程序,邀请供应商提供资格文件,只有通过资格审查的供应商才能参加后续招标,这种采购方式称为()。【2009年真题】
Ithinkthereareonlyafewsportsthatareboth_________and___________.
在体育教学过程中,体育教师运用队列队形要达到的基本要求是()。
《大面》又称《代面》,表现北齐兰陵王才武而貌美,常戴假面与敌作战的情景。
把下面的六个图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是:
下列对于智力发展的趋势的表述正确的是()
最新回复
(
0
)