第 9 章二叉树 · 知识细节练习

壹

树与二叉树基本概念

6 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

判断题：树中除根节点外，每个节点都有且仅有一个父节点。

（1 分）

A

正确

B

错误

第 2 题 A2 未作答

判断题：二叉树中每个节点最多有两个子节点，且左右子树有顺序之分。

（1 分）

A

正确

B

错误

第 3 题 A3 未作答

二叉树第 $4$ 层（根为第 $1$ 层）最多有（）个节点。

（1 分）

A

$4$

B

$8$

C

$16$

D

$7$

第 4 题 A4 未作答

判断题： $n$ 个节点的树（二叉树）恰有 $n-1$ 条边。

（1 分）

A

正确

B

错误

第 5 题 A5 未作答

深度为 $5$ （根深度为 $1$ ）的二叉树最多有（）个节点。

（1 分）

A

$16$

B

$31$

C

$32$

D

$15$

第 6 题 A6 未作答

判断题：任意二叉树中，叶子节点数 = 度为 2 的节点数 + 1。

（1 分）

A

正确

B

错误

贰

特殊二叉树

6 QUESTIONS · 2 POINTS EACH

第 7 题 B1 未作答

判断题：满二叉树每一层的节点数都达到最大值。

（1 分）

A

正确

B

错误

第 8 题 B2 未作答

判断题：完全二叉树除最后一层外每层都满，且最后一层节点靠左排列。

（1 分）

A

正确

B

错误

第 9 题 B3 未作答

深度为 $4$ 的满二叉树共有（）个节点。

（1 分）

A

$7$

B

$8$

C

$15$

D

$16$

第 10 题 B4 未作答

有 $100$ 个节点的完全二叉树的深度是（）（根深度为 $1$ ）。

（1 分）

A

$6$

B

$7$

C

$8$

D

$10$

第 11 题 B5 未作答

完全二叉树数组存储（根编号为 $1$ ），编号为 $i$ 的节点的左孩子编号是（）。

（1 分）

A

$2i$

B

$2i+1$

C

$i/2$

D

$i+1$

第 12 题 B6 未作答

判断题：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

（1 分）

A

正确

B

错误

叁

遍历

7 QUESTIONS · 2 POINTS EACH

第 13 题 C1 未作答

前序遍历的顺序是（）。

（1 分）

A

根节点 → 左子树 → 右子树

B

左子树 → 根节点 → 右子树

C

左子树 → 右子树 → 根节点

D

逐层从左到右

第 14 题 C2 未作答

中序遍历的顺序是（）。

（1 分）

A

根节点 → 左子树 → 右子树

B

左子树 → 根节点 → 右子树

C

左子树 → 右子树 → 根节点

D

逐层从左到右

第 15 题 C3 未作答

后序遍历的顺序是（）。

（1 分）

A

根节点 → 左子树 → 右子树

B

左子树 → 根节点 → 右子树

C

左子树 → 右子树 → 根节点

D

逐层从左到右

第 16 题 C4 未作答

判断题：层序遍历从上到下、从左到右逐层访问，通常用队列实现。

（1 分）

A

正确

B

错误

第 17 题 C5 未作答

某二叉树前序 A B C、中序 B A C，则该树的后序是（）。

（1 分）

A

B C A

B

C B A

C

A C B

D

B A C

第 18 题 C6 未作答

判断题：已知前序遍历和中序遍历序列，可以唯一确定一棵二叉树。

（1 分）

A

正确

B

错误

第 19 题 C7 未作答

判断题：表达式树的前序遍历 = 前缀表达式、中序遍历 = 中缀表达式、后序遍历 = 后缀表达式。

（1 分）

A

正确

B

错误

肆

性质进阶

6 QUESTIONS · 2 POINTS EACH

第 20 题 D1 未作答

某二叉树有 $7$ 个叶子节点，则度为 $2$ 的节点有（）个。

（1 分）

