2. 考研
  3. 已知有31个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12：3段长度为20(单位均为物理块)。在最佳5-路归并方案下，则总的读／写外存的次数为( )。

已知有31个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12：3段长度为20(单位均为物理块)。在最佳5-路归并方案下，则总的读／写外存的次数为( )。

admin2019-08-10  88
问题 已知有31个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12：3段长度为20(单位均为物理块)。在最佳5-路归并方案下，则总的读／写外存的次数为(    )。
选项 A、400
B、500
C、600
D、800
答案D
解析 固定解题思路：
    判断是否需要补充空归并段。如何判断?设度为O的结点有n0个，度为m的结点有nm个，则对严格m叉树有n0=(m一1)nm+1，由此可以得出nm=(n0—1)／m一1。    (1)如果(n0一1)mod(m一1)=0，则说明这n0个叶子结点(初始归并段)正好可以构造m叉归并树。此时，内结点有nm个。    (2)如果(n0一1)mod(m—1)=u≠0，则说明这n0个叶子结点，其中有u个结点多余，不能被包含在m叉归并树内。为了构造包含所有n0个初始归并段的m叉归并树，应在原有的nm个内结点中再增加一个内结点。它在归并树中代替了一个叶子结点的位置，被代替的叶子结点加上刚才多出的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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)