🏷️ 知识点：外部排序

18 个初始归并段进行 5 路平衡归并，需要增加（ ）个虚拟归并段。

A. 1 B. 2 C. 3 D. 4

外部排序 操作系统概念

[tag_link]

正确答案：C

在5路平衡归并中，每次归并操作都需要恰好5个归并段作为输入，以确保归并过程平衡。

初始归并段数为18个，但归并过程中，每次归并会减少归并段的数量。 具体来说，每归并一次，5个归并段合并为1个新段，因此段数减少4个（即k-1，其中k=5）。

设归并次数为m，最终剩下1个归并段，则有关系式：18 - 4m = 1。 计算得m = (18-1)/4 = 17/4 = 4.25，不是整数。 这意味着如果不添加虚拟归并段，无法通过整数次归并完成，且最后一次归并可能不足5路，破坏平衡性。

为了使得归并次数为整数且每次归并都是5路，需要添加d个虚拟归并段，使总段数S’ = 18 + d，并满足(S’ - 1)能被4整除（即归并次数为整数）。 计算(18 + d - 1) = 17 + d，需使17 + d是4的倍数。 17除以4余1，因此d最小为3（因1+3=4可被4整除）。 此时S’ = 21，归并次数m = (21-1)/4 = 5，均为整数。

验证归并过程：添加3个虚拟段后，总段数21，进行5次归并，每次归并5个段（虚拟段视为空段，不影响结果），最终得到1个有序文件，符合5路平衡归并要求。 因此，需要增加3个虚拟归并段。

若对 29 个记录只进行三趟多路平衡归并，则选取的归并路数至少是（ ）。

A. 2 B. 3 C. 4 D. 5

操作系统概念 外部排序

[tag_link]

正确答案：C

在多路平衡归并中，归并趟数

$t$ 与归并路数 $k$ 、初始归并段数 $m$ 之间的关系为：经过 $t$ 趟归并，最多能处理 $k^t$ 个初始归并段，即需满足

$$k^t\ge m.$$

本题中，对 29 个记录排序，初始归并段数 $m=29$ ，要求只进行三趟归并（ $t=3$ ），因此需满足

$$k^3\ge 29.$$

计算各选项的立方：

23=8«/span>29,33=27«/span>29,43=64≥29,53=125≥29.

若 $k=3$ ，则 27«/span>29 ，需至少四趟归并，不符合“只进行三趟”的要求；

$k=4$ 时， $64\ge 29$ ，可在三趟内完成。 因此归并路数至少为 4。

对 10TB 的数据文件进行排序，应使用的方法是（）

外部排序

A. 希尔排序 B. 堆排序 C. 快速排序 D. 归并排序

[tag_link]

正确答案：D

外部排序 指待排序文件较大，内存一次性放不下，需存放在外部介质中。外部排序通常采用归并排序法。选项 A、B、C 都是内部排序的方法。

设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是（ ）。

外部排序

A. 1 B. 2 C. 3 D. 4

[tag_link]

正确答案：B

在 12 路归并树中只存在度为 0 和度为 12 的结点，设度为 0 的结点数、度为 12 的结点数和要补充的结点数分别为n0，n12，n补，则有n0 =120+n补，n0 =(12−1)n12 +1，可得n12 =(120−1+n补 )/(12−1)。由于结点数n12为整数，所以 n 补是使上式整除的最小整数，求得n补 =2，所以答案选 B。

对含有 n（n > 0）个记录的文件进行外部排序，采用置换 - 选择排序生成初始归并段时需要使用一个工作，工作区中能保存 m 个记录，请回答下列问题，

(1) 如果文件中由 19 个记录，其关键字是 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100；当 m=4 时，可以生成几个初始归并段，各是什么？

(2) 对任意的 m 个（n > m > 0），生成的第一个初始归并段的长度最大值和最小值分别是多少？

外部排序

[tag_link]

1）参考 置换选择排序，该题的关键字序列可生成 3 个初始归并段，分别是：

• 37，51，63，92，94，99
• 14，15，23，31，48，56，60，90，166
• 8，17，43，100

2）最大值为 n，最小值为 m。