A

$7$

B

$8$

C

$6$

D

$5$

第 21 题 D2 未作答

$7$ 个节点的完全二叉树有（）个叶子节点。

（1 分）

A

$3$

B

$4$

C

$5$

D

$2$

第 22 题 D3 未作答

判断题：深度为 $k$ 的二叉树节点数范围是 $[k, 2^k - 1]$ 。

（1 分）

A

正确

B

错误

第 23 题 D4 未作答

判断题：完全二叉树适合用数组顺序存储（按层编号），一般二叉树用数组会浪费空间。

（1 分）

A

正确

B

错误

第 24 题 D5 未作答

判断题：树（二叉树）的高度 = 根节点到最远叶子的边数（或层数）。

（1 分）

A

正确

B

错误

第 25 题 D6 未作答

判断题：二叉链表存储二叉树，每个节点含数据域、左孩子指针、右孩子指针。

（1 分）

A

正确

B

错误

伍

哈夫曼树与编码

7 QUESTIONS · 2 POINTS EACH

第 26 题 E1 未作答

判断题：哈夫曼树是带权路径长度（WPL）最小的二叉树。

（1 分）

A

正确

B

错误

第 27 题 E2 未作答

权值为 $\{2, 3, 4, 5\}$ 的哈夫曼树的 WPL 是（）。

（1 分）

A

$14$

B

$24$

C

$28$

D

$40$

第 28 题 E3 未作答

判断题：哈夫曼编码把出现频率高的字符编成较短的码字。

（1 分）

A

正确

B

错误

第 29 题 E4 未作答

判断题：哈夫曼编码是前缀编码——任何一个码字都不是另一个码字的前缀，解码无歧义。

（1 分）

A

正确

B

错误

第 30 题 E5 未作答

判断题：构造哈夫曼树时，每次从集合中取出权值最小的两个节点合并成新节点（贪心）。

（1 分）

A

正确

B

错误

第 31 题 E6 未作答

判断题：哈夫曼编码的总长度 = 各字符权值 × 其码字长度的和 = WPL。

（1 分）

A

正确

B

错误

第 32 题 E7 未作答

判断题：频率分布不均时，哈夫曼编码总长度通常短于等长编码。

（1 分）

A

正确

B

错误

陆

二叉搜索树与完全二叉树

7 QUESTIONS · 2 POINTS EACH

第 33 题 F1 未作答

判断题：二叉搜索树（BST）中，左子树所有节点值 < 根 < 右子树所有节点值（假设无重复）。

（1 分）

A

正确

B

错误

第 34 题 F2 未作答

判断题：BST 查找从根开始，目标比当前节点小走左子树、大走右子树——每次排除一半。

（1 分）

A

正确

B

错误

第 35 题 F3 未作答

判断题：BST 插入新值也是"比当前小走左、大走右"，最终落在空位成为叶子。

（1 分）

A

正确

B

错误

第 36 题 F4 未作答

判断题：对 BST 做中序遍历，得到的序列是有序的（升序）。

（1 分）

A

正确

B

错误

第 37 题 F5 未作答

判断题：完全二叉树可以用数组表示：根存下标 1，节点 $i$ 的左孩子是 $2i$ 、右孩子是 $2i+1$ ——恰好按层序依次连续存放。

（1 分）

A

正确

B

错误

第 38 题 F6 未作答

单选题：完全二叉树数组表示（根在下标 1）中，下标 $6$ 的节点的父节点下标是？

（1 分）

A

$3$ （父 = 子 ÷ 2）

B

$2$

C

$12$

D

$13$

第 39 题 F7 未作答

判断题：完全二叉树按层序存放在数组中时，数组的先后顺序恰好就是层序遍历的结果。

（1 分）

A

正确

B

错误

柒

实现与操作

6 QUESTIONS · 2 POINTS EACH

第 40 题 G1 未作答

