408 真题做题本·数据结构部分

第 4 章 树与二叉树

4.1 树的基本概念

1. 【2010】在一棵度为4 的树T 中，若有20 个度为4 的结点, 10 个度为3 的结点, 1 个度为2 的结点,10 个度为1 的结点，则树T 的叶结点个数是（ ）。

A. 41
B. 82
C. 113
D. 122

答案： B

解析：

设度为 $i$ 的结点数为 $n_i$，叶结点数为 $n_0$。树中结点总数为

$$n=n_0+n_1+n_2+n_3+n_4.$$

树的边数一方面为 $n-1$，另一方面等于所有结点度数之和，因此

$$n-1=n_1+2n_2+3n_3+4n_4.$$

两式相减可得树中叶结点数公式

$$n_0=1+\sum _{i=1}^4(i-1)n_i.$$

代入已知数据：

$$n_0=1+(2-1)\times 1+(3-1)\times 10+(4-1)\times 20=82.$$

故选 B。

2. 【2022】若三叉树T 中有244 个结点(叶结点的高度为1)，则T 的高度至少是（ ）。

A. 8
B. 7
C. 6
D. 5

答案： C

解析：

高度为 $h$ 的三叉树在每一层结点数都达到最大时，结点总数最多为

$$1+3+3^2+\cdots +3^{h-1}=\frac{3^h-1}{2}.$$

为了使244个结点所需的高度最小，应尽可能将前面各层填满。

当 $h=5$ 时，最多有

$$\frac{3^5-1}{2}=121$$

个结点，不足244个；当 $h=6$ 时，最多有

$$\frac{3^6-1}{2}=364$$

个结点，可以容纳244个结点。因此高度至少为6，选 C。

4.2 二叉树基础

1. 【2009】已知一棵完全二叉树的第6 层(设根为第1 层) 有8 个叶结点，则该完全二叉树的结点个数最多是（ ）。

A. 39
B. 52
C. 111
D. 119

答案： C

解析：

完全二叉树第6层最多有

$$2^{6-1}=32$$

个结点。若第6层有8个叶结点，为使整棵树的结点总数最多，应使第6层的其余

$$32-8=24$$

个结点都具有两个孩子。

因此第7层最多有

$$24\times 2=48$$

个结点。前6层全部填满时共有

$$1+2+4+8+16+32=63$$

个结点，所以结点总数最多为

$$63+48=111.$$

故选 C。

2. 【2011】若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是（ ）。

A. 257
B. 258
C. 384
D. 385

答案： C

解析：

完全二叉树采用从1开始的顺序编号时，编号为

$$\lfloor \frac{n}{2}\rfloor +1,\dots ,n$$

的结点均为叶结点。因此叶结点数为

$$n-\lfloor \frac{n}{2}\rfloor =\lceil \frac{n}{2}\rceil .$$

当 $n=768$ 时，

$$n_0=\frac{768}{2}=384.$$

故选 C。

3. 【2011】已知一棵有2011 个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是（ ）。

A. 115
B. 116
C. 1895
D. 1896

答案： D

解析：

树转换为二叉树时采用“左孩子—右兄弟”表示法：

• 二叉树中的左指针指向原树结点的第一个孩子；
• 二叉树中的右指针指向原树结点的下一个兄弟。

原树中每个非叶结点的孩子序列里，最后一个孩子都没有右兄弟，因此每个非叶结点对应一个“无右孩子”的孩子结点。此外，原树的根结点也没有右兄弟。

原树中非叶结点数为

$$2011-116=1895.$$

故对应二叉树中无右孩子的结点数为

$$1895+1=1896.$$

故选 D。

4. 【2018】设一棵非空完全二叉树T 的所有叶结点均位于同一层, 且每个非叶结点都有2 个子结点。若T 有k 个叶结点，则T 的结点总数是（ ）。

A. $2k-1$
B. $2^k-1$
C. $2^k$
D. $k^2$

答案： A

解析：

题目所述二叉树中，每个非叶结点都有两个孩子，因此它是一棵满二叉树。设度为2的结点数为 $n_2$，叶结点数为 $n_0=k$。

任意非空二叉树均满足

$$n_0=n_2+1.$$

于是

$$n_2=k-1.$$

结点总数为

$$n=n_0+n_2=k+(k-1)=2k-1.$$

