首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有3 1个长度不等的初始归并段,其中8段长度为2;8段长度为3;7段长度为5;5段长度为12;3段长度为20(单位均为物理块)。在最佳5.路归并方案下,则总的读/写外存的次数为( )。
已知有3 1个长度不等的初始归并段,其中8段长度为2;8段长度为3;7段长度为5;5段长度为12;3段长度为20(单位均为物理块)。在最佳5.路归并方案下,则总的读/写外存的次数为( )。
admin
2022-06-07
49
问题
已知有3 1个长度不等的初始归并段,其中8段长度为2;8段长度为3;7段长度为5;5段长度为12;3段长度为20(单位均为物理块)。在最佳5.路归并方案下,则总的读/写外存的次数为( )。
选项
A、400
B、500
C、600
D、800
答案
D
解析
固定解题思路:
判断是否需要补充空归并段。如何判断?设度为0的结点有n
0
个,度为m的结点有nm个,则对严格m叉树有m
0
=(m—1)m
m
+1,由此可以得出n
m
=(n
0
—1)/m—1。
(1)如果(no—l)mod(m—l)=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/jx3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
设有一个直接映像方式的Cache,其容量为8KB,每块的大小为16B,主存的容量为512KB,试回答以下问题:将主存中的第513块调入Cache,则Cache的块号为多少?它的区号为多少?
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点u出发的最小生成树T的步骤如下:初始化U
如果文件需要采用随机存取,且文件大小不固定,则应采用()物理结构。
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们
在含有15个结点的平衡二叉树上,查找关键字为28(存在该结点)的结点,则依次比较的关键字有可能是()。
一台主机访问网站:www.pku.edu.cn的连接,请回答下列问题:(1)为了成功访问当前网站,网络中首先需要做什么?应用层的协议的查询顺序是怎样的?(2)在这一过程中,使用了哪个传输层协议和网络层协议?(3)当网络层收到一个完整的数据
下面()寻址方式处理数组问题更为方便。
利用逐点插入建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,要查找元素30要进行元素间的比较次数是()。
假设主机1(在图2-4中网络1以太网上)是可以运行IE浏览器的某客户机,主机4(在图2—4中网络3以太网上)为天勤论坛Web服务器(IP地址为202.197.11.5),主机5(在图2-4中网络2的FDDI主干网上)为天勤论坛DNS服务器,该DNS服务器上
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。集中式总线判优控制与分布式总线判优控制的区别是什么?
随机试题
下列属于公司长期资本筹集方式的有()
A.柏油样便B.暗红色便C.果酱样便D.陶土色便E.米泔水样便上消化道出血时,大便呈
患者微恶风寒、发热重、浊涕,痰稠或黄,咽喉肿痛,苔薄黄、脉浮数。治疗取大椎穴,宜采用的刺灸法是()
美国一项研究表明,二手烟雾对非烟民的危害远甚于烟民本人。吸烟的人在损害自身心血管系统的同时,系统可以进行自我调节以便于抵消吸烟造成的部分后果,而不吸烟的人的身体无法适应烟雾吸人后的变化。因此,被动吸烟对非烟民所产生的影响远远大于对烟民的影响。以下哪项如果为
期货交易所负有按交易规则规定的期限、方式,将交易的结算结果通知期货公司的义务。如果期货交易所怠于履行该义务造成期货公司损失的,应当()。
宏观经济走向包括( )。
1958年竺可桢在《中国的亚热带》一文中指出:我国亚热带北界接近34°N,即淮河、秦岭、白龙江一线直至104°E;南界横贯台湾中部和雷州半岛南部。完成以下题。我国亚热带在34°N以南、104°E以西分布范围小,主要影响因素是()。
当事人因不动产纠纷而提起行政诉讼,该案件的管辖为()。
毛泽东在《新民主主义论》中提出了新民主主义的经济纲领,保护民族工商业是其中极具特色的一项内容。保护民族工商业,发展资本主义,是由()
F
最新回复
(
0
)