判断题：二叉树可以递归定义：空树是二叉树，或"根 + 左子树（二叉树）+ 右子树（二叉树）"。

（1 分）

A

正确

B

错误

第 41 题 G2 未作答

判断题：二叉树深度 = max(左子树深度, 右子树深度) + 1，空树深度为 0。

（1 分）

A

正确

B

错误

第 42 题 G3 未作答

判断题：二叉树节点数 = 左子树节点数 + 右子树节点数 + 1，空树为 0。

（1 分）

A

正确

B

错误

第 43 题 G4 未作答

判断题：叶子节点数 = 左子树叶子数 + 右子树叶子数；单节点树叶子数为 1。

（1 分）

A

正确

B

错误

第 44 题 G5 未作答

判断题：BST 查找的平均复杂度为 $O(\log n)$ ，最坏（退化成链）为 $O(n)$ 。

（1 分）

A

正确

B

错误

第 45 题 G6 未作答

判断题：BST 插入的平均复杂度 $O(\log n)$ ，插入后中序仍有序。

（1 分）

A

正确

B

错误

捌

易错综合

5 QUESTIONS · 2 POINTS EACH

第 46 题 H1 未作答

判断题：后序遍历 = 左子树 → 右子树 → 根节点，根节点最后访问。

（1 分）

A

正确

B

错误

第 47 题 H2 未作答

判断题：完全二叉树要求最后一层靠左连续，满二叉树要求所有层全满。

（1 分）

A

正确

B

错误

第 48 题 H3 未作答

判断题：完全二叉树数组存储时根节点编号为 $1$ ，孩子 $2i$ 、 $2i+1$ 、父亲 $\lfloor i/2 \rfloor$ 。

（1 分）

A

正确

B

错误

第 49 题 H4 未作答

判断题：WPL = 每个叶子节点的权值 × 根到它的路径长度之和（不是节点值相加）。

（1 分）

A

正确

B

错误

第 50 题 H5 未作答

下列说法错误的是（）。

（1 分）

A

满二叉树必是完全二叉树

B

哈夫曼编码是前缀码

C

BST 中序遍历有序

D

前序遍历 = 左 → 右 → 根

玖

二叉树存储与结构

6 QUESTIONS · 2 POINTS EACH

第 51 题 I1 未作答

01struct Node {
02    int data;        // 数据域
03    Node *lchild;    // 左孩子指针
04    Node *rchild;    // 右孩子指针
05};

判断题：二叉链表每个节点含数据域和左右孩子两个指针，空孩子指针为 NULL。

（1 分）

A

正确

B

错误

第 52 题 I2 未作答

01const int MAXN = 100;
02int tree[MAXN];   // 完全二叉树的顺序存储：根下标 1，左孩子 2i、右孩子 2i+1
03// 空位存 -1 表示没有节点

判断题：一般二叉树（非完全）顺序存储时中间会有大量空洞，浪费空间。

（1 分）

A

正确

B

错误

第 53 题 I3 未作答

01const int MAXN = 100;
02int tree[MAXN];
03int n;
04// 按层序读入 n 个节点的完全二叉树（1 号下标开始存，空节点读入 -1）

判断题：读入顺序 = 层序遍历顺序，tree[i] 的孩子在 tree[2*i]、tree[2*i+1]。

（1 分）

A

正确

B

错误

第 54 题 I4 未作答

// 完全二叉树数组存储，根编号 1，编号 i 的节点：
// 左孩子 = 2 * i，右孩子 = 2 * i + 1，父亲 = i / 2

编号为 $6$ 的节点的父节点编号是（）。

（1 分）

A

$2$

B

$3$

C

$12$

D

$4$

第 55 题 I5 未作答

01const int MAXN = 100;
02int tree[MAXN];   // tree[1]=10, tree[2]=20, tree[3]=30,
03                  // tree[4]=40, tree[5]=50, tree[6]=60, tree[7]=70
04
05// 前序遍历（递归版）：
06void pre(int i) {
07    if (i > 7 || tree[i] == -1) return;
08    cout << tree[i] << ' ';
09    pre(2 * i);
10    pre(2 * i + 1);
11}