故选 A。

5. 【2020】对任意高度为5 且有10 个结点的二叉树,若采用顺序存储结构保存,每个结点占1 个存储单元(仅存放结点的数据信息)，则存放该二叉树需存储单元数量至少是（ ）。

A. 31
B. 16
C. 15
D. 10

答案： B

解析：

二叉树采用顺序存储时，根结点编号为1，编号为 $i$ 的结点的左、右孩子编号分别为 $2i$ 和 $2i+1$。

高度为5说明至少有一个结点位于第5层。第5层最靠左结点的编号为

$$2^{5-1}=16.$$

因此，不论树形如何，存储数组至少必须开到第16号存储单元。

该下界可以达到。例如取结点编号集合

$$\{1,2,3,4,5,6,7,8,9,16\},$$

其中每个非根结点的双亲均存在，且结点16位于第5层。故至少需要16个存储单元，选 B。

6. 【2016】如果一棵非空 $k(k\ge 2)$ 叉树T 中每个非叶结点都有k 个孩子，则称T 为正则k 叉树, 回答下列问题并给出推导过程:

(1) 若T 有m 个非叶结点，则T 中的叶结点有多少个？

(2) 若T 的高度为h(单结点的树h = 1)，则T 的结点数最多为多少个? 最少为多少个?

答案：

(1) 叶结点数为 $(k-1)m+1$。

(2) 结点数最多为 $\frac{k^h-1}{k-1}$，最少为 $k(h-1)+1$。

解析：

设叶结点数为 $n_0$，非叶结点数为 $m$，结点总数为

$$n=m+n_0.$$

由于每个非叶结点都有 $k$ 个孩子，树中边数为 $km$；另一方面，非空树的边数为 $n-1$，故

$$km=n-1=m+n_0-1.$$

整理得

$$n_0=(k-1)m+1.$$

对于第(2)问：

当每一层都达到最大结点数时，第 $i$ 层有 $k^{i-1}$ 个结点，因此结点总数最大为

$$n_{\max }=1+k+k^2+\cdots +k^{h-1}=\frac{k^h-1}{k-1}.$$

要使高度为 $h$ 时结点数最少，应使从第1层到第 $h-1$ 层每层只有一个非叶结点继续向下延伸。此时共有 $h-1$ 个非叶结点，故

$$n_{\min }=k(h-1)+1.$$

当 $h=1$ 时，两式均给出1，与单结点树相符。

4.3 二叉树的遍历

1. 【2009】给定二叉树如右图所示。设N 表示二叉树的根, L 表示根结点的左子树, R 表示根结点的右子树。若遍历后的结点序列是3,1,7,5,6,2, 4，则其遍历方式是（ ）。

A. LRN
B. NRL
C. RLN
D. RNL

答案： D

解析：

按 RNL，即“右子树—根结点—左子树”的次序遍历：

• 先遍历根结点1的右子树，得到3；
• 再访问根结点1；
• 最后按 RNL 遍历左子树。以2为根的左子树中，先遍历右子树5，得到 $7,5,6$，再访问2，最后访问其左孩子4。

因此完整序列为

$$3,1,7,5,6,2,4,$$

与题目相同，故选 D。

2. 【2011】若一棵二叉树的先序遍历序列和后序遍历序列分别为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

答案： C

解析：

先序序列为 $1,2,3,4$，后序序列为 $4,3,2,1$，说明每个非叶结点都只有一个孩子，整棵树是一条由 $1,2,3,4$ 依次连接而成的链。每条边都可以选择连接为左孩子或右孩子。

• A：所有结点均只有右孩子时，中序为 $1,2,3,4$；
• B：1只有左孩子2，而2、3均只有右孩子时，中序为 $2,3,4,1$；
• D：所有结点均只有左孩子时，中序为 $4,3,2,1$。

若中序为 $3,2,4,1$，则在以2为根的子树中，3应位于2的左侧而4位于2的右侧，这要求2同时具有左、右两个孩子，与整棵树为单支链矛盾。因此 C 不可能。

3. 【2012】若一棵二叉树的先序遍历序列为aebdc, 后序遍历序列为bcdea，则根结点的孩子结点是（ ）。

A. 只有e
B. 有e、b
C. 有e、c
D. 无法确定

答案： A

解析：

