区用于输出,因此,可采用5路归并。归并过程如下: 450 450 450 450 450 2250 2250 4500 共做了2趟归并,每趟需要读60个磁盘页块,写出60个磁盘页块。 9-25设初始归并段为(10,15,31,∞)(9,20.∞),(22,34,37,m(6,15,42,∞),(12,37,∞),(84, 95,∞),试利用败者树进行k路归并,手工执行选择最小的5个关键码的过程。 【解答】做6路归并排序,选择最小的5个关键码的败者树如下图所示 ④输出64号段) 输出9(1号段) 输出10(0号段) 菌齿的画 15递补 20递补 15递补 输出1265号段) 输出15(4号段 ②237图84 37递补 42递补 9-26设输入文件包含以下记录:14,22,7,24,15,16,11100,10,9,20,12,90,17,13,19,2 38,30,25,50,28,110,21,40。现采用败者树生成初始归并段,请画出选择的过程 9-27给出12个初始归并段,其长度分别为30,448,6,3,20,60,18,9,62,68,85。现要做4 路外归并排序,试画出表示归并过程的最佳归并树,并计算该归并树的带权路径长度WPL 39.69.99.149.19 9.119.17 9.89.12 149239259.27 9.199.21 9.24926区用于输出，因此，可采用 5 路归并。归并过程如下： 共做了 2 趟归并，每趟需要读 60 个磁盘页块，写出 60 个磁盘页块。 9-25 设初始归并段为(10, 15, 31, ), (9, 20, ), (22, 34, 37, ), (6, 15, 42, ), (12, 37, ), (84, 95, ) , 试利用败者树进行 k 路归并，手工执行选择最小的 5 个关键码的过程。 【解答】做 6 路归并排序，选择最小的 5 个关键码的败者树如下图所示。 9-26 设输入文件包含以下记录：14, 22, 7, 24, 15, 16, 11, 100, 10, 9, 20, 12, 90, 17, 13, 19, 26, 38, 30, 25, 50, 28, 110, 21, 40。现采用败者树生成初始归并段，请画出选择的过程。 9-27 给出 12 个初始归并段，其长度分别为 30, 44, 8, 6, 3, 20, 60, 18, 9, 62, 68, 85。现要做 4 路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度 WPL。 13 9.6 9.9 9.14 9.19 9.11 9.17 9.8 9.12 9.15 14 9.23 9.25 9.27 9.19 9.21 9.24 9.26 450 450 450 450 450 450 450 450 450 450 2250 2250 4500 10 9 0 1 22 3 6 4 12 84 5 6 3 6 5 0 1 4 输出 6 (4 号段) 9 22 15 5 3 6 4 0 5 1 20 22 15 5 3 6 4 1 5 0 20 22 15 5 3 6 4 1 0 5 20 22 15 5 3 6 5 1 0 4 0 1 3 4 84 6 12 0 1 3 4 84 6 12 0 1 3 4 84 6 0 1 3 4 84 6 12 37 15 递补 10 输出 9 (1 号段) 20 递补 10 输出 10 (0 号段) 15 递补 15 输出 12 (5 号段) 37 递补 15 输出 15 (4 号段) 42 递补