单选题
12.已知有3 1个长度不等的初始归并段，其中8段长度为2；8段长度为3；7段长度为5；5段长度为12；3段长度为20（单位均为物理块）。在最佳5．路归并方案下，则总的读/写外存的次数为( )。
【正确答案】
D
【答案解析】固定解题思路：
判断是否需要补充空归并段。如何判断？设度为0的结点有n0个，度为m的结点有nm个，则对严格m叉树有m0=(m—1)mm+1，由此可以得出nm=(n0—1)/m—1。
(1)如果(no—l)mod(m—l)=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—11所示。
判断是否需要补充空归并段。如何判断？设度为0的结点有n0个，度为m的结点有nm个，则对严格m叉树有m0=(m—1)mm+1，由此可以得出nm=(n0—1)/m—1。
(1)如果(no—l)mod(m—l)=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—11所示。