先序遍历的第一个结点和后序遍历的最后一个结点均为根结点 $a$。

先序序列中，根结点后第一个结点为 $e$，故 $e$ 必是 $a$ 的某个孩子。后序序列去掉根结点 $a$ 后为

$$b,c,d,e,$$

其中最后一个结点 $e$ 是整个非根子树的根。这说明除 $a$ 外的所有结点都位于以 $e$ 为根的同一棵子树中，因此根结点 $a$ 只有一个孩子 $e$。

故选 A。

4. 【2015】先序序列为a,b,c,d 的不同二叉树的个数是（ ）。

A. 13
B. 14
C. 15
D. 16

答案： B

解析：

给定 $n$ 个互不相同结点的先序序列后，每一种不同的二叉树形态都唯一确定一棵二叉树。含 $n$ 个结点的不同二叉树形态数为第 $n$ 个卡特兰数

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right).$$

当 $n=4$ 时，

$$C_4=\frac{1}{5}\left(\genfrac{}{}{0ex}{}{8}{4}\right)=14.$$

故选 B。

5. 【2017】要使一棵非空二叉树的先序序列与中序序列相同, 所有非叶结点须满足的条件是（ ）。

A. 只有左子树
B. 只有右子树

C. 结点的度均为1
D. 结点的度均为2

答案： B

解析：

先序遍历顺序为“根—左—右”，中序遍历顺序为“左—根—右”。若某个结点存在非空左子树，则中序遍历会先访问左子树，而先序遍历会先访问该结点，两种序列在此处必不相同。

因此每个非叶结点都不能有左子树，只能有右子树。此时两种遍历均按从根到右孩子的顺序访问结点，序列相同。

故选 B。选项 C 只要求度为1，但该唯一孩子仍可能是左孩子，条件不充分。

6. 【2017】已知一棵二叉树的树形如右图所示,其后序序列为eacbdgf,树中与结点a 同层的结点是（ ）。

A. c
B. d
C. f
D. g

答案： B

解析：

后序遍历顺序为“左子树—右子树—根”。根据图中的树形分割序列：

• 整棵树根结点为后序序列最后的 $f$；
• 左子树对应序列 $e,a,c$，故左子树根为 $c$；其中 $a$ 的孩子为 $e$；
• 右子树对应序列 $b,d,g$，故右子树根为 $g$；其中 $d$ 的孩子为 $b$。

结点 $a$ 与结点 $d$ 都位于从根结点向下的第3层，因此同层结点为 $d$，选 B。

7. 【2022】若结点p 与q 在二叉树T 的中序遍历序列中相邻, 且p 在q 之前，则下列p 与q 的关系中,不可能的是（ ）。

I. q 是p 的双亲 II. q 是p 的右孩子 III. q 是p 的右兄弟 IV. q 是p 的双亲的双亲

A. 仅I
B. 仅III

C. 仅II、III
D. 仅II、IV

答案： B

解析：

逐项判断：

• I 可以发生。若 $p$ 是 $q$ 左子树中最右下的结点，则中序遍历访问 $p$ 后立即访问 $q$。
• II 可以发生。若 $q$ 是 $p$ 的右孩子且 $q$ 没有左子树，则访问 $p$ 后立即访问 $q$。
• III 不可能。若 $p$ 与 $q$ 是兄弟，且 $p$ 为左孩子、$q$ 为右孩子，则中序遍历在完成 $p$ 所在左子树后，必须先访问二者的双亲，再进入 $q$ 所在右子树，所以 $p$ 与 $q$ 不可能相邻。
• IV 可以发生。例如 $q$ 的左孩子的右孩子为 $p$，且 $p$ 无右子树，则中序遍历可在访问 $p$ 后立即访问其祖父 $q$。

因此仅 III 不可能，选 B。

8. 【2023】已知一棵二叉树的树形如右图所示，若其后序遍历序列为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

解析：

后序序列最后一个结点为根，因此根结点是 $a$。根据给定树形：

• 根的右子树只有一个结点，所以该结点为 $c$；
• 根的左子树后序序列为 $f,d,b,e$，故左子树根为 $e$；
• $e$ 的左子树后序序列为 $f,d$，故其根为 $d$，$d$ 的孩子为 $f$；
• $e$ 的右孩子为 $b$。

因此按“根—左—右”进行先序遍历，得到