调用 pre(1) 输出为（）。

（1 分）

A

10 20 40 50 30 60 70

B

40 20 50 10 60 30 70

C

10 20 30 40 50 60 70

D

40 50 20 60 70 30 10

第 56 题 I6 未作答

01// 满二叉树：深度 k，节点总数 = 2^k - 1
02int cnt(int k) {
03    return (1 << k) - 1;
04}

判断题：深度 $4$ 的满二叉树调用 cnt(4) 返回 $15$ 。

（1 分）

A

正确

B

错误

拾

遍历代码

7 QUESTIONS · 2 POINTS EACH

第 57 题 J1 未作答

01struct Node { char data; Node *l, *r; };
02// 树形：     A
03//          /   \
04//         B     C
05//        / \   /
06//       D   E F
07void pre(Node *p) {
08    if (p == NULL) return;
09    cout << p->data;
10    pre(p->l);
11    pre(p->r);
12}

前序遍历输出为（）。

（1 分）

A

ABDECF

B

DBEAFC

C

DEBFCA

D

ABCDEF

第 58 题 J2 未作答

01// 树形：     A
02//          /   \
03//         B     C
04//        / \   /
05//       D   E F
06void in(Node *p) {
07    if (p == NULL) return;
08    in(p->l);
09    cout << p->data;
10    in(p->r);
11}

中序遍历输出为（）。

（1 分）

A

ABDECF

B

DBEAFC

C

DEBFCA

D

DBEACF

第 59 题 J3 未作答

01// 树形：     A
02//          /   \
03//         B     C
04//        / \   /
05//       D   E F
06void post(Node *p) {
07    if (p == NULL) return;
08    post(p->l);
09    post(p->r);
10    cout << p->data;
11}

后序遍历输出为（）。

（1 分）

A

DEBFCA

B

DBEAFC

C

ABDECF

D

DEFCBA

第 60 题 J4 未作答

// 树形：
//      A
//     / \
//    B   C
//   / \ /
//  D  E F
// 前序 ABDECF、中序 DBEAFC、后序 DEBFCA

判断题：前序第一个节点是根，后序最后一个节点是根。

（1 分）

A

正确

B

错误

第 61 题 J5 未作答

01// 层序遍历：队列保存节点，出队时输出并把左右孩子入队
02// 树形：     A
03//          /   \
04//         B     C
05//        / \   /
06//       D   E F
07queue<Node*> q;
08q.push(root);
09while (!q.empty()) {
10    Node *p = q.front(); q.pop();
11    cout << p->data;
12    if (p->l) q.push(p->l);
13    if (p->r) q.push(p->r);
14}

层序遍历输出为（）。

（1 分）

A

ABCDEF

B

ABDECF

C

DBEAFC

D

ACBDEF

第 62 题 J6 未作答

某二叉树：前序 = "ABDEC"，中序 = "DBEAC"

由前序定根、中序分左右子树，可推出后序为（）。

（1 分）

A

DEBCA

B

DBEAC

C

EDCBA

D

DEBAC

第 63 题 J7 未作答

01struct Node { char data; Node *l, *r; };
02
03// 后序遍历：左 → 右 → 根
04void post(Node *p) {
05    if (p == NULL) return;
06    post(p->l);
07    ______;
08    cout << p->data;
09}

横线处应填（）。

（1 分）

A

post(p->r)

B

post(p->l)

C

cout << p->data

D

return

拾壹

递归计算代码

7 QUESTIONS · 2 POINTS EACH

第 64 题 K1 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求二叉树的节点个数
04int cnt(Node *p) {
05    if (p == NULL) return 0;
06    return cnt(p->l) + cnt(p->r) + 1;
07}

