首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有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
63
问题
已知有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
学硕统考专业
相关试题推荐
张居正改革期间,调任抗倭名将()镇守蓟门,对安定北方发挥了积极作用。
简述大化改新的内容和影响。
论述秦国商鞅变法的内容、过程以及重要意义。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
通常通信信道的带宽越大,在数据传输中失真将会()。
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
以下说法中,错误的是()。
一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。
随机试题
四时田园诗的集大成者是【】
AsIchangedmyplan,Iphonedthehotelto______myreservation.
简述遗嘱继承的特征。
下列选项不属于骨筋膜室产生的原因的是
甲经乙公司股东丙介绍购买乙公司矿粉,甲依约预付了100万元货款,乙公司仅交付部分矿粉,经结算欠甲50万元货款。乙公司与丙商议,由乙公司和丙以欠款人的身份向甲出具欠条。其后,乙公司未按期支付。关于丙在欠条上签名的行为,下列哪一选项是正确的?(2017年卷三9
架空电力线路导线架设程序中,立杆的紧后工序是()。
某公司某会计年度的财务数据如下:公司年初总资产为20000万元,流动资产为7500万元;年末总资产为22500万元,流动资产为8500万元;该年度营业成本为16000万元,营业毛利率为20%,总资产收益率为5%。给定上述数据,则该公司的流动资产周
反洗钱法的主要内容包括()。
在党的十六届三中全会上提出了科学的发展观,其基本内容是()。
某工业企业大量生产甲、乙两种商品。该企业采用品种法计算产品成本,适用的增值税税率为17%。2013年5月份,该企业发生的有关经济业务如下:(1)5月份开始生产甲、乙产品,当月投产甲产品270件,耗用材料4800千克;投产乙产品216件,耗用材料400
最新回复
(
0
)