$$a,e,d,f,b,c.$$

故选 A。

9. 【2024】若p,q,v 均为二叉树T 中的结点, v 有两个孩子结点, T 的中序遍历序列形如:"..., p, v, q,..."，则下列叙述中, 正确的是（ ）。

A. p 没有右孩子, q 没有左孩子

B. p 没有右孩子, q 有左孩子

C. p 有右孩子, q 没有左孩子

D. p 有右孩子, q 有左孩子

答案： A

解析：

结点 $v$ 有左、右两个孩子。中序遍历顺序为“左子树—根—右子树”。

在序列中紧邻 $v$ 且位于其前面的结点 $p$，必是 $v$ 左子树中最后被访问的结点，即左子树中最右下的结点。因此 $p$ 不可能还有右孩子，否则还应继续访问其右子树中的结点。

同理，紧邻 $v$ 且位于其后面的结点 $q$，必是 $v$ 右子树中最先被访问的结点，即右子树中最左下的结点。因此 $q$ 不可能还有左孩子。

故选 A。

10. 【2017】设计算法,将给定的表达式树(二叉树) 转换为等价的中缀表达式(通过括号反映操作符的计算次序) 并输出。例如, 当下列两棵表达式树作为输入时, 输出的等价中缀表达式分别为a+b* c* -d 和a*b + - c-d 。二叉树结点定义如下:

C

typedef struct node {
    char data[10];          // 存储操作数或操作符
    struct node *left;      // 指向左子树
    struct node *right;     // 指向右子树
} BTree;

要求:

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用C 或C++ 语言描述算法，关键之处给出注释。

答案：

(1) 对表达式树进行中序遍历。访问非叶结点所代表的子表达式时，除整棵树的根结点外，在该子表达式的左右分别输出左、右括号；叶结点直接输出操作数。这样可由括号明确表达式树规定的运算次序。

(2) 算法如下：

C

#include <stdio.h>

typedef struct node {
    char data[10];
    struct node *left;
    struct node *right;
} BTree;

/*
 * t：当前结点
 * depth：当前结点深度，根结点深度为0
 */
void PrintInfix(BTree *t, int depth) {
    if (t == NULL)
        return;

    /* 有孩子的结点表示运算符，即当前是一棵子表达式树 */
    int isOperator = (t->left != NULL || t->right != NULL);

    /* 除整棵表达式树的根外，运算符子树外加括号 */
    if (isOperator && depth > 0)
        printf("(");

    /* 中序遍历左子树 */
    PrintInfix(t->left, depth + 1);

    /* 输出当前操作数或操作符 */
    printf("%s", t->data);

    /* 中序遍历右子树；一元运算符只有一个孩子时也适用 */
    PrintInfix(t->right, depth + 1);

    if (isOperator && depth > 0)
        printf(")");
}

void PrintExpression(BTree *root) {
    PrintInfix(root, 0);
}

解析：

表达式树的叶结点是操作数，非叶结点是操作符。中序遍历天然按照“左操作数—操作符—右操作数”的顺序输出，但仅做普通中序遍历会丢失树中规定的结合次序，因此需要对子表达式加括号。

例如，图(a)可输出为

Text

(a+b)*(c*(-d))

图(b)可输出为

Text

(a*b)+(-(c-d))

算法对每个结点只访问一次，时间复杂度为 $O(n)$；递归栈的空间复杂度为 $O(h)$，其中 $h$ 为树高。

4.4 线索二叉树

1. 【2010】下列线索二叉树中(虚线表示线索), 符合后序线索树定义的是（ ）。

答案： D

解析：

图中实线所示二叉树的结构为：根结点 $a$ 的左、右孩子分别为 $b,c$，结点 $b$ 的右孩子为 $d$。其后序遍历序列为

$$d,b,c,a.$$

后序线索化时，空左指针指向该结点的后序前驱，空右指针指向该结点的后序后继：

• $d$ 的前驱为空，后继为 $b$；
• $b$ 的空左指针指向前驱 $d$；
• $c$ 的前驱为 $b$，后继为 $a$；
• $a$ 的左右指针均为真实孩子指针。

只有图 D 中的线索关系与上述关系一致。

2. 【2013】X 是后序线索二叉树的叶结点, 且X 存在左兄弟结点Y，则X 右线索指向（ ）。

