外部排序与大规模数据处理（MapReduce/BSP）

共 21 题
#

1. k 路归并如何用最小堆在每轮选全局最小维持 O(n log k)

A O(n)
B O(n²)
C O(n k)
D O(n log k) ✓ 正确答案
#

2. 如何用外部排序思路做超大数据的中位数/Top K

A 一次全部载入内存
B 分桶定位中位数所在区间，再在桶内精确处理 ✓ 正确答案
C 随机猜测
D 使用哈希
#

3. 替换选择（replacement selection）中如何用败者树在内存中生成接近两倍内存长度的初始归并段，减少归并趟数

A 内存大小的两倍 ✓ 正确答案
B 内存大小
C 内存大小的一半
D 与内存无关
#

4. 为何内存不足以装下数据时不能简单用内部快排

A 快排不稳定
B 快排太慢
C 快排需要全部数据载入内存，超内存时无法进行 ✓ 正确答案
D 快排不能排序
#

5. 分布式排序（如 Hadoop Terasort）如何做分区+局部+归并

A 哈希分区
B 随机分区
C 单机排序
D 采样确定分区边界，使各分区覆盖有序区间 ✓ 正确答案
#

6. 外排序的 I/O 复杂度以"磁盘页传送次数"而非比较次数计

A 与 I/O 无关
B 比较次数不重要
C 页传送更简单
D 磁盘 I/O 比内存比较昂贵得多，是性能瓶颈 ✓ 正确答案
#

7. 外部排序（External Sort）为何要"分块排序+多路归并"

A 一次全量排序
B 分块排序生成有序段，再多路归并 ✓ 正确答案
C 随机访问
D 哈希分桶
#

8. 归并时如何利用"归并段已有序"做顺序 I/O 而非随机

A 顺序 ✓ 正确答案
B 随机
C 无 I/O
D 乱序
#

9. 当 k 很大时如何用"赢者树/败者树"降低归并比较次数

A O(n)
B O(log k) ✓ 正确答案
C O(k²)
D O(1)
#

10. 双缓冲与异步预读中归并时如何让磁盘读写与比较计算重叠，减少等待 I/O 的停顿

A 减少比较次数
B 增加内存占用无意义
C 让磁盘 I/O 与归并计算重叠，隐藏 I/O 延迟 ✓ 正确答案
D 避免排序
#

11. 分布式 Top-K 中精确解为何需要全局归并或分桶，近似解如何用 sketch 与误差上界交换成本

A 无需汇总
B 局部即可
C 随机选择
D 各节点局部 Top 不一定是全局 Top，需全局汇总 ✓ 正确答案
#

12. 如何用 MapReduce 做分布式外排序与多路归并

A 分区使各分区覆盖连续键区间，拼接即有序 ✓ 正确答案
B 随机分区
C 单机排序
D 哈希分区
#

13. Combiner 为何能在 map 端预聚合降低网络 shuffle 量

A 聚合函数满足结合律，可先局部合并 ✓ 正确答案
B 任意函数
C 随机聚合
D 无需满足任何性质
#

14. MapReduce 的 map/shuffle/reduce 三阶段数据流动

A 输出
B map
C reduce
D shuffle ✓ 正确答案
#

15. PageRank 在 MapReduce 上的迭代实现与收敛判定

A 固定不判断
B 随机停止
C 相邻两轮 rank 变化小于阈值 ε ✓ 正确答案
D 查看内存
#

16. Pregel（BSP）的"超步+消息传递"如何优化图计算

A 单机计算
B 每轮全量落盘
C 无消息
D 顶点状态常驻内存，消息传递避免每轮落盘 ✓ 正确答案
#

17. WordCount 如何体现"键值对"在 shuffle 按 key 聚合

A 按 value
B 按 key（单词） ✓ 正确答案
C 随机
D 按时间
#

18. 为何 MapReduce 不适合迭代图算法（每轮全量落盘）

A 不支持并行
B 图太大
C 每轮迭代中间结果全量落盘，I/O 开销巨大 ✓ 正确答案
D 无法计算
#

19. 在稀疏/稠密图上 BSP 与 MapReduce 的性能差异来源

A 无消息
B 落盘 I/O
C 消息数量巨大导致通信/内存压力 ✓ 正确答案
D 单机限制
#

20. MapReduce 的 straggler 中慢任务拖慢整体作业，推测执行与备份任务如何缓解

A 放弃任务
B 等待重试
C 推测执行（为慢任务启动备份并行） ✓ 正确答案
D 串行执行
#

21. 数据库 ORDER BY 中 sort-merge 如何利用外排序与 LIMIT 提前终止，索引扫描为何可免排序

A 索引更快读取
B 索引本身按 key 有序，扫描即可按序输出 ✓ 正确答案
C 索引自动排序
D 索引不用