树形（A 为根）：

      A
     / \
    B   C
   / \ /
  D  E F

该树共 $6$ 个节点，判断题：cnt(root) 返回 $6$ 。

（1 分）

A

正确

B

错误

第 65 题 K2 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求深度：空树 0，否则 max(左,右) + 1
04int depth(Node *p) {
05    if (p == NULL) return 0;
06    return max(depth(p->l), depth(p->r)) + 1;
07}

树形（A 为根）：

      A
     / \
    B   C
   / \ /
  D  E F

该树深度为 $3$ （最远叶子到根的层数），判断题：depth(root) 返回 $3$ 。

（1 分）

A

正确

B

错误

第 66 题 K3 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求叶子数：叶子 = 左右都空
04int leaf(Node *p) {
05    if (p == NULL) return 0;
06    if (p->l == NULL && p->r == NULL) return 1;
07    return leaf(p->l) + leaf(p->r);
08}

树形（A 为根）：

      A
     / \
    B   C
   / \ /
  D  E F

该树的叶子是 D、E、F（没有孩子的节点）共 $3$ 个，判断题：leaf(root) 返回 $3$ 。

（1 分）

A

正确

B

错误

第 67 题 K4 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求第 k 层节点数（根是第 1 层）
04int levelCnt(Node *p, int k) {
05    if (p == NULL || k < 1) return 0;
06    if (k == 1) return 1;
07    return levelCnt(p->l, k - 1) + levelCnt(p->r, k - 1);
08}

树形（A 为根）：

      A
     / \
    B   C
   / \ /
  D  E F

判断题：levelCnt(root, 3) 返回 $3$ （第三层有 D、E、F 三个节点）。

（1 分）

A

正确

B

错误

第 68 题 K5 未作答

01struct Node { int data; Node *l, *r; };
02
03// 交换左右子树（镜像）
04void mirror(Node *p) {
05    if (p == NULL) return;
06    swap(p->l, p->r);
07    mirror(p->l);
08    mirror(p->r);
09}

判断题：mirror 递归地把每棵子树的左右孩子交换——整棵树变成"镜像"。

（1 分）

A

正确

B

错误

第 69 题 K6 未作答

01// 判断满二叉树：每层都满 ⇔ 节点数 = 2^深度 - 1
02bool isFull(Node *p) {
03    return cnt(p) == (1 << depth(p)) - 1;
04}

树形（A 为根）：

      A
     / \
    B   C
   / \ /
  D  E F

该树共 6 节点、深度 3， $2^3 - 1 = 7 \ne 6$ ，判断题：返回 false（不是满二叉树）。

（1 分）

A

正确

B

错误

第 70 题 K7 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求二叉树最大值
04int maxVal(Node *p) {
05    if (p == NULL) return -1e9;
06    return max(p->data, max(maxVal(p->l), maxVal(p->r)));
07}

判断题：空节点返回极小值 $-10^9$ ，保证不影响比较结果。

（1 分）

A

正确

B

错误

拾贰

BST 代码

7 QUESTIONS · 2 POINTS EACH

第 71 题 L1 未作答

01struct Node { int data; Node *l, *r; };
02
03// BST 查找：小走左、大走右、相等命中
04bool find(Node *p, int x) {
05    if (p == NULL) return false;
06    if (p->data == x) return true;
07    return x < p->data ? find(p->l, x) : find(p->r, x);
08}

BST：5（根），左 3（左 2），右 8（左 6），判断题：find(root, 6) 的查找路径是 5 → 8 → 6。

（1 分）

A

正确

B

错误

第 72 题 L2 未作答

01struct Node { int data; Node *l, *r; };
02
03// BST 插入：小走左、大走右，到空位落成叶子
04void insert(Node* &p, int x) {
05    if (p == NULL) { p = new Node; p->data = x; p->l = p->r = NULL; return; }
06    if (x < p->data) insert(p->l, x);
07    else insert(p->r, x);
08}