A. X 的父结点
B. Y 为根的子树的最左下结点

C. X 的左兄弟结点Y
D. Y 为根的子树的最右下结点

答案： A

解析：

结点 $X$ 有左兄弟 $Y$，说明 $X$ 是其双亲的右孩子。后序遍历顺序为“左子树—右子树—根”。完成右子树中叶结点 $X$ 的访问后，下一步就访问它们的双亲结点。

因此 $X$ 的后序后继是其父结点，而叶结点 $X$ 的右指针为空，后序线索化后其右线索指向父结点。故选 A。

3. 【2014】若对如右图的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是（ ）。

A. e、c
B. e、a
C. d、c
D. b、a

答案： D

解析：

由图可得二叉树的中序遍历序列为

$$d,e,b,x,a,c.$$

结点 $x$ 是叶结点，其左、右指针均为空。中序线索化后：

• 左线索指向其中序前驱 $b$；
• 右线索指向其中序后继 $a$。

故选 D。

4.5 树与森林

1. 【2009】将森林转换为对应的二叉树，若在二叉树中, 结点u 是结点v 的父结点的父结点，则在原来的森林中, u 和v 可能具有的关系是（ ）。

I. 父子关系 II. 兄弟关系 III. u 的父结点与v 的父结点是兄弟关系

A. 只有II
B. I 和II

C. I 和III
D. I、II 和III

答案： B

解析：

森林转换为二叉树时，左指针表示“第一个孩子”，右指针表示“下一个兄弟”。若二叉树中从 $u$ 到 $v$ 恰好经过两条向下的边，则可能有以下情况：

• 先沿左指针，再沿右指针：先到 $u$ 的第一个孩子，再到该孩子的兄弟，因此 $v$ 仍是 $u$ 的孩子，$u,v$ 为父子关系，即 I 可能；
• 连续沿两次右指针：$v$ 是 $u$ 后面的兄弟，因此 II 可能；
• 先沿左指针再沿左指针时，$u,v$ 是祖孙关系；
• 先沿右指针再沿左指针时，$v$ 是 $u$ 的兄弟的孩子，不能得到 III 所述关系。

因此可能的是 I 和 II，选 B。

2. 【2014】将森林F 转换为对应的二叉树T,F 中叶结点的个数等于（ ）。

A. T 中叶结点的个数

B. T 中度为1 的结点个数

C. T 中左孩子指针为空的结点个数

D. T 中右孩子指针为空的结点个数

答案： C

解析：

在“左孩子—右兄弟”表示法中，二叉树结点的左孩子指针指向原森林中该结点的第一个孩子。

因此，原森林中的叶结点没有孩子，当且仅当其在对应二叉树中的左孩子指针为空。故森林 $F$ 的叶结点数等于二叉树 $T$ 中左孩子指针为空的结点数，选 C。

3. 【2019】若将一棵树T 转化为对应的二叉树BT，则下列对BT 的遍历中, 其遍历序列与T 的后根遍历序列相同的是（ ）。

A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历

答案： B

解析：

树转换为二叉树后：

• 树的先根遍历序列与对应二叉树的先序遍历序列相同；
• 树的后根遍历序列与对应二叉树的中序遍历序列相同。

原因是树的后根遍历要求先依次访问所有孩子子树，最后访问根；在左孩子—右兄弟二叉树中，中序遍历先访问左孩子及其右兄弟链所表示的全部孩子子树，最后访问根。

故选 B。

4. 【2020】已知森林F 及与之对应的二叉树T，若F 的先根遍历序列是abcdef, 后根遍历序列是 badfec，则T 的后根遍历序列是（ ）。

A. badfec
B. bdfeca

C. bfedca
D. fedcba

答案： C

解析：

森林的先根遍历等于对应二叉树的先序遍历，森林的后根遍历等于对应二叉树的中序遍历。因此二叉树 $T$ 的

$$\text{先序序列}=abcdef,$$ $$\text{中序序列}=badfec.$$

由先序和中序序列重建二叉树：

• 根为 $a$，左子树只有 $b$；
• 右子树根为 $c$；
• $c$ 的左子树根为 $d$；
• $d$ 的右子树根为 $e$，$e$ 的左孩子为 $f$。

由此得到二叉树后序序列

$$b,f,e,d,c,a.$$

