CSP-S 2026 第一轮 第 2 题：用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树

题目

用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。

选项

• A. 108
• B. 96
• C. 99
• D. 102

答案

D

题解

选 D. 102。

哈夫曼树的构造方法是：每次选出两个最小的权值合并，把它们的和放回，再继续选择。

带权路径长度（WPL）等于每次合并产生的新权值之和，因此：

\[ WPL=3+6+9+12+15+21+36=\boxed{102} \]

这是因为每合并一次，两棵子树中所有叶子的深度都增加 1，WPL 就增加这次合并的权值之和。