题16

题16

题目

Q:【2019 统考真题】设外存上有 120 个初始归并段, 进行 12 路归并时, 为实现最佳归并, 需要补充的虚段个数是 ( ).
A. 1 B. 2 C. 3 D. 4

分析

A:注意公式：(m - 1) % (k - 1) == 0
1. 外部排序与归并:

• 理解外部排序的基本概念，明白为什么需要将大文件拆分成归并段进行处理。
• 了解归并排序的基本原理，特别是多路归并的概念和操作步骤。
  2. 最佳归并树（k 叉哈夫曼树）：
• 理解最佳归并树的定义和作用：它使用带权路径长度 (WPL) 最小的 k 叉树来指导归并顺序，以最小化磁盘 I/O 操作。
• 掌握最佳归并树的构造方法：利用贪心算法，每次合并权值最小的 k 个节点。
• 知道如何根据初始归并段数量和归并路数来判断是否需要添加虚段（权值为 0 的节点）。
  3. 虚段的作用：
• 理解为什么要添加虚段：为了将初始归并段的数量调整为可以构建严格 k 叉树的形式。
• 掌握计算虚段数量的方法：利用公式或推理，根据初始归并段数量和归并路数确定需要添加的虚段数量。
  思考步骤：

1. 明确目标： 题目要求计算出需要补充的虚段个数，以实现 12 路最佳归并。
2. 应用知识点：
   • 我们已知初始归并段数量 m = 120，归并路数 k = 12.
   • 我们需要判断 m 是否满足构建严格 k 叉树的条件。
   • 如果不满足，需要计算补充多少个虚段才能满足条件。
3. 公式或推理：
   • 公式： 判断是否需要添加虚段，可以使用公式 (m - 1) % (k - 1) == 0。 如果结果为 0，则不需要添加虚段；如果不为 0，则需要添加虚段使其满足条件。
   • 推理： 可以根据 k 叉树的性质，推导出需要添加的虚段数量。
     具体计算：
     本题中，(120 - 1) % (12 - 1) = 119 % 11 = 10 != 0, 说明需要添加虚段。
     为了使结果为 0，我们需要添加 2 个虚段，使得 (122 - 1) % (12 - 1) = 0.

解

B

• 在 12 路归并树中只存在度为 0 和度为 12 的结点
  • 设度为 0 的结点数、度为 12 的结点数和要补充的结点数分别为 和
• 则有
  • 可得
• 因为结点数 为整数
  • 所以 是使上式整除的最小整数
  • 求得
• 此外,题中为实现最佳归并,应满足 12 叉哈夫曼树
  • 不满足 的条件
  • 因此需要添加两个权值为 0 的叶结点
  • 使得
  • 才能满足条件