第四章树与二叉树¶
答案速对¶
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| B | C | C | C | D | A | A | D | D | C |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| A | B | B | B | A | A | C | D | A | D |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| B | C | B | C | C | A | B | D | D | D |
| 31 | 32 | 33 | 34 | 35 | 36 | ||||
| A | C | B | D | B | D |
(一) 树的基本概念¶
- 【2010-05】在一棵度数为4的树 T 中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为 1 的结点，则树 T 的叶结点个数是（ ）。
A. 41
B. 82
C. 113
D. 122
解析
设度为 i 的结点数为 
，叶结点数为 
。
树中所有结点的度数之和等于边数。题目中非叶结点贡献的边数为
因此树有 122 条边。树的结点总数等于边数加 1，所以
已知非叶结点总数为
故叶结点数为
也可以直接使用公式
进行计算。
答案：B
- 【2022-04】若三叉树T有244个结点（叶结点的高度为1），则T的高度至少是（ ）。
A. 4
B. 5
C. 6
D. 7
解析
要让包含固定结点数的三叉树高度尽量小，每一层都应尽可能放满。
高度为 h 的满三叉树最多包含
个结点。
分别计算：
高度为 5 时最多只有 121 个结点，容纳不了 244 个；高度为 6 时最多可容纳 364 个，因此可以容纳 244 个。
所以最小高度为 6。
答案：C
(二) 二叉树¶
二叉树的定义及其主要特征¶
- 【2009-05】已知一棵完全二叉树的第6层（设根为第1层）有 8 个叶结点，则完全二叉树的结点个数最多是（ ）。
A. 39
B. 52
C. 111
D. 119
解析
要使结点总数最大，树应尽可能向第 7 层扩展。
如果树有第 7 层，则第 1 至第 6 层必须全部排满。第 6 层共有
个结点。
其中有 8 个是叶结点，所以其余
个结点可以拥有孩子。
为了让总数最大，这 24 个非叶结点都应有两个孩子，因此第 7 层最多有
个结点。完全二叉树要求最后一层从左向右连续排列，48 个结点满足这一要求。
第 1 至第 6 层共有
个结点，所以最多共有
个结点。
答案：C
- 【2011-04】若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A. 257
B. 258
C. 384
D. 385
解析
完全二叉树按从 1 开始的顺序编号时，编号为 i 的结点若存在左孩子，则左孩子编号为 
。
因此，编号满足
的结点是非叶结点，即
非叶结点共有
个。
叶结点数为
等价地说，完全二叉树的叶结点数为 
。
答案：C
- 【2011-06】已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（ ）。
A. 115
B. 116
C. 1895
D. 1896
解析
树转换为二叉树时采用“左孩子—右兄弟”表示法：
- 二叉树中的左孩子指针指向原树中的第一个孩子；
- 二叉树中的右孩子指针指向原树中的下一个兄弟。
在原树中，每个非叶结点的所有孩子里，最后一个孩子没有下一个兄弟，因此它在对应二叉树中没有右孩子。
原树的非叶结点数为
每个非叶结点贡献一个“最后的孩子”，所以有 1895 个这样的无右孩子结点。
此外，原树的根结点没有兄弟，在对应二叉树中也没有右孩子。因此还要加上根结点：
答案：D
- 【2018-04】设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有 k 个叶结点，则T的结点总数是（ ）。
A. 2k−1
B. 2k
C. \(k^2\)
D. \(2^k−1\)
解析
题目描述的是一棵满二叉树，也是一棵严格二叉树。设叶结点数为 
，度为 2 的结点数为 
。
二叉树中有基本关系
因此
树中没有度为 1 的结点，所以结点总数为
答案：A
二叉树的顺序存储结构和链式存储结构¶
- 【2020-03】对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（ ）。
A. 31
B. 16
C. 15
D. 10
解析
顺序存储二叉树时，若根结点编号为 1，则编号为 i 的结点：
- 左孩子编号为 ；
- 右孩子编号为
。
高度为 5 的二叉树中，最右侧路径上的结点编号依次为
虽然树只有 10 个实际结点，但“任意一棵”意味着必须考虑结点分布很稀疏、最深结点恰好位于编号 31 的位置。完全可以先用 5 个结点形成最右路径，再在其祖先的其他位置补入另外 5 个结点，所以这种情况确实存在。
数组必须能够访问下标或编号 31 对应的位置，因此至少需要 31 个存储单元。
顺序存储的空间需求取决于最大结点编号，而不只是实际结点数。
答案：A
- 【2025-03】若二叉树的节点值均为正整数，采用顺序存储方式保存在数组 R 中，用 -1 表示节点不存在，则下列数组中，不能表示一棵二叉树的是（）。
A.R[] = {20, 15, 40, -1, -1, 35}
B.R[] = {15, 40, 10, 18, 35, -1, -1}
C.R[] = {15, 40, 10, -1, -1, -1, 12}
D.R[] = {17, 20, 35, -1, 18, 45, -1, -1, 19, 27}
解析
数组下标从 0 开始时，下标 i 处结点的父结点下标为
一个非空结点若要合法存在，其父结点位置必须也非空。
A 中下标 5 的结点 35，其父结点下标为 2，对应结点 40，合法。
B 中所有非空结点的父结点均存在，合法。
C 中下标 6 的结点 12，其父结点下标为 2，对应结点 10，合法。
D 中下标 8 存放结点 19，但其父结点下标为
而下标 3 的值是 
，表示父结点不存在。没有父结点的 19 成了“悬空结点”，不能构成合法二叉树。
答案：D
二叉树的遍历¶
- 【2009-03】给定二叉树如右图所示。设 N 代表二叉树的根， L 代表根结点的左子树， R 代表根结点的右子树。若遍历后的结点序列为3, 1, 7, 5, 6, 2, 4，则其遍历方式是（ ）。
A. LRN
B. NRL
C. RLN
D. RNL
解析
题目序列从 3 开始，而 3 是根结点 1 的右子树，所以第一步是 R。
访问完右子树 3 后，序列立即出现根结点 1，所以第二步是 N。
最后处理左子树。对以 2 为根的左子树也采用 RNL：
- 先遍历 2 的右子树 5；
- 在以 5 为根的子树中，先访问右孩子 7，再访问根 5，再访问左孩子 6；
- 然后访问根 2；
- 最后访问左孩子 4。
于是完整序列为
与题目完全一致。
答案：D
- 【2011-05】若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A. 1, 2, 3, 4
B. 2, 3, 4, 1
C. 3, 2, 4, 1
D. 4, 3, 2, 1
解析
前序为 1、2、3、4，后序为 4、3、2、1，说明结点关系只能是一条单支链：
每个父结点都只有一个孩子，但这个孩子可以是左孩子，也可以是右孩子。
- 若每个孩子都是右孩子，中序为 1、2、3、4，所以 A 可能。
- 若 1 的孩子 2 是左孩子，而 2、3、4 构成右链，中序为 2、3、4、1，所以 B 可能。
- 若每个孩子都是左孩子，中序为 4、3、2、1，所以 D 可能。
检查 C：要使 1 最后访问，2 必须位于 1 的左子树。对于以 2 为根的单支链：
- 若 2 的唯一孩子在右边，中序必须先出现 2；
- 若唯一孩子在左边，中序必须先完整访问孩子子树，再出现 2，2 后面不可能再出现同一子树中的 4。
因此 3、2、4、1 无法产生。
答案：C
- 【2012-03】若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点（ ）。
A. 只有e
B. 有e、b
C. 有e、c
D. 无法确定
解析
前序遍历的第一个结点和后序遍历的最后一个结点都是根，因此根为 a。
前序中 a 后面的第一个结点 e 一定是 a 的某个孩子，并且是 a 唯一子树或左子树的根。
后序序列中，e 位于 a 之前的最后一个位置：
这说明除 a 外的所有结点 b、c、d、e 都属于以 e 为根的同一棵子树。
如果 a 还有第二个孩子，那么第二棵子树的根应在后序遍历中位于 e 与 a 之间，但这里没有任何结点。因此 a 只有一个孩子 e。
至于 e 是左孩子还是右孩子，仅凭前序和后序不能确定，但题目只问孩子结点是谁。
答案：A
- 【2015-02】先序序列为a, b, c, d的不同二叉树的个数是（ ）。
A. 13
B. 14
C. 15
D. 16
解析
给定 4 个互不相同的结点和固定先序序列后，每一种不同的二叉树形状都唯一对应一种结点安排：按照先序顺序依次把 a、b、c、d 填入该形状即可。
含 n 个结点的不同二叉树形状数为第 n 个卡特兰数：
当 
时：
答案：B
- 【2017-05】已知一棵二叉树的树形如下图所示，其后序序列为e, a, c, b, d, g, f，树中与结点a同层的结点是（ ）。
A. c
B. d
C. f
D. g
解析
根据题图形状和后序遍历“左子树—右子树—根”依次回填结点，可得到：
验证后序：
- 左子树后序为 e、a、c；
- 右子树后序为 b、d、g；
- 最后访问根 f。
合并后正是 e、a、c、b、d、g、f。
从层次看：
- 第 1 层：f；
- 第 2 层：c、g；
- 第 3 层：a、d；
- 第 4 层：e、b。
所以与 a 同层的是 d。
答案：B
- 【2017-04】要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是（ ）。
A. 只有左子树
B. 只有右子树
C. 结点的度均为1
D. 结点的度均为2
解析
先序遍历次序是
中序遍历次序是
两者唯一的差异是根与左子树的先后顺序。
如果任一非叶结点存在左子树：
- 先序会先访问该结点，再访问左子树；
- 中序会先访问左子树，再访问该结点。
两种序列必然不同。
因此所有非叶结点都不能有左子树，只能有右子树。这样先序和中序都会先访问当前根，再沿右子树继续。
“度均为 1”还可能包含只有左孩子的结点，条件不够充分。
答案：B
- 【2023-05】已知一棵二叉树的树形如下图所示，若其后序遍历为 f, d, b, e, c, a，则其先（前）序遍历序列是（ ）。
A. a, e, d, f, b, c
B. a, c, e, b, d, f
C. c, a, b, e, f, d
D. d, f, e, b, a, c
解析
答案：A
- 【2024-03】若 p、q 和 v 均为二叉树 T 中的结点，v 有两个孩子结点，T 的中序遍历序列形如“ …,p,v,q,… ”，则下列叙述中，正确的是
A. p没有右孩子，q没有左孩子
B. p没有右孩子，q有左孩子
C. p有右孩子，q没有左孩子
D. p有右孩子，q有左孩子
解析
因为 v 有左子树，中序遍历中 v 的直接前驱 p 是 v 左子树中最靠右的结点。
如果 p 还有右孩子，那么中序遍历在访问 p 后还必须访问其右子树，p 就不可能紧邻 v。因此 p 没有右孩子。
同理，v 的直接后继 q 是 v 右子树中最靠左的结点。
如果 q 还有左孩子，中序遍历必须先访问该左子树，再访问 q，q 就不可能紧邻 v。因此 q 没有左孩子。
答案：A
- 【2026-03】已知二叉树 T 的中序遍历为 b, e, d, f, c, a, g。层序遍历为 a, b, g, c, d, e, f。则其后序遍历序列为多少？
A.c, e, d, f, b, g, a
B.c, e, f, d, b, g, a
C.e, f, d, c, b, g, a
D.e, g, f, d, b, c, a
解析
层序遍历的第一个结点 a 是根。a 在中序序列中把树分成：
- 左子树：b、e、d、f、c；
- 右子树：g。
在层序序列中筛选左子树结点，最先出现的是 b，所以 b 是左子树根。b 在对应中序片段的最左端，因此 b 没有左子树，右子树包含 e、d、f、c。
继续筛选，c 最先出现，所以 c 是 b 的右孩子。c 在中序片段末尾，因此 c 只有左子树 e、d、f。
该左子树根为 d，中序中 d 左边是 e、右边是 f，所以 d 的左右孩子分别是 e、f。
后序遍历为：
- a 的左子树：e、f、d、c、b；
- a 的右子树：g；
- 根：a。
所以结果是
答案：C
线索二叉树的基本概念和构造¶
- 【2010-03】下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）
解析
这棵树的后序遍历是
后序线索化时，空左指针指向后序前驱，空右指针指向后序后继：
- b 的左指针为空，b 的前驱是 d，所以左线索指向 d；
- c 是叶结点，前驱是 b、后继是 a，所以 c 的左右线索分别指向 b、a；
- d 是第一个后序结点，左线索指向 NULL；d 的后继是 b，所以右线索指向 b；
- a 的左右指针均为真实孩子指针，不建立线索。
这与题图中的 D 一致。
答案：D
- 【2013-05】若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y 。则 X 的右线索指的是（ ）。
A. X 的父结点
B. 以 Y 为根的子树的最左下结点
C. X 的左兄弟结点 Y
D. 以 Y 为根的子树的最右下结点
解析
X 存在左兄弟 Y，说明 X 是父结点的右孩子。
后序遍历顺序是
遍历完左兄弟 Y 所在的左子树后，会遍历右子树 X。X 是叶结点，访问 X 后，父结点的两个子树都已处理完，因此下一个访问的结点就是 X 的父结点。
叶结点 X 的右指针为空，在后序线索化中应改为指向其后序后继，即父结点。
答案：A
- 【2014-04】若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分别是（ ）。
A. e、c
B. e、a
C. d、c
D. b、a
解析
中序遍历按“左子树—根—右子树”进行：
- d 的中序序列为 d、e；
- b 的左子树之后访问 b，再访问右孩子 x；
- 最后访问 a、c。
所以完整中序序列为
x 是叶结点，左右指针都为空：
- x 的中序前驱是紧邻它之前的 b，所以左线索指向 b；
- x 的中序后继是紧邻它之后的 a，所以右线索指向 a。
答案：D
(三) 树、森林¶
树的存储结构¶
森林与二叉树的转换¶
- 【2009-06】将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中， u 和 v 可能具有的关系是（ ）。
I. 父子关系
II. 兄弟关系
III. u 的父结点与 v 的父结点是兄弟关系
A. 只有II
B. I和II
C. I和III
D. I、II和III
解析
森林转换为二叉树采用“左孩子、右兄弟”规则：
- 二叉树中的左边
L：对应森林中的第一个孩子。 - 二叉树中的右边
R：对应森林中的下一个兄弟。
设二叉树中 v 的父结点为 x，题意即路径为 u → x → v。两条边各有左、右两种可能，共有四种情况：
方法一：枚举四种情况
L-L：x是u的孩子，v是x的孩子。
因此u与v是祖孙关系，不符合 I～III。L-R：x是u的第一个孩子，v是x的下一个兄弟。
所以x、v都是u的孩子，即u与v是父子关系。
I 正确。R-L：x是u的下一个兄弟，v是x的孩子。
因此u是v的父结点x的兄弟，二者属于叔侄关系，不符合 I～III。R-R：x是u的下一个兄弟，v又是x的下一个兄弟。
所以u、x、v是同一组兄弟结点。
II 正确。
方法二：快速判断
二叉树中从 u 到 v 恰好只有两条边，因此只能出现 L-L、L-R、R-L、R-R 四种情况。它们在森林中分别对应祖孙、父子、叔侄和兄弟关系。
其中没有任何一种情况能使“u 的父结点与 v 的父结点是兄弟关系”，故 III 错误。
因此，本题选择 B．I 和 II。
答案：B
- 【2014-05】将森林F转换为对应的二叉树T，F中叶子的个数等于（ ）。
A. T中叶结点的个数
B. T中度为1的结点个数
C. T中左孩子指针为空的结点个数
D. T中右孩子指针为空的结点个数
解析
在“左孩子—右兄弟”表示法中，二叉树结点的左孩子指针指向原森林中该结点的第一个孩子。
因此：
- 原森林中的结点若有孩子，其左孩子指针一定非空；
- 原森林中的结点若是叶子，没有任何孩子，其左孩子指针一定为空。
两者一一对应，所以森林叶子数等于对应二叉树中左孩子指针为空的结点数。
右孩子指针反映的是“有没有下一个兄弟”，与是否为叶子无直接对应关系。
答案：C
- 【2019-02】若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是（ ）。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
解析
树的后根遍历规则是：
- 从左到右依次遍历根的各棵子树；
- 最后访问根。
转换后的二叉树用左指针连接第一个孩子，用右指针连接后续兄弟。
对二叉树进行中序遍历时：
- 先沿左指针进入第一个孩子；
- 孩子的右兄弟链会在对应子树的遍历过程中依次得到处理；
- 所有孩子及其子树处理完成后，才访问当前根。
这与原树“先遍历各子树、后访问根”的后根遍历一致。
一个简单例子：原树根 a 有孩子 b、c。原树后根遍历为 b、c、a。转换后二叉树中 a 的左孩子是 b，b 的右孩子是 c，其中序遍历同样为 b、c、a。
答案：B
- 【2020-04】已知森林F和对应的二叉树T，若F的先根遍历序列序是a, b, c, d, e, f，后根遍历序列是b, a, d, f, e, c，则T的后序遍历序列是（ ）。
A. b, a, d, f, e, c
B. b, d, f, e, c, a
C. b, f, e, d, c, a
D. f, e, d, c, b, a
解析
- 【2021-04】某森林F对应的二叉树为T，若T的先序遍历序列是a, b, d, c, e, g, f，中序遍历序列是b, d, a, e, g, c, f，则F中树的棵数是（ ）。
A. 1
B. 2
C. 3
D. 4
解析
树和森林的遍历¶
(四) 树与二叉树的应用¶
哈夫曼(Huffman)树和哈夫曼编码¶
- 【2010-06】对 n(n≥2) 个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（ ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为 1 的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
解析
哈夫曼树的构造过程是每次选取当前权值最小的两个结点合并。
B 正确。每次合并都会产生一个拥有两个孩子的新结点，所以哈夫曼树只有度为 0 和度为 2 的结点，没有度为 1 的结点。
C 正确。最初两个最小权值一定在第一次合并时成为同一新结点的两个孩子，之后它们的兄弟关系不会改变。
D 正确。内部结点的权值是其两个孩子权值之和，并且哈夫曼合并过程使越靠近根的合并权值越大，不会小于下一层结点的权值。
A 错误。哈夫曼树一定是严格二叉树，但不一定是完全二叉树。权值分布很不均匀时，较小权值会被多次合并，树形可能明显向一侧加深，不满足完全二叉树的层序连续性。
答案：A
- 【2013-04】已知三叉树 T 中 6 个叶结点的权分别是 2,3,4,5,6,7 ， T 的带权（外部）路径长度最小是（ ）。
A. 27
B. 46
C. 54
D. 56
解析
对于严格三叉哈夫曼树，叶结点数 n 应满足
这里 
，不满足条件，所以补入一个权值为 0 的虚叶结点，使叶结点数变为 7。虚结点只用于构造，不增加 WPL。
每次合并三个最小权值：
- 合并
，得到新权值 5； - 此时权值为
，合并 
，得到 14； - 合并
，得到根权值 27。
哈夫曼树的 WPL 等于所有合并权值之和：
答案：B
- 【2014-06】5个字符有如下4种编码方案，不是前缀编码的是（ ）。
A. 01, 0000, 0001, 001, 1
B. 011, 000, 001, 010, 1
C. 000, 001, 010, 011, 100
D. 0, 100, 110, 1110, 1100
解析
前缀编码要求：任何一个字符的编码都不能是另一个字符编码的前缀。
A 中：
- 01 不会成为任何其他编码的开头；
- 001 与 0000、0001 在第三位已经不同；
- 1 也不是其他编码的前缀。
所以 A 是前缀编码。
B 中 4 个以 0 开头的编码长度都为 3，编码 1 与它们首位不同，因此也是前缀编码。
C 中所有编码等长，任一编码都不可能是另一个不同编码的前缀。
D 中存在
编码 110 是编码 1100 的前缀，因此无法进行唯一、即时译码。
答案：D
- 【2015-03】下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A. 24, 10, 5 和 24, 10, 7
B. 24, 10, 5 和 24, 12, 7
C. 24, 10, 10 和 24, 14, 11
D. 24, 10, 5 和 24, 14, 6
解析
哈夫曼树中，每个非叶结点的权值等于两个孩子权值之和。
A 中两个叶结点 5、7 若同属于权值 10 的父结点，应满足 
，但实际为 12，不可能。
B 中根的两个孩子权值为 10、12，但 
，不可能。
C 中权值为 10 的非叶结点不可能有一个权值也为 10 的孩子，因为另一个孩子权值为正时，两个孩子之和必然大于 10。
D 中合并过程为 
、
、
，完全符合哈夫曼构造规则。两条路径可以分别是 24、10、5 和 24、14、6。
答案：D
- 【2017-06】已知字符集{a, b, c, d, e, f, g, h}，若各字符的哈夫曼编码依次是0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列0100011001001011110101的译码结果是（ ）。
A. a c g a b f h
B. a d b a g b b
C. a f b e a g d
D. a f e e f g d
解析
哈夫曼编码是前缀编码，所以从左向右扫描，每遇到一个完整编码就可立即确定字符。
对编码串分段：
逐段查找：
所以译码结果为 a、f、e、e、f、g、d。
答案：D
- 【2018-05】已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是（ ）。
A. 00, 1011, 01, 1010, 11, 100
B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010
D. 0011, 10, 11, 0010, 01, 000
解析
按哈夫曼算法合并权值：
；
；- ；
；
。
由此得到各字符的编码长度：
- a，频次 6：长度 2；
- b，频次 3：长度 4；
- c，频次 8：长度 2；
- d，频次 2：长度 4；
- e，频次 10：长度 2；
- f，频次 4：长度 3。
权值越小的字符通常越深，权值较大的字符更靠近根。
A 中各字符编码长度依次为
与哈夫曼树的深度完全一致，并且该组编码满足前缀编码条件。
其他选项的编码长度分配与上述深度不符，部分还不满足前缀条件。
答案：A
- 【2019-03】对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则 n 的值是（ ）。
A. 56
B. 57
C. 58
D. 60
解析
二叉哈夫曼树没有度为 1 的结点，是严格二叉树。
设叶结点数为 n，度为 2 的内部结点数为 。严格二叉树满足
所以
总结点数为
根据题意：
答案：C
- 【2021-05】若某二叉树有5个叶结点，其权值分别为10, 12, 16, 21, 30，则其最小的带权路径长度(WPL)是（ ）。
A. 89
B. 200
C. 208
D. 289
解析
答案：B
- 【2022-05】对于任意给定的含 n(n>2) 个字符集的有限集 S ，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树T1和T2。下列叙述中，正确的是（ ）。
A. T1和T2的结点数相同
B. T1的高度大于T2的高度
C. 出现频次不同的字符在T1中处于不同的层
D. 出现频次不同的字符在T2中处于相同的层
解析
定长编码的所有字符编码长度相同，所以表示这些字符的叶结点全部位于相同层。字符出现频次不会改变其编码长度，因此 D 正确。
A 错误。哈夫曼树和定长编码树的形状通常不同，内部结点和空缺分支情况也不同，结点数不保证相同。
B 错误。哈夫曼树可能比定长编码树高，但在频次相同或树形较平衡时也可能高度相同，不能对任意字符集都断言严格大于。
C 错误。频次不同的字符也可能得到相同长度的哈夫曼编码，即位于同一层。例如两个权值不同的叶结点可能恰好处于同一深度。
答案：D
- 【2023-04】在由 6 个字符组成的字符集 S 中，各字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼编码的加权平均长度为（ ）。
A. 2.4
B. 2.5
C. 2.67
D. 2.75
解析
按哈夫曼算法合并：
；
；
；
；
。
WPL 为所有合并权值之和：
所有字符频次之和为
加权平均编码长度为
答案：B
- 【2026-05】假设二叉树中节点权值为 a=1 , b=2 , c=4 , d=5 , e=8 , f=10 , g=12 。当带权路径长度（WPL）最小时，与节点 e （权值 8）处于相同深度的节点是哪些？
A.d B.g C.d,f D.f,g
解析
按哈夫曼算法依次合并：
；- ；
；
；- 原权值 12 与新权值 12 合并为 24；
。
对应的一棵哈夫曼树为：
从根开始计算深度：
- e、f、g 都位于第 2 层深度；
- d 位于更深一层；
- c、a、b 更深。
因此与 e 同深度的是 f 和 g。
答案：D