数据结构之外部排序题解

单项选择题

01. 设在磁盘上存放有 375000个记录，做5路平衡归并排序，内存工作区能容纳 600 个记录，为把所有记录排好序，需要做()趟归并排序。

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

答案: B

解释:

初始归并段的个数 $ r = = 625 $。
归并趟数 $ S = _5 r = _5 625 = 4 $。
第一次将 625 个归并段归并成 125 个；第二次将 125 个归并段归并成 25 个；第三次将 25 个归并段归并成 5 个；第四次将 5 个归并段归并成 1 个。

02. 设有5个初始归并段，每个归并段有 20个记录，采用5路平衡归并排序，若不采用败者树，使用传统的顺序选出最小记录(简单选择排序)的方法，总的比较次数为(①);若采用败者树最小的方法，总的比较次数约为(②)。

①: A. 20 B. 300 C. 396 D. 500
②: A. 20 B. 300 C. 396 D. 500

答案: ①: C, ②: B

解释:

① 不采用败者树时，在5个记录中选出最小的需要做4次比较。共有100个记录，需要做99次选择最小记录的操作，因此总比较次数为 $ 4 = 396 $。
② 采用败者树时，5路归并意味着败者树的外结点有5个，败者树的高度 $ h = _2 5 = 3 $。每次选择一个关键字最小的记录，比较次数不超过 $ h $，共100个记录需要的比较次数不超过 $ 100 = 300 $。

03. 置换-选择排序的作用是()。

A. 用于生成外部排序的初始归并段
B. 完成将一个磁盘文件排序成有序文件的有效的外部排序算法
C. 生成的初始归并段的长度是内存工作区的2倍
D. 对外部排序中输入/归并/输出的并行处理

答案: A

解释: 置换-选择排序是外部排序中生成初始归并段的方法。通过此方法得到的初始归并段的长度是不等长的，其长度平均是传统等长初始归并段的2倍，从而使得初始归并段数减少到原来的近二分之一。然而，置换-选择排序并不是一种完整的生成有序文件的外部排序算法。

04. 最佳归并树在外部排序中的作用是()。

A. 产生初始归并段
B. 设计 m路归并排序的优化方案
C. 与锦标赛树的作用类似
D. 对外部排序中输入/归并/输出的并行处理

答案: B

解释: 最佳归并树在外部排序中的作用是设计m路归并排序的优化方案。仿照构造哈夫曼树的方法，以初始归并段的长度为权值，构造具有最小带权路径长度的m路哈夫曼树，可以有效地减少归并过程中的读写记录数，加快外部排序的速度。

05. 在下列关于外部排序过程输入/输出缓冲区作用的叙述中，不正确的是()。

A. 暂存输入/输出记录
B. 内部归并的工作区
C. 产生初始归并段的工作区
D. 传送用户界面的消息

答案: D

解释: 在外部排序过程中，输入/输出缓冲区的主要作用是暂存输入/输出记录，作为内部归并的工作区，并可用于产生初始归并段。因此，选项D是不正确的，因为输入/输出缓冲区并不涉及传送用户界面的消息。

06. 在做 m 路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置( ①)个输入缓冲区和(②)个输出缓冲区。

①: A. 2 B. m C. 2m-1 D. 2m
②: A. 1 B. 2 C. 54 D. 12

答案: ①: D, ②: A

解释: 在做m路平衡归并排序时，为了实现输入/内部归并/输出的并行处理，通常需要设置 $ 2m $ 个输入缓冲区和 1 个输出缓冲区。这样可以在执行内部归并的同时进行输入和输出操作。

07. 【2013 统考真题】已知三叉树T中6个叶结点的权分别是2,3,4,5,6,7，T的带权(外部)路径长度最小是()。

A. 27
B. 46
C. 56
D. 60

答案: B

解释: 将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需要添加权为0的虚叶结点。根据带权路径长度的计算，最小的带权路径长度为 $ (2+3) + (4+5) + (6+7) = 46 $。

08. 【2019统考真题】设外存上有 120个初始归并段，进行 12路归并时，为实现最佳归并需要补充的虚段个数是()。

A. 1
B. 2
C. 54
D. 12

答案: B

解释: 在12路归并树中只存在度为0和度为12的结点。设度为0的结点数、度为12的结点数和要补充的结点数分别为 $ n_0, n_{12}, n_补 $，可以得到方程 $ n_0 = 120 + n_补 $，和 $ n_0 = (12-1)n_{12} + 1 $。由此推导得 $ n = $，通过求解可以得到 $ n_补 = 2 $，因此答案为B。

综合题

多路平衡归并排序是外部排序的主要方法，试问多路平衡归并排序包括哪两个相对独立的阶段?每个阶段完成何种工作?

多路平衡归并排序由两个相对独立的阶段组成：

生成初始归并段阶段：
- 工作内容：根据内存工作区的大小，将有 $ n $ 个记录的磁盘文件分批输入内存。然后，采用有效的内部排序方法（如快速排序、归并排序或堆排序）对这些输入的记录进行排序，生成若干有序的子文件，这些有序的子文件被称为初始归并段。
多趟归并排序阶段：
- 工作内容：在这一阶段，采用多路归并方法对之前生成的初始归并段逐趟进行归并，最终将所有的有序子文件合并成一个完整的有序文件。该阶段通过合理的输入/输出管理和内存使用，确保排序效率。

若某个文件经内部排序得到80个初始归并段，试问:

若使用多路平衡归并执行3趟完成排序，则应取得的归并路数至少应为多少?
若操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序?若限定趟数，可取的最低路数是多少?
归并路数计算：
- 设归并路数为 $ m $，初始归并段个数 $ r = 80 $。根据归并趟数计算公式：$ S = _m r = 3 $
- 由此得出： $ _m 80 < 3 $
- 转化为指数形式： $ 80 < m^3 $
- 解得： $ m > $
- 因此，应取的归并路数至少为 5。
操作系统限制：
- 设多路归并的归并路数为 $ m $。需要 $ m $ 个输入缓冲区和 1 个输出缓冲区，因此一个缓冲区对应一个文件，总数为 $ m + 1 $。
- 根据操作系统要求： $ m + 1 m $
- 由此可以进行 14 路归并。接着计算所需的趟数： $ S = {m} 80 = {14} 80 $
- 所以至少需要 2 趟归并完成排序。
- 若限定趟数为 2，依据公式： $ S = _{m} 80 = 2 m^2 $
- 解得： $ m $
- 因此，进行 9 路归并排序即可。

假设文件有 4500 个记录，在磁盘上每个块可放 75 个记录。计算机中用于排序的内存区可容纳 450 个记录。试问:

可以建立多少个初始归并段? 每个初始归并段有多少记录? 存放于多少个块中?
应采用几路归并? 请写出归并过程及每趟需要读写磁盘的块数。
初始归并段的计算：
- 文件总记录数为 4500 个。
- 内存区可容纳 450 个记录，因此可以建立的初始归并段数量为： $ = = 10 $
- 每个初始归并段有 450 个记录，存放于多少个块中计算如下：
  - 每个块可放 75 个记录，因此每个初始归并段需要的块数为： $ = = 6 $
- 所以，建立了 10 个初始归并段，每个初始归并段有 450 个记录，存放于 6 个块中。
路归并的计算：
- 内存区可容纳 450 个记录，相当于 6 个块（因为每个块可放 75 个记录）。
- 可以建立 6 个缓冲区，其中 5 个用于输入，1 个用于输出，因此可以采用 5 路归并。