即 bfedca，故选 C。

5. 【2021】某森林F 对应的二叉树为T，若T 的先序遍历序列是abdcegf, 中序遍历序列是bdaegcf，则F 中树的棵数是（ ）。

A. 1
B. 2
C. 3
D. 4

答案： C

解析：

由先序序列和中序序列可重建二叉树 $T$。先序为

$$a,b,d,c,e,g,f,$$

中序为

$$b,d,a,e,g,c,f.$$

重建后，二叉树根结点及其沿右孩子指针形成的链为

$$a\to c\to f.$$

在森林的左孩子—右兄弟表示中，各棵树的根结点正是沿二叉树根结点的右孩子链排列的。因此森林中共有3棵树，选 C。

4.6 树与二叉树的应用

1. 【2010】对 $n(n\ge 2)$ 个权值均不相同的字符构造成哈夫曼树。下列关于该哈夫曼树的叙述中, 错误的是（ ）。

A. 该树一定是一棵完全二叉树

B. 树中一定没有度为1 的结点

C. 树中两个权值最小的结点一定是兄弟结点

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

答案： A

解析：

哈夫曼树的构造过程每次选取当前权值最小的两个结点合并，因此：

• 每次产生的非叶结点都有两个孩子，所以树中没有度为1的结点，B 正确；
• 初始权值最小的两个字符在第一次合并时成为兄弟，C 正确；
• 哈夫曼树中父结点权值为两个孩子权值之和，且按构造过程形成的层次满足非叶结点权值不小于下一层结点权值，D 正确。

哈夫曼树只要求带权路径长度最小，并不保证最后一层结点从左到右连续排列，所以不一定是完全二叉树。A 错误。

2. 【2013】已知三叉树T 中6 个叶结点的权分别是2、3、4、5、6、7,T 的带权(外部) 路径长度最小是（ ）。

A. 27
B. 46
C. 54
D. 56

答案： B

解析：

构造三叉哈夫曼树时，每次合并3个最小权值。满三叉树的叶结点数 $n_0$ 应满足

$$(n_0-1)\mathrm{mod}(3-1)=0.$$

原有6个叶结点，不满足该条件，因此补入一个权值为0的虚叶结点，得到权值序列

$$0,2,3,4,5,6,7.$$

依次合并：

$$0+2+3=5,$$ $$4+5+5=14,$$ $$6+7+14=27.$$

哈夫曼树的最小 WPL 等于各次合并所得权值之和：

$$WPL=5+14+27=46.$$

故选 B。

3. 【2014】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

答案： D

解析：

前缀编码要求任意一个字符的编码都不是其他字符编码的前缀。

在 D 中，编码 110 是编码 1100 的前缀，因此 D 不具有前缀特性。

其余三组中均不存在某个完整编码作为另一个编码前缀的情况，故选 D。

4. 【2015】下列选项给出的是从根分别到达两个叶结点路径上的权值序列,能属于同一棵哈夫曼树的是（ ）。

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

答案： D

解析：

哈夫曼树中任一非叶结点的权值等于其两个孩子的权值之和。

• A 中两个叶结点5和7若同以10为父结点，则应有 $5+7=10$，不成立；
• B 中根结点的两个孩子若分别为10和12，则根权值应为22而不是24；
• C 中权值为10的父结点有一个权值为10的孩子，则另一个孩子权值只能为0，不符合通常的正权值条件；
• D 中根结点可由权值10和14的两个孩子组成，且10可由5和5组成，14可由6和8组成，符合哈夫曼树的权值关系。

故选 D。

5. 【2017】已知字符集 {a、b、c、d、e、f 、g、h}，若各字符的哈夫曼编码依次是0100、10、0000、0101、001、011、11、0001，则编码序列0100011001001011110101 的译码结果是（ ）。

A. acgabfh
B. adbagbb

C. afbeagd
D. afeefgd

答案： D

解析：

按照前缀编码从左到右逐段匹配：

Text

0100 | 011 | 001 | 001 | 011 | 11 | 0101
  a     f     e     e     f     g      d

因此译码结果为

Text

afeefgd

故选 D。