判断题：依次插入 5、3、8、6，6 落在 8 的左孩子位置。

（1 分）

A

正确

B

错误

第 73 题 L3 未作答

01// 对 BST 5（左 3（左 2）、右 8（左 6））做中序遍历
02void in(Node *p) {
03    if (p == NULL) return;
04    in(p->l);
05    cout << p->data << ' ';
06    in(p->r);
07}

输出为（）。

（1 分）

A

2 3 5 6 8

B

5 3 8 2 6

C

2 3 6 8 5

D

5 3 2 8 6

第 74 题 L4 未作答

依次向空 BST 插入：4, 2, 6, 1, 3, 5, 7

构建完成后中序遍历输出为（）。

（1 分）

A

1 2 3 4 5 6 7

B

4 2 6 1 3 5 7

C

1 3 5 7 2 6 4

D

4 2 1 3 6 5 7

第 75 题 L5 未作答

BST：8（左 3（右 6（左 4）），右 10）

查找 4 的路径是（）。

（1 分）

A

8 3 6 4

B

8 10 6 4

C

4 6 3 8

D

8 3 4

第 76 题 L6 未作答

01// 判断一棵树是否是 BST：中序遍历检查是否严格递增
02bool ok = true;
03int prev = INT_MIN;
04void check(Node *p) {
05    if (p == NULL) return;
06    check(p->l);
07    if (p->data <= prev) ok = false;
08    prev = p->data;
09    check(p->r);
10}

判断题：中序遍历 BST 应严格递增——出现"当前值 ≤ 前一个值"即判定非 BST。

（1 分）

A

正确

B

错误

第 77 题 L7 未作答

01// BST 最小值 = 一直向左走到底
02int minVal(Node *p) {
03    while (p->l != NULL) p = p->l;
04    return p->data;
05}

判断题：BST 的最小值在最左边的节点（左子树为空的节点）。

（1 分）

A

正确

B

错误

拾叁

完全二叉树数组代码

6 QUESTIONS · 2 POINTS EACH

第 78 题 M1 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {0, 1, 2, 3, 4, 5, 6, 7};   // 完全二叉树数组存储（a[0] 不用）
05    // 第 2 层的节点：下标 2、3
06    cout << a[2] << " " << a[3];
07    return 0;
08}

单选题：程序输出是？

（1 分）

A

2 3

B

4 5

C

1 2

D

6 7

第 79 题 M2 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int i = 5;                            // 节点下标（根为 1）
05    int parent = i / 2;                   // 父节点
06    int left = 2 * i;                     // 左孩子
07    cout << parent << " " << left;
08    return 0;
09}

单选题：程序输出是？

（1 分）

A

2 10

B

3 10

C

2 11

D

5 10

第 80 题 M3 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 7;                            // 节点个数
05    int depth = 0;
06    while ((1 << depth) <= n) depth++;    // 2^depth <= n 的最大层
07    cout << depth;                        // 完全二叉树深度
08    return 0;
09}

单选题：程序输出是？

（1 分）

A

3

B

2

C

7

D

4

第 81 题 M4 未作答

单选题：完全二叉树数组表示的特点是？

（1 分）

A

下标 $1 \sim n$ 连续存放、中间没有空缺

B

只存叶子节点

C

数组必须已排序

D

必须用链表辅助

第 82 题 M5 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {0, 10, 20, 30, 40, 50, 60, 70};   // 完全二叉树数组存储
05    int i = 3;                            // 节点下标
06    cout << a[2 * i];                     // 左孩子的值
07    return 0;
08}

单选题：程序输出是？

（1 分）

A

60

B

30

C

40

D

70

第 83 题 M6 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {0, 1, 2, 3, 4, 5, 6, 7};   // 完全二叉树数组存储
05    int i = 3;                            // 当前节点下标
06    cout << a[______] << " " << a[______];  // 输出节点 i 的左右孩子
07    return 0;
08}

