首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有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
39
问题
已知有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
学硕统考专业
相关试题推荐
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时,最后一个IP分片的数据长度是()。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
(1)简述判断死锁的必要条件。(2)一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法),分析其死锁的可能性并提出解决方案。Philosopheri:d0{wait(chopstick[i];wait(ch
随机试题
利润的特点有()。
A、高嵌体B、单面嵌体C、双面嵌体D、钉嵌体E、嵌体冠涉及牙冠颊面和牙合面的嵌体称
下列律师事务所的做法中,不符合法律规定的有:
我国《拍卖法》规定,拍卖活动应当遵循()原则。
需用企业就地就近选择供应单位的好处包括()。
Abouterrorcorrection,whichofthefollowingistrueforspeakingclass?
根据我国刑事证据排除规则,犯罪嫌疑人被罚站两天后作出的无罪陈述,不能作为证据使用。()
药厂使用电动研磨器将一批晒干的中药磨成药粉。厂长决定从上午10点开始,增加若干台手工研磨器进行辅助作业。他估算如果增加2台,可在晚上8点完成,如果增加8台,可在下午6点完成。问如果希望在下午3点完成,需要增加多少台手T研磨器?()
从所给四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性。
一个虚拟存储系统由容量C1=8MB的主存和容量C2=800MB的辅存两级存储器所构成。主存每位平均代价p1=10个单位成本,辅存每位平均代价p2=1个单位成本。相对于CPU而言,从主存读出时间为tA1=500ns,从辅存读出时间为tA2=5ms。为了测定是
最新回复
(
0
)