GESP 六级 · GESP 202509 C++ 六级 第 9 题

设有字符集 {a, b, c, d, e, f}，其出现频率分别为 {5, 9, 12, 13, 16, 45}。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 0，右边分支记作 1，左右互换不影响正确性）。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】哈夫曼编码｜堆（优先队列）｜贪心策略

1. 🎯 考纲定位

GESP 六级算法模块核心题型。命题人卡住的是考生对哈夫曼树构造过程的陌生——学生往往知道"频率越高编码越短"，却不会模拟合并节点、生成深度，导致对选项深度完全失准。