Day 12　树的遍历与哈夫曼树

建议用时：22～28 分钟。请先打开今日知识卡完成复习，再独立提交本页答案。

今日学习资料

• 打开今日蓝白学习页
• 下载今日 PDF

复习目标：分清前序、中序、后序和层序遍历，会由遍历序列分析树形，并掌握哈夫曼树的合并过程与带权路径长度。

今日练习

1. 【CSP-J 2021·第 11 题】数据压缩编码中的哈夫曼编码，本质上采用（　）策略。

{{ select(1) }}

• 枚举
• 贪心
• 递归
• 动态规划

2. 【CSP-J 2022·第 7 题】字母 {a,b,c,d,e} 的出现频率依次为 10%,15%,30%,16%,29%。使用哈夫曼编码时，字母 d 的编码长度为（　）位。

{{ select(2) }}

• 1
• 2
• 2 或 3
• 3

3. 【CSP-J 2023·第 10 题】字符 {a,b,c,d,e,f} 的频率依次为 5%,9%,12%,13%,16%,45%。下列哪一组分别对应一组合法的哈夫曼编码？（　）

{{ select(3) }}

• 1111，1110，101，100，110，0
• 1010，1001，1000，011，010，00
• 000，001，010，011，10，11
• 1010，1011，110，111，00，01

4. 【CSP-J 2023·第 11 题】一棵二叉树的前序遍历为 ABDECFG，中序遍历为 DEBACFG，其后序遍历为（　）。

{{ select(4) }}

• EDBFGCA
• EDBGCFA
• DEBGFCA
• DBEGFCA

5. 【CSP-J 2024·第 12 题】已知二叉树的前序遍历为 [A,B,D,E,C,F,G]，中序遍历为 [D,B,E,A,F,C,G]，其后序遍历为（　）。

{{ select(5) }}

• DEBFGCA
• DEBFGAC
• DBEFGCA
• DEBFGAC

6. 【CSP-J 2025·第 4 题】用权值 10,12,15,20,25 构造哈夫曼树，该树的带权路径长度是（　）。

{{ select(6) }}

• 176
• 186
• 196
• 206

主题程序阅读

阅读下面的程序：

#include <iostream>
using namespace std;

int lc[7] = {0, 2, 4, 0, 0, 0, 0};
int rc[7] = {0, 3, 5, 6, 0, 0, 0};

void walk(int u) {
    if (u == 0) return;
    walk(lc[u]);
    cout << u << ' ';
    walk(rc[u]);
}

int main() {
    walk(1);
    return 0;
}

7. 若把 cout << u << ' '; 移到第一次递归调用之前，输出将变成 1 2 4 5 3 6。（判断对错）

{{ select(7) }}

• 正确
• 错误

8. 若交换 walk(lc[u]); 与 walk(rc[u]); 的位置，输出将变成 6 3 1 5 2 4。（判断对错）

{{ select(8) }}

• 正确
• 错误