6. 【2018】已知字符集 {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,3,8,2,10,4.$$

按哈夫曼算法依次合并：

$$2+3=5,$$ $$4+5=9,$$ $$6+8=14,$$ $$9+10=19,$$ $$14+19=33.$$

由此可知：权值10、8、6的字符编码长度均可为2，权值4的编码长度为3，权值3、2的编码长度为4。

选项 A 中各字符编码长度依次为

$$2,4,2,4,2,3,$$

恰好与权值大小所对应的哈夫曼树深度一致，并且这组编码满足前缀特性，所以可能是相应的哈夫曼编码。

故选 A。

7. 【2019】对n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115 个结点，则n 的值是（ ）。

A. 56
B. 57
C. 58
D. 60

答案： C

解析：

二叉哈夫曼树没有度为1的结点。若叶结点数为 $n$，则度为2的结点数为 $n-1$，总的结点数为

$$n+(n-1)=2n-1.$$

由题意

$$2n-1=115,$$

解得

$$n=58.$$

故选 C。

8. 【2021】若某二叉树有5 个叶子结点, 其权值分别为10、12、16、21、30，则其最小的带权路径长度(WPL) 是（ ）。

A. 89
B. 200
C. 208
D. 289

答案： B

解析：

按哈夫曼算法合并最小的两个权值：

$$10+12=22,$$ $$16+21=37,$$ $$22+30=52,$$ $$37+52=89.$$

最小带权路径长度等于所有合并权值之和：

$$WPL=22+37+52+89=200.$$

故选 B。

9. 【2022】对任意给定的含 $n(n>2)$ 个字符的有限集S, 用二叉树表示S 的哈夫曼编码集和定长编码集, 分别得到二叉树 $T_1$ 和 $T_2$。下列叙述中, 正确的是（ ）。

A. $T_1$ 与T2 的结点数相同

B. $T_1$ 的高度大于T2 的高度

C. 出现频次不同的字符在T1 中处于不同的层

D. 出现频次不同的字符在T2 中处于相同的层

答案： D

解析：

定长编码中，每个字符的编码长度都相同。用二叉树表示时，所有字符对应的叶结点均处于相同深度，与字符出现频次无关，因此出现频次不同的字符在 $T_2$ 中仍处于同一层，D 正确。

其他选项：

• 哈夫曼编码树与定长编码树的内部结点结构不同，结点数不一定相同，A 错误；
• 哈夫曼树高度可能大于、等于或在具体构造下与定长编码树不同，不能一概而论，B 错误；
• 不同频次字符在哈夫曼树中可能具有相同编码长度，因而可能处于同一层，C 错误。

10. 【2023】在由6 个字符组成的字符集S 中, 各字符出现的频次分别为3,4,5,6,8,10, 为S 构造的哈夫曼编码的加权平均长度为（ ）。

A. 2.4
B. 2.5
C. 2.67
D. 2.75

答案： B

解析：

按哈夫曼算法依次合并：

$$3+4=7,$$ $$5+6=11,$$ $$7+8=15,$$ $$10+11=21,$$ $$15+21=36.$$

因此哈夫曼树的带权路径长度为

$$WPL=7+11+15+21+36=90.$$

所有字符总频次为

$$3+4+5+6+8+10=36.$$

加权平均编码长度为

$$\frac{WPL}{36}=\frac{90}{36}=\mathrm{2.5.}$$

故选 B。

11. 【2012】设有6 个有序表A、B、C、D、E、F, 分别含有10、35、40、50、60 和200 个数据元素,各表中的元素按升序排列。要求通过5 次两两合并, 将6 个表最终合并成1 个升序表, 并在最坏情况下比较的总次数最小。请回答下列问题:

(1) 给出完整的合并过程, 并求出最坏情况下比较的总次数。

(2) 根据你的合并过程, 描述 $N(N\ge 2)$ 个不等长升序表的合并策略, 并说明理由。

答案：

(1) 每次选择当前长度最小的两个有序表进行合并：

合并步骤	被合并表长	新表长度	最坏比较次数
1	10，35	45	44
2	40，45	85	84
3	50，60	110	109
4	85，110	195	194
5	195，200	395	394

最坏情况下的总比较次数为

$$44+84+109+194+394=825.$$

(2) 对 $N$ 个不等长升序表，应反复选取当前长度最小的两个表合并，将新表长度重新放回待合并集合，直到只剩一个表。

解析：

长度分别为 $m,n$ 的两个升序表合并时，最坏情况下需要

$$m+n-1$$

次比较。整个合并过程可表示为一棵二叉树：原始表为叶结点，表长为叶结点权值；每次合并形成一个权值为两子树权值之和的内部结点。

若原始第 $i$ 个表的长度为 $w_i$，其在合并树中的深度为 $d_i$，则所有合并长度之和为

$$\sum _{i=1}^N{w}_i{d}_i.$$

总的最坏比较次数为

$$\sum _{i=1}^N{w}_i{d}_i-(N-1).$$

其中 $N-1$ 为合并次数，是常数。因此问题等价于使带权路径长度最小，正是哈夫曼树的最优合并问题。故每次合并两个最短表可得到最小总比较次数。

12. 【2014】二叉树的带权路径长度(WPL) 是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储, 其结点结构为 |left|weight|right|。其中叶结点的weight 域保存该结点的非负权值。设root 为指向T 的根结点的指针，请设计求T 的WPL 的算法, 要求:

(1) 给出算法的基本设计思想。

(2) 使用C 或C++ 语言, 给出二叉树结点的数据类型定义。

(3) 根据设计思想，采用C 或C++ 语言描述算法，关键之处给出注释。

答案：

(1) 从根结点开始递归遍历二叉树，同时记录当前结点的深度。若当前结点是叶结点，则将“叶结点权值乘以其深度”计入结果；若不是叶结点，则递归计算左、右子树的 WPL 并相加。

(2) 结点定义：

C

typedef struct BiTNode {
    int weight;
    struct BiTNode *left;
    struct BiTNode *right;
} BiTNode, *BiTree;

(3) 算法：

C

/* 求以root为根的二叉树的WPL，根结点深度规定为0 */
long long WPLCore(BiTree root, int depth) {
    if (root == NULL)
        return 0;

    /* 叶结点的带权路径长度为weight * depth */
    if (root->left == NULL && root->right == NULL)
        return (long long)root->weight * depth;

    return WPLCore(root->left, depth + 1)
         + WPLCore(root->right, depth + 1);
}

long long WPL(BiTree root) {
    return WPLCore(root, 0);
}

解析：

每个叶结点对 WPL 的贡献为

$$\text{weight}\times \text{depth}.$$

递归遍历能在到达叶结点时获得其深度并累加该贡献。每个结点仅访问一次，故时间复杂度为 $O(n)$；递归栈空间复杂度为 $O(h)$，其中 $h$ 为树高。

13. 【2020】若任一字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性,现有某字符集(字符个数≥2) 的不等长编码, 每个字符的编码均为二进制的0,1 序列, 最长为L 位, 且具有前缀特性。请回答下列问题:

(1) 哪种数据结构适宜保存上述具有前缀特性的不等长编码？

(2) 基于你所设计的数据结构, 简述从0/1 串到字符串的译码过程。

(3) 简述判定某字符集的不等长编码是否具有前缀特性的过程。

答案：

(1) 适合采用二叉字典树，即二叉 Trie，也可将其看作一棵编码树。树边分别表示0和1，字符存放在终止结点中。

(2) 译码时从根结点开始逐位读取0/1串：读到0就沿左孩子指针向下，读到1就沿右孩子指针向下。到达字符终止结点时输出该字符，并重新回到根结点继续处理后续位。若某一步对应孩子不存在，或输入结束时尚未回到根结点，则输入编码串非法。

(3) 将所有编码逐个插入二叉 Trie。插入某个编码时：

• 若尚未读取完该编码就到达已有字符终止结点，则已有编码是当前编码的前缀，不具有前缀特性；
• 读取完当前编码后，若当前结点已有孩子，则当前编码是某个已有编码的前缀，不具有前缀特性；
• 若当前结点已经是字符终止结点，则存在重复编码，也不合法；
• 所有编码均成功插入且未发生上述情况，则编码集具有前缀特性。

解析：

二叉 Trie 的根到某终止结点的路径唯一对应一个二进制编码。具有前缀特性等价于“任何字符终止结点都不是另一个字符终止结点的祖先”，因此既可用于高效译码，也可直接用于前缀特性的判定。

设待判定编码总长度为 $M$，建树及判定的时间复杂度为 $O(M)$，所需额外空间也为 $O(M)$；单个编码的长度不超过 $L$，故处理单个编码的时间为 $O(L)$。