首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有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
54
问题
已知有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
学硕统考专业
相关试题推荐
古代印度的国王在种姓制度中属于()
1945年,联合国成立之时,创始会员国共有()个国家。
晋常璩所著的研究汉中和川、云、贵地方史的著作是()。
郡县制度在春秋战国时代是政治变革中最显著的一个方面,下列选项中,对郡县制度表述错误的是()
中世纪战争史上有过两次君士坦丁堡陷落,分别简述其发生的时间、征战的双方、导致的历史变动。
基督教产生的时间是()。
1946年3月5日,英国前首相丘吉尔在富尔敦发表了(),发出第一个明白无误的“冷战”信号。
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
有效容量为128KB的Cache,每块16字节,8路组相联。字节地址为1234567H的单元调入该Cache,其Tag应是()。
某计算机的主存地址空间大小为256MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下:假定int类型数据用32位补码表示,程序
随机试题
男性,40岁,风湿性心脏病史10年。近一年常有发作性夜间呼吸困难,被迫坐起、出汗、咳嗽,血压140/60mmHg,双肺有水泡音及少量哮鸣音,心脏听诊A:MDM3/6,L2、3EDM3/6向右颈部传导,胸片见心影扩大,最可能的诊断是
下列性状的粪便提示急性细菌性痢疾的是
环境现状调查的方法主要有()。
需求膨胀的具体表现是()。
前台交易人员需要的风险报告是()。
下列属于布鲁纳的认知发现学习理论的是()
【2019上】学习动机与学习效果成正比。
小王每天去体育场跑步,一位叔叔也在锻炼.两人沿400m跑道跑步,每次总是小王跑2圈时,叔叔跑了3圈.若在首次相遇后他们改为同向而跑,经过多少秒后,两人第1次同向相遇?
3,43,434,4434,44344,()
•Readthetextbelowaboutdifferentkindsofconsumergoods.•ChoosethebestwordtofilleachgapfromA,B,CorDontheo
最新回复
(
0
)