单选题：两处横线依次应填入？

（1 分）

A

2 * i、2 * i + 1

B

i / 2、i / 2 + 1

C

i + 1、i + 2

D

i - 1、i - 2

拾肆

完善程序

7 QUESTIONS · 2 POINTS EACH

第 84 题 N1 未作答

01struct Node { char data; Node *l, *r; };
02
03// 前序遍历：根 → 左 → 右
04void pre(Node *p) {
05    if (p == NULL) return;
06    cout << p->data;
07    pre(p->l);
08    ______;
09}

横线处应填（）。

（1 分）

A

pre(p->r)

B

pre(p->l)

C

cout << p->data

D

return

第 85 题 N2 未作答

01struct Node { char data; Node *l, *r; };
02
03// 中序遍历：左 → 根 → 右
04void in(Node *p) {
05    if (p == NULL) return;
06    ______;
07    cout << p->data;
08    in(p->r);
09}

横线处应填（）。

（1 分）

A

in(p->l)

B

in(p->r)

C

cout << p->data

D

return

第 86 题 N3 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求深度：空树 0，否则 max(左,右) + 1
04int depth(Node *p) {
05    if (p == NULL) return 0;
06    return ______;
07}

横线处应填（）。

（1 分）

A

max(depth(p->l), depth(p->r)) + 1

B

depth(p->l) + depth(p->r) + 1

C

max(depth(p->l), depth(p->r))

D

depth(p->l) + depth(p->r)

第 87 题 N4 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求节点数：空树 0，否则 左 + 右 + 1
04int cnt(Node *p) {
05    if (p == NULL) return 0;
06    return ______;
07}

横线处应填（）。

（1 分）

A

cnt(p->l) + cnt(p->r) + 1

B

cnt(p->l) + cnt(p->r)

C

max(cnt(p->l), cnt(p->r)) + 1

D

cnt(p->l) + 1

第 88 题 N5 未作答

01struct Node { int data; Node *l, *r; };
02
03// 求叶子数
04int leaf(Node *p) {
05    if (p == NULL) return 0;
06    if (______) return 1;
07    return leaf(p->l) + leaf(p->r);
08}

横线处应填（）。

（1 分）

A

p->l == NULL && p->r == NULL

B

p->l != NULL && p->r != NULL

C

p->l == NULL

D

p->r == NULL

第 89 题 N6 未作答

01struct Node { int data; Node *l, *r; };
02
03// BST 插入
04void insert(Node* &p, int x) {
05    if (p == NULL) {
06        p = new Node;
07        p->data = x; p->l = p->r = NULL;
08        return;
09    }
10    if (x < p->data) insert(p->l, x);
11    else ______;
12}

横线处应填（）。

（1 分）

A

insert(p->r, x)

B

insert(p->l, x)

C

p->r = x

D

return

第 90 题 N7 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {0, 1, 2, 3, 4, 5, 6, 7};   // 完全二叉树数组存储（a[0] 不用）
05    int i = 6;                            // 当前节点下标
06    cout << a[______];                    // 输出节点 i 的父节点值
07    return 0;
08}

单选题：横线处应填入？

（1 分）

A

i / 2

B

2 * i

C

i + 1

D

i - 1

拾伍

代码综合应用

5 QUESTIONS · 2 POINTS EACH

第 91 题 O1 未作答

层序遍历（队列）：完全二叉树数组存：10, 20, 30, 40, 50, 60, 70（下标 1 起）

按层输出 = 数组下标顺序 1..7，输出为（）。

（1 分）

A

10 20 30 40 50 60 70

B

10 20 40 50 30 60 70

C

40 20 50 10 60 30 70

D

40 50 20 60 70 30 10

第 92 题 O2 未作答

前序 + 中序重建二叉树：

前序 = "ABDECF"，中序 = "DBEAFC"

