首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有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
50
问题
已知有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
学硕统考专业
相关试题推荐
在一个分页存储管理系统中,地址空间分页(每页1K),物理空间分块,设主存总容量是256KB,描述主存分配情况的位示图如图6-4所示(0表示未分配,1表示已分配),此时,作业调度程序选中一个长为5.2K的作业投入内存。试回答以下问题:页式存储管理有无内
有一个文件系统如图7—2所示。其中的方框表示目录,椭圆圈表示普通文件。根目录常驻内存,目录文件组织成链接文件,不设文件控制块,普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占2B,共4B)。若下级文件是目录文件,指示其第一个磁盘块地址。若
在一个段式存储管理系统中,逻辑地址为32位,其中高16位为段号,低16位为段内偏移,以下是段表(其中的数据均为十六进制,如表7-1所示)。以下是代码段的内容:试问:x的逻辑地址为10108,它的物理地址是多少?
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求:说明你所设计算法的时间复杂度与空间复杂度。
某单位有1个总部和6个分部,各个部门都有自己的局域网。该单位申请了6个C类IP地址202.115.10.0/24~202.115.15.0/24,其中总部与分部4共用一个C类地址。网络采用R1~R7共7台路由器,采用动态路由协议OSPF,并划分了3个OSP
直接插入排序法的基本思想是:对于参加排序的原始序列(k0,1,k0,2,…,k0,n),第i趟排序将序列的第i+1个元素插入到大小为i、且已经按值有序的子序列(ki-1,1,ki-1,2,…,ki-1,i)的合适位置,得到一个大小为i+l、且仍然按值有序的
一台计算机有分离的数据和指令Cache。同时该计算机还采用了页式虚拟存储器技术。这里假定页面和(;ache块具有大小相同。已知Cache的存取速度为10ns,主存的存取速度为60ns,磁盘的存取速度为12ms。该计算机的时钟周期为10ns。如果指令
设某计算机有四个中断源,优先顺序按1→2→3→4降序排列,若1,2,3,4中断源的服务程序中对应的屏蔽字分别为11lO,0100,OllO,1111,试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求,画出CPU执行程序的轨迹
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
下列说法中错误的是()。
随机试题
施工企业的施工生产计划与建设工程项目施工进度计划属于( )的计划。
在一个图中,点表示研究的_______,线表示_______之间的关系。
在诺基亚公司,“科技以人为本”的标语随处可见,这属于企业文化的()
套期保值俗称()。
2013年6月16日13时20分左右,C钢铁集团有限责任公司大型轧钢厂发生机械伤害事故,造成1人死亡,直接经济损失约80万元。2013年6月16日7时30分,夜班调度值班长张某交班时,告诉白班调度值班长唐某说:“线材生产线打包机的2号线和4号线工作卡线,
建设工程纠纷处理的基本形式有()。
某台设备账面原值为210000元,预计净残值率为5%,预计使用年限为5年,采用双倍余额递减法计提折旧。该设备在使用3年零6个月后提前报废,报废时发生清理费用5000元,取得残值收入10000元,未计提减值准备。则该设备报废时对企业当期税前利润的影响为
下列犯罪中最高刑是无期徒刑的是( )。
已知某曲线经过点(1,1),它的切线在纵轴上的截距等于切点的横坐标,求它的方程.
YouwillhearapassagebetweenJohnandLarry,whoarediscussingthethornyissueofputtingmotivationaltechniquesintoprac
最新回复
(
0
)