首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有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
60
问题
已知有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
学硕统考专业
相关试题推荐
论述秦国商鞅变法的内容、过程以及重要意义。
下列各组条约的时间排列顺序正确的是()。①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
屋大维的权力达到顶峰是在获得了哪一称号之后?()
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
下列关于社会大分工不正确的说法是()。
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述,不正确的是()
相对于微程序控制器,硬布线控制器的特点是()。
计算机系统中存储器为何采用分级结构?
CRT显示器显示图形图像的原理是图形图像()。
随机试题
最易导致外伤性关节脱位的是
民用建筑的供电线路,当电流超过()A时,应采用380/220V三相四制供电。
土石坝中,黏性心墙和斜墙顶部水平厚度一般不小于()m,以便于机械化施工。
砂枕坝体施工前,应根据()等绘制坝体断面砂枕布置图。
私募股权投资企业需要进行清算的情况不包括()。
依照《公司登记管理条例》规定,设立股份有限公司,应由()向公司登记机关申请设立登记。
据统计资料显示,美国的人均寿命是73.9岁,而在夏威夷出生的人的平均寿命是77岁,在路易斯安那州出生的人的平均寿命是71.7岁。因此,一个来自路易斯安那州的新婚夫妇,如果选择定居夏威夷,那么,他们的孩子的寿命,可以指望比在路易斯安那州出生的孩子要长。
a=-5是齐次方程组有非零解的()
【B1】【B3】
A、Itissignedbythestategovernment.B、Itcouldraisemoneyfromparents.C、Ithasbeendrawnuptoprotectchildren.D、Itco
最新回复
(
0
)