重建后的树：A 为根，B 的左右孩子是 D/E，C 的左孩子是 F

判断题：重建时先取前序第一个为根，再在中序里找根位置分左右子树，递归建。

（1 分）

A

正确

B

错误

第 93 题 O3 未作答

权值 {2, 3, 4, 5} 构造哈夫曼树（每次合并最小的两个）：

2+3=5 → {4, 5, 5}；4+5=9 → {5, 9}；5+9=14

WPL = 2*3 + 3*3 + 4*2 + 5*1 = 28

判断题：构造过程中新节点权值 = 两个子节点权值之和，最终根权值 = 全部权值和。

（1 分）

A

正确

B

错误

第 94 题 O4 未作答

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {0, 1, 2, 3, 4, 5, 6, 7};   // 完全二叉树数组存储
05    cout << a[1] << endl;                 // 第 1 层
06    cout << a[2] << " " << a[3] << endl;  // 第 2 层
07    cout << a[4] << " " << a[5] << " " << a[6] << " " << a[7] << endl;  // 第 3 层
08    return 0;
09}

单选题：程序输出是？

（1 分）

A

1 换行 2 3 换行 4 5 6 7

B

1 2 3 4 5 6 7

C

7 6 5 4 3 2 1

D

1 换行 2 4 换行 3 5 6 7

第 95 题 O5 未作答

依次插入 7, 2, 9, 1, 5 到 BST，中序遍历输出 = 排序结果

输出为（）。

（1 分）

A

1 2 5 7 9

B

7 2 9 1 5

C

9 7 5 2 1

D

1 5 2 9 7

拾陆

代码易错

5 QUESTIONS · 2 POINTS EACH

第 96 题 P1 未作答

01// 前序遍历（缺少递归出口）：
02void pre(Node *p) {
03    cout << p->data;
04    pre(p->l);
05    pre(p->r);
06}

判断题：没有 if (p == NULL) return; 出口，遇到叶子节点会继续对空指针解引用导致崩溃。

（1 分）

A

正确

B

错误

第 97 题 P2 未作答

01// 中序遍历（左右写反）：
02void in(Node *p) {
03    if (p == NULL) return;
04    in(p->r);          // 先右
05    cout << p->data;
06    in(p->l);          // 后左
07}

判断题：这样输出的是"降序"（对 BST 而言是右-根-左遍历），不是标准中序。

（1 分）

A

正确

B

错误

第 98 题 P3 未作答

01// 层序遍历误用栈（stack）代替队列（queue）：
02stack<Node*> st;
03st.push(root);
04while (!st.empty()) {
05    Node *p = st.top(); st.pop();
06    cout << p->data;
07    if (p->l) st.push(p->l);
08    if (p->r) st.push(p->r);
09}

判断题：用栈会变成深度优先（后进先出），输出不再是层序。

（1 分）

A

正确

B

错误

第 99 题 P4 未作答

01// 求深度（缺少空树判断）：
02int depth(Node *p) {
03    return max(depth(p->l), depth(p->r)) + 1;   // 无 p == NULL 出口
04}

判断题：没有空树出口，递归到叶子时会解引用空指针——崩溃。

（1 分）

A

正确

B

错误

第 100 题 P5 未作答

下列说法错误的是（）。

（1 分）

A

前序遍历第一个节点是根

B

BST 中序遍历升序

C

完全二叉树第 $层最多有 ^{k-1}$ 个节点

D

后序遍历第一个节点是根

重置作答

第 9 章 二叉树 · 知识细节练习

判 分 报 告

树与二叉树基本概念

特殊二叉树

遍历

性质进阶

哈夫曼树与编码

二叉搜索树与完全二叉树

实现与操作

易错综合

二叉树存储与结构

遍历代码

递归计算代码

BST 代码

完全二叉树数组代码

完善程序

代码综合应用

代码易错

打印

导出 HTML 子卷

第 9 章二叉树 · 知识细节练习

判分报告