树二叉树 · 考纲词条练习

第 1 题单选未作答

令根结点的高度为 $1$ ，则含有 $2021$ 个结点的二叉树的高度至少为（）。（2021 年真题）

（2 分）

A

$10$

B

$2021$

C

$11$

D

$12$

原创 2026 · 单选第1题｜知识点 KJ-27c、KJ-27f

第 2 题单选未作答

前序遍历和中序遍历相同的二叉树为且仅为（）。（2021 年真题）

（2 分）

A

非叶子结点只有右子树的二叉树

B

根结点没有左子树的二叉树

C

只有 $1$ 个点的二叉树

D

非叶子结点只有左子树的二叉树

原创 2026 · 单选第2题｜知识点 KJ-27c、KJ-27f

第 3 题单选未作答

前序遍历和后序遍历相同的二叉树为且仅为（）。

（2 分）

A

所有二叉树

B

满二叉树

C

只有根结点（单结点树）——前序=后序=根；两结点以上前序根在首、后序根在尾必不同

D

完全二叉树

原创 2026 · 单选第3题｜知识点 KJ-27c、KJ-27f

第 4 题单选未作答

深度为 $5$ （根深度 $1$ ）的完全 $3$ 叉树，前序遍历编号从 $1$ 开始，第 $100$ 号结点的父结点是第（）号。（2022 年真题）

（2 分）

A

$96$

B

$95$

C

$97$

D

$98$

原创 2026 · 单选第4题｜知识点 KJ-27c、KJ-27f

第 5 题单选未作答

完全 $k$ 叉树前序编号从 $1$ 开始，第 $i$ 个结点的父结点编号是（）。

（2 分）

A

$\lfloor i/k \rfloor$

B

$\lfloor (i-2)/k \rfloor + 1$

C

$i - k$

D

$\lceil i/k \rceil$

原创 2026 · 单选第5题｜知识点 KJ-27c、KJ-27f

第 6 题单选未作答

完全 $k$ 叉树第 $h$ 层最多有（）个结点。

（2 分）

A

$h^k$

B

$k \times h$

C

$k^{h-1}$

D

$2^h$

原创 2026 · 单选第6题｜知识点 KJ-27c、KJ-27f

第 7 题单选未作答

含有 $h$ 层的完全二叉树最多包含多少个结点（）。（2024 年真题）

（2 分）

A

$2^h - 1$

B

$2^{h+1}$

C

$2^h$

D

$2^{h+1} - 1$

原创 2026 · 单选第7题｜知识点 KJ-27c、KJ-27f

第 8 题单选未作答

高度为 $h$ 的二叉树最少有（）个结点。

（2 分）

A

$2^h$

B

$2^{h-1}$

C

$0$

D

$h$ ——每层恰好一个结点（链形）

原创 2026 · 单选第8题｜知识点 KJ-27c、KJ-27f

第 9 题单选未作答

$n$ 个结点的满二叉树，叶子结点个数为（）。

（2 分）

A

$\sqrt{n}$

B

$n-1$

C

$n/3$

D

$(n+1)/2$

原创 2026 · 单选第9题｜知识点 KJ-27c、KJ-27f

第 10 题单选未作答

$n$ 个结点的完全二叉树（编号 $1 \sim n$ ），编号为 $i$ 的结点是叶子结点的条件是（）。

（2 分）

A

$2i > n$ ——没有左孩子就没有右孩子，是叶子

B

$2i + 1 > n$

C

$i > n/2$

D

$i$ 是偶数

原创 2026 · 单选第10题｜知识点 KJ-27c、KJ-27f

第 11 题单选未作答

$100$ 个结点的二叉树，最大高度和最小高度分别是（）。

（2 分）

A

$100$ 和 $100$

B

$99$ 和 $7$

C

$50$ 和 $10$

D

$100$ 和 $7$

原创 2026 · 单选第11题｜知识点 KJ-27c、KJ-27f

第 12 题单选未作答

关于二叉树性质，错误的是（）。

（2 分）

A

满二叉树第 $h$ 层有 $2^{h-1}$ 个结点

B

完全二叉树编号 $i$ 的左孩子是 $2i$

C

$n$ 个结点的二叉树高度在 $\lceil \log_2(n+1) \rceil$ 到 $n$ 之间

D

任何二叉树的叶子数都等于度为 $2$ 的结点数

原创 2026 · 单选第12题｜知识点 KJ-27c、KJ-27f

第 13 题单选未作答

二叉搜索树（BST）的性质是（）。

（2 分）

A

所有结点值都相同

B

左子树所有结点值 $<$ 根 $<$ 右子树所有结点值

C

是完全二叉树

D

左子树值大于根，右子树值小于根

原创 2026 · 单选第13题｜知识点 KJ-27i

第 14 题单选未作答

BST 的中序遍历结果是（）。

（2 分）

A

升序序列——这是 BST 最重要的性质

B

不确定

C

原插入顺序

D

降序序列

原创 2026 · 单选第14题｜知识点 KJ-27i

第 15 题单选未作答

向 BST 插入元素 $x$ 的过程是（）。

（2 分）

A

从根出发： $x$ 小于当前结点走左、大于走右，走到空位插入——比较决定方向

B

随机选择位置

C

插入到最后一个叶子的右孩子

D

插入到根

原创 2026 · 单选第15题｜知识点 KJ-27i

第 16 题单选未作答

在平衡的 BST 中查找元素的时间复杂度是（）。

（2 分）

A

$O(1)$

B

$O(\log n)$ ——每步排除一半

C

$O(n \log n)$

D

$O(n)$

原创 2026 · 单选第16题｜知识点 KJ-27i

第 17 题单选未作答

BST 的根结点值与左右子树的关系是（）。

（2 分）

A

左子树值等于根值

B

只有左孩子 < 根 < 右孩子

C

没有固定关系

D

左子树所有结点值 $<$ 根值 $<$ 右子树所有结点值——不只是直接孩子

原创 2026 · 单选第17题｜知识点 KJ-27i

第 18 题单选未作答

BST 中某结点的左子树中最大结点值与右子树中最小结点值的关系是（）。

（2 分）

A

不确定

B

两者相等

C

左子树最大 $<$ 根 $<$ 右子树最小——三者严格递增

D

左子树最大 $>$ 右子树最小

原创 2026 · 单选第18题｜知识点 KJ-27i

第 19 题单选未作答

BST 删除叶子结点只需（）。

（2 分）

A

直接删除——父结点对应指针置空即可，不影响其余结构

B

需要旋转

C

不能删除叶子

D

需要重建整棵树

原创 2026 · 单选第19题｜知识点 KJ-27i

第 20 题单选未作答

向空 BST 依次插入 $1, 2, 3, \ldots, n$ （升序），树的高度变为（）。

（2 分）

A

$\log_2 n$

B

$n/2$

C

$\sqrt{n}$

D

$n$ ——退化为链表（每个新元素都是最大值，全走右路）

原创 2026 · 单选第20题｜知识点 KJ-27i

第 21 题单选未作答

$n$ 个结点的 BST 最好情况高度是（）。

（2 分）

A

$1$

B

$\lceil \log_2(n+1) \rceil$ ——恰好是满二叉树形态

C

$n/2$

D

$n$

原创 2026 · 单选第21题｜知识点 KJ-27i

第 22 题单选未作答

BST 的后序遍历是 $2, 5, 4, 8, 12, 10, 6$ ，前序遍历是（）。（2025 年真题）

（2 分）

A

$6, 4, 5, 2, 10, 12, 8$

B

$2, 4, 5, 6, 8, 10, 12$

C

$12, 8, 10, 5, 2, 4, 6$

D

$6, 4, 2, 5, 10, 8, 12$

原创 2026 · 单选第22题｜知识点 KJ-27i

第 23 题单选未作答

BST 的前序遍历是 $6, 4, 2, 5, 10, 8, 12$ ，后序遍历是（）。

（2 分）

A

$12, 8, 10, 5, 2, 4, 6$

B

$2, 4, 5, 8, 10, 12, 6$

C

$6, 4, 2, 5, 10, 8, 12$

D

$2, 5, 4, 8, 12, 10, 6$

原创 2026 · 单选第23题｜知识点 KJ-27i

第 24 题单选未作答

判定一棵二叉树是 BST 的充分必要条件是（）。

（2 分）

A

根结点是最大值

B

中序遍历结果严格递增

C

树是完全二叉树

D

每个结点的左孩子值小于右孩子值

原创 2026 · 单选第24题｜知识点 KJ-27i

第 25 题单选未作答

BST 与排序的关系是（）。

（2 分）

A

BST 与排序无关

B

BST 只能处理已排序数据

C

BST 的中序遍历就是排序结果——构建 BST 再中序遍历等于排序

D

BST 就是快速排序

原创 2026 · 单选第25题｜知识点 KJ-27i

第 26 题单选未作答

关于 BST，错误的是（）。

（2 分）

A

升序插入退化为链表

B

查找最好 $O(\log n)$

C

任何插入顺序都得到相同形态的 BST

D

中序遍历升序

原创 2026 · 单选第26题｜知识点 KJ-27i

第 27 题单选未作答

树的 DFS 序（先序遍历序）是指（）。

（2 分）

A

按结点编号从小到大

B

深度优先搜索时首次到达每个结点的顺序——即前序遍历的顺序

C

广度优先的顺序

D

随机顺序

原创 2026 · 单选第27题｜知识点 KJ-27c

第 28 题单选未作答

DFS 序的核心性质是（）。

（2 分）

A

DFS 序与结点编号相同

B

DFS 序是严格递增的

C

DFS 序长度小于结点数

D

每棵子树在 DFS 序中占据一段连续区间——子树查询变为区间查询

原创 2026 · 单选第28题｜知识点 KJ-27c

第 29 题单选未作答

树的欧拉序是指（）。

（2 分）

A

只记录叶子结点

B

DFS 遍历时进入和离开每个结点都记录一次——序列长度 $2n$ ，每个结点出现两次

C

与 DFS 序完全相同

D

按层遍历的顺序

原创 2026 · 单选第29题｜知识点 KJ-27c

第 30 题单选未作答

结点 $u$ 的子树在 DFS 序中占据的区间是（）（ $\text{in}[u]$ 为 $u$ 的 DFS 序号， $\text{sz}[u]$ 为子树大小）。

（2 分）

A

$[\text{in}[u], \text{in}[u] + \text{sz}[u] - 1]$ ——连续 $\text{sz}[u]$ 个位置

B

不确定

C

$[\text{in}[u], 2 \times \text{in}[u]]$

D

$[1, n]$

原创 2026 · 单选第30题｜知识点 KJ-27c

第 31 题单选未作答

DFS 序最重要的应用是（）。

（2 分）

A

求最短路

B

排序

C

把子树操作（修改/查询）转化为数组区间操作——配合树状数组/线段树

D

字符串匹配

原创 2026 · 单选第31题｜知识点 KJ-27c

第 32 题单选未作答

利用欧拉序求 LCA 的原理是（）。

（2 分）

A

欧拉序的第一个是 LCA

B

两点在欧拉序中首次出现位置之间深度最小的结点就是 LCA——转化为 RMQ 问题

C

欧拉序的最后一个是 LCA

D

欧拉序与 LCA 无关

原创 2026 · 单选第32题｜知识点 KJ-27c

第 33 题单选未作答

求结点 $u$ 的子树中所有点权之和，利用 DFS 序转化为（）。

（2 分）

A

最短路

B

数组上区间 $[\text{in}[u], \text{in}[u]+\text{sz}[u]-1]$ 的求和

C

不需要转化

D

图中连通块计数

原创 2026 · 单选第33题｜知识点 KJ-27c

第 34 题单选未作答

树的前序遍历序与 DFS 序的关系是（）。

（2 分）

A

完全不同

B

只对满二叉树相同

C

完全相同——DFS 序就是前序遍历的别名（在线段树/树状数组语境下习惯叫 DFS 序）

D

互为逆序

原创 2026 · 单选第34题｜知识点 KJ-27c

第 35 题单选未作答

结点 $u$ 的重儿子是指（）。

（2 分）

A

最左边的孩子

B

值最大的孩子

C

最右边的孩子

D

$u$ 的所有孩子中子树最大的那个

原创 2026 · 单选第35题｜知识点 KJ-27c

第 36 题单选未作答

树链剖分中，从任意结点到根路径上的轻边（非重链上的边）条数至多是（）。

（2 分）

A

$\sqrt{n}$

B

$O(\log n)$ ——每走一条轻边子树大小至少减半

C

$O(1)$

D

$n$

原创 2026 · 单选第36题｜知识点 KJ-27c

第 37 题单选未作答

DFS 序代码中 $\text{in}[u]$ 和 $\text{sz}[u]$ 的计算时机是（）。

（2 分）

A

$\text{in}[u]$ 在递归前赋值（计数器先加再赋）， $\text{sz}[u]$ 在递归后累加（所有孩子子树大小之和加 $1$ ）

B

都在递归前

C

不需要计算

D

都在递归后

原创 2026 · 单选第37题｜知识点 KJ-27c

第 38 题单选未作答

$7$ 个结点的满二叉树，DFS 序长度和欧拉序长度分别是（）。

（2 分）

A

$14$ 和 $7$

B

$3$ 和 $6$

C

$7$ 和 $14$

D

$7$ 和 $7$

原创 2026 · 单选第38题｜知识点 KJ-27c

第 39 题单选未作答

DFS 序为 $1, 2, 4, 5, 3, 6, 7$ 的二叉树，结点 $2$ 的子树在 DFS 序中的区间是（）。

（2 分）

A

$[2, 4]$ —— $\text{in}[2]=2$ ， $\text{sz}[2]=3$ （含 2,4,5）

B

$[2, 3]$

C

$[4, 5]$

D

$[1, 7]$

原创 2026 · 单选第39题｜知识点 KJ-27c

第 40 题单选未作答

关于 DFS 序和欧拉序，错误的是（）。

（2 分）

A

DFS 序中子树连续

B

欧拉序可用来求 LCA

C

欧拉序长度为 $2n$

D

DFS 序长度为 $2n$

原创 2026 · 单选第40题｜知识点 KJ-27c

第 41 题单选未作答

$\text{LCA}(u, v)$ （最近公共祖先）的定义是（）。

（2 分）

A

同时是 $u$ 和 $v$ 的祖先且深度最大（离 $u$ 、 $v$ 最近）的结点

B

$u$ 和 $v$ 中深度较浅的那个

C

$u$ 和 $v$ 的父结点

D

根结点

原创 2026 · 单选第41题｜知识点 KS-61l

第 42 题单选未作答

若 $w = \text{LCA}(u, v)$ ，则（）。

（2 分）

A

$w$ 一定是叶子

B

$u$ 到 $v$ 的路径必经过 $w$ ——且 $w$ 是该路径上深度最小的结点

C

$u$ 和 $v$ 一定在同一层

D

$w = u$ 或 $w = v$ 总成立

原创 2026 · 单选第42题｜知识点 KS-61l

第 43 题单选未作答

$u$ 到 $v$ 的树上路径经过 $\text{LCA}(u, v)$ ，路径表示为（）。

（2 分）

A

$u \to \text{LCA}(u,v) \to v$ ——先向上到 LCA 再向下

B

$u \to v$ 直接一条边

C

不确定

D

$u \to$ 根 $\to v$

原创 2026 · 单选第43题｜知识点 KS-61l

第 44 题单选未作答

树上 $u$ 到 $v$ 的距离（边数） $= \text{depth}[u] + \text{depth}[v] - ?$ （）。

（2 分）

A

$\text{depth}[\text{LCA}]$

B

$2 \times \text{depth}[\text{LCA}]$

C

$\text{depth}[u] \times \text{depth}[v]$

D

$0$

原创 2026 · 单选第44题｜知识点 KS-61l

第 45 题单选未作答

求 LCA 的常见方法不包括（）。

（2 分）

A

Dijkstra 最短路

B

倍增法（ $O(n \log n)$ 预处理、 $O(\log n)$ 查询）

C

Tarjan 离线算法

D

欧拉序 + RMQ

原创 2026 · 单选第45题｜知识点 KS-61l

第 46 题单选未作答

倍增求 LCA 的核心思想是（）。

（2 分）

A

预处理每个结点向上跳 $2^j$ 步到达的祖先，查询时两结点先跳到同一深度再一起向上跳——二进制分解跳步数

B

用哈希表

C

随机猜测

D

逐层向上走

原创 2026 · 单选第46题｜知识点 KS-61l

第 47 题单选未作答

利用 DFS 序判断 " $a$ 是否为 $b$ 的祖先"，条件是（）。

（2 分）

A

无法用 DFS 序判断

B

$a$ 和 $b$ 的 DFS 序号相等

C

$\text{in}[a] \le \text{in}[b]$ 且 $\text{in}[b] < \text{in}[a] + \text{sz}[a]$ —— $b$ 在 $a$ 的子树区间内

D

$a$ 的 DFS 序号小于 $b$ 即可

原创 2026 · 单选第47题｜知识点 KS-61l

第 48 题单选未作答

三点 $\text{LCA}(a, b, c)$ 的求法： $\text{LCA}(a,b,c)$ 等于（）。

（2 分）

A

$\text{LCA}(b,c)$

B

$\text{LCA}(a,b)$

C

$\text{LCA}(a,b), \text{LCA}(b,c), \text{LCA}(a,c)$ 三者中深度最大的那个（三个中两个相等且深度较浅、另一个较深）

D

根结点

原创 2026 · 单选第48题｜知识点 KS-61l

第 49 题单选未作答

已知 $\text{LCA}(12, 18) = 4$ 。下列不可能成立的是（）。（2025 年真题考法）

（2 分）

A

$\text{LCA}(12, 4) = 4$

B

$\text{LCA}(12, 1) = 4$ ——若 $1$ 是根结点则 $\text{LCA}$ 必为 $1$ （根是所有人的祖先）

C

$\text{LCA}(12, 18, 4) = 4$

D

$\text{LCA}(18, 4) = 4$

原创 2026 · 单选第49题｜知识点 KS-61l

第 50 题单选未作答

根为 $1$ 的树： $1$ 的孩子 $2, 3$ ； $2$ 的孩子 $4, 5$ ； $4$ 的孩子 $6$ 。 $\text{LCA}(5, 6) = ?$ （）。

（2 分）

A

$1$

B

$4$

C

$5$

D

$2$

原创 2026 · 单选第50题｜知识点 KS-61l

第 51 题单选未作答

LCA 在竞赛中的典型应用不包括（）。

（2 分）

A

求树上两点距离

B

树链剖分的基础

C

求图的连通分量

D

树上路径修改/查询

原创 2026 · 单选第51题｜知识点 KS-61l

第 52 题单选未作答

关于 LCA，错误的是（）。

（2 分）

A

$u$ 是 $v$ 的祖先时 $\text{LCA}(u,v) = u$

B

$\text{LCA}(u, u) = u$

C

倍增求 LCA 是 $O(\log n)$ 每次查询

D

LCA 只能有一层（不能递归求 LCA 的 LCA）

原创 2026 · 单选第52题｜知识点 KS-61l

第 53 题单选未作答

树的重心是指（）。

（2 分）

A

度数最大的结点

B

深度最大的结点

C

以该结点为根时最大子树的结点数最少的结点——删去后各连通块尽量均匀

D

值最大的结点

原创 2026 · 单选第53题｜知识点 KJ-27c

第 54 题单选未作答

关于树的重心，正确的是（）。

（2 分）

A

重心一定是叶子

B

重心到所有结点的距离之和最小

C

重心就是根

D

重心一定只有一个

原创 2026 · 单选第54题｜知识点 KJ-27c

第 55 题单选未作答

一棵树可能有多个重心。下列一定只有一个重心的是（）。（2023 年真题）

（2 分）

A

$7$ 个结点的树

B

$4$ 个结点的树

C

$6$ 个结点的树

D

$8$ 个结点的树

原创 2026 · 单选第55题｜知识点 KJ-27c

第 56 题单选未作答

求树的重心的方法是（）。

（2 分）

A

取中间结点

B

找深度最大的

C

DFS 每个结点：计算以其为根时最大子树大小（ $\max(\text{子树最大}, n - \text{sz}[u])$ ），取最小者

D

找度数最大的

原创 2026 · 单选第56题｜知识点 KJ-27c

第 57 题单选未作答

树的直径是指（）。

（2 分）

A

最深的两个叶子

B

树上任意两点间距离的最大值（最长路径的长度）

C

结点数

D

树的所有边权之和

原创 2026 · 单选第57题｜知识点 KJ-27c

第 58 题单选未作答

求树的直径的经典两次 DFS 方法的步骤是（）。

（2 分）

A

只需一次 DFS

B

Floyd

C

从任意点 DFS 找最远点 $u$ ，再从 $u$ DFS 找最远点 $v$ ， $\text{dist}(u,v)$ 即直径

D

Dijkstra

原创 2026 · 单选第58题｜知识点 KJ-27c

第 59 题单选未作答

关于树的直径，正确的是（）。

（2 分）

A

直径端点一定是度数为 $1$ 的结点以外的

B

直径一定通过根结点

C

直径等于结点数减一

D

树的直径可能不唯一（多条最长路径），但所有直径的长度相同

原创 2026 · 单选第59题｜知识点 KJ-27c

第 60 题单选未作答

树的直径与重心的关系是（）。

（2 分）

A

重心一定在直径路径上或距直径路径至多 $1$ 步

B

两者无关

C

重心一定不在直径上

D

重心就是直径的中点

原创 2026 · 单选第60题｜知识点 KJ-27c

第 61 题单选未作答

树的重心在竞赛中的典型应用是（）。

（2 分）

A

点分治的核心：每次选重心作为分治根，保证子树大小减半、递归深度 $O(\log n)$

B

拓扑排序

C

字符串匹配

D

求最短路

原创 2026 · 单选第61题｜知识点 KJ-27c

第 62 题单选未作答

树的直径在竞赛中的典型应用是（）。

（2 分）

A

排序

B

并查集

C

哈希

D

求树上最远点对、判定树的最长链、优化树上问题（如直径端点性质）

原创 2026 · 单选第62题｜知识点 KJ-27c

第 63 题单选未作答

$n$ 个结点的树，重心的最大子树大小至多是（）。

（2 分）

A

$\sqrt{n}$

B

$n-1$

C

$n$

D

$\lfloor n/2 \rfloor$ ——重心的定义保证最大子树不超过一半

原创 2026 · 单选第63题｜知识点 KJ-27c

第 64 题单选未作答

关于重心和直径，错误的是（）。

（2 分）

A

重心一定恰好在直径的正中间

B

直径可能不唯一

C

重心最大子树 $\le \lfloor n/2 \rfloor$

D

两次 DFS 可求直径

原创 2026 · 单选第64题｜知识点 KJ-27c

第 65 题单选未作答

结点 $u$ 的子树和是指（）。

（2 分）

A

$u$ 自身的权值

B

以 $u$ 为根的子树中所有结点权值之和

C

$u$ 的所有孩子权值之和

D

$u$ 到根路径上权值之和

原创 2026 · 单选第65题｜知识点 KJ-27c

第 66 题单选未作答

DFS 求子树和： $\text{sum}[u] = ?$ （）。

（2 分）

A

$\text{val}[u] + \sum_{v \in \text{children}(u)} \text{sum}[v]$ ——自身值加所有孩子子树和

B

$\text{val}[u]$

C

所有结点之和

D

$\max(\text{val}[\text{children}])$

原创 2026 · 单选第66题｜知识点 KJ-27c

第 67 题单选未作答

树上点差分：路径 $u \to v$ 上每个点权值加 $1$ ，操作是（）。

（2 分）

A

路径上每个点逐个加

B

$\text{diff}[u]{+}{+}, \text{diff}[v]{+}{+}, \text{diff}[\text{LCA}]{-}{-}, \text{diff}[\text{fa}(\text{LCA})]{-}{-}$ ——最后 DFS 回收

C

只给 $u$ 加 $1$

D

不能差分

原创 2026 · 单选第67题｜知识点 KJ-27c

第 68 题单选未作答

树上边差分与点差分的区别是（）。

（2 分）

A

边差分更复杂

B

边差分不能实现

C

边差分不需要 $\text{diff}[\text{fa}(\text{LCA})]{-}{-}$ ——只对 LCA 减一次（LCA 本身不受边影响）

D

没有区别

原创 2026 · 单选第68题｜知识点 KJ-27c

第 69 题单选未作答

树上差分后求每个点的实际值，方法是（）。

（2 分）

A

直接读 diff 数组

B

排序后取前缀和

C

不需要求

D

DFS 自底向上累加： $\text{val}[u] = \text{diff}[u] + \sum \text{val}[\text{children}]$ ——即"子树 diff 之和"

原创 2026 · 单选第69题｜知识点 KJ-27c

第 70 题单选未作答

DFS 求子树和的代码框架是（）。

（2 分）

A

01void dfs(int u) { sum[u] = val[u]; for (int v : g[u]) if (v != fa) { dfs(v); sum[u] += sum[v]; } }

B

用 BFS

C

01for (int i = 1; i <= n; ++i) sum[i] = val[i];

D

不需要代码

原创 2026 · 单选第70题｜知识点 KJ-27c

第 71 题单选未作答

树上路径 $u \to v$ 上所有点加 $w$ ，用差分实现的修改次数是（）。

（2 分）

A

$O(n \log n)$

B

$O(\log n)$

C

$O(1)$ ——只改 $4$ 个位置的 diff 值，最后 DFS 统一回收

D

$O(n)$ ——路径上逐个修改

原创 2026 · 单选第71题｜知识点 KJ-27c

第 72 题单选未作答

树上差分的最大优势是（）。

（2 分）

A

代码最短

B

多次路径修改每次只 $O(1)$ ，最后一次性 DFS 回收所有前缀和——批量高效

C

不需要 LCA

D

空间为 $O(1)$

原创 2026 · 单选第72题｜知识点 KJ-27c

第 73 题单选未作答

DFS 序中结点 $u$ 的 $\text{in}[u] = 5$ 、 $\text{sz}[u] = 4$ ， $u$ 的子树占 DFS 序区间（）。

（2 分）

A

$[4, 8]$

B

$[5, 9]$

C

$[1, 4]$

D

$[5, 8]$

原创 2026 · 单选第73题｜知识点 KJ-27c

第 74 题单选未作答

关于子树和与树上差分，错误的是（）。

（2 分）

A

子树和由 DFS 自底向上累加

B

树上差分不需要知道 LCA

C

差分回收时一次 DFS 即可

D

树上差分需 LCA

原创 2026 · 单选第74题｜知识点 KJ-27c

第 75 题单选未作答

哈夫曼树的构造过程是（）。

（2 分）

A

每次从候选集中取出权重最小的两个合并为新结点（权重=两子之和），新结点放回候选集，重复直到只剩一个

B

每次取最大的两个

C

随机组合

D

按权重排序后从大到小挂

原创 2026 · 单选第75题｜知识点 KJ-27h

第 76 题单选未作答

权重 $1, 2, 3, 4, 5$ 的哈夫曼树 WPL 是（）。

（2 分）

A

$15$

B

$20$

C

$14$

D

$33$

原创 2026 · 单选第76题｜知识点 KJ-27h

第 77 题单选未作答

权重 $1, 2, 3, 4, 5$ 的哈夫曼编码总长度（ $\sum$ 权重×深度） $=$ WPL $=$ （）。

（2 分）

A

$5$

B

$15$

C

$33$

D

$150$

原创 2026 · 单选第77题｜知识点 KJ-27h

第 78 题单选未作答

哈夫曼编码是前缀码的含义是（）。

（2 分）

A

编码按字典序排列

B

任何编码都不是另一个编码的前缀——解码时不会歧义

C

每个编码都以 $0$ 开头

D

编码长度都相同

原创 2026 · 单选第78题｜知识点 KJ-27h

第 79 题单选未作答

哈夫曼算法使用的贪心策略是（）。

（2 分）

A

每次合并当前最小的两个——权重小的深度大（编码长），权重大的深度小（编码短）

B

每次合并最大的两个

C

按顺序合并

D

随机合并

原创 2026 · 单选第79题｜知识点 KJ-27h

第 80 题单选未作答

权重 $1, 2, 3, 4, 5, 6, 7$ 的哈夫曼树 WPL 是（）。

（2 分）

A

$28$

B

$74$

C

$56$

D

$35$

原创 2026 · 单选第80题｜知识点 KJ-27h

第 81 题单选未作答

同一组权重构造的哈夫曼树（）。

（2 分）

A

WPL 可能不同

B

完全随机

C

形态唯一

D

形态可能不唯一（权重相同时选择不同），但 WPL 一定相同（最优值唯一）

原创 2026 · 单选第81题｜知识点 KJ-27h

第 82 题单选未作答

$n$ 个叶子的哈夫曼树，编码总长度取决于（）。

（2 分）

A

叶子编号

B

插入顺序

C

各叶子的权重值——权重分布越不均匀总长度越优

D

树的形态

原创 2026 · 单选第82题｜知识点 KJ-27h

第 83 题单选未作答

哈夫曼树 WPL 最小的保证来自（）。

（2 分）

A

数据量小

B

没有保证

C

贪心选择性质：最优解中权重最小的两个结点一定可以同为最深的兄弟（交换论证可证）

D

随机性

原创 2026 · 单选第83题｜知识点 KJ-27h

第 84 题单选未作答

哈夫曼构造过程中每次合并的是（）。

（2 分）

A

深度最大的两个

B

当前候选集中权重最小的两个

C

第一个和最后一个

D

任意两个

原创 2026 · 单选第84题｜知识点 KJ-27h

第 85 题单选未作答

$4$ 个叶子权重 $1, 2, 3, 4$ 的哈夫曼 WPL 是（）。

（2 分）

A

$24$

B

$14$

C

$19$

D

$10$

原创 2026 · 单选第85题｜知识点 KJ-27h

第 86 题单选未作答

关于哈夫曼树，错误的是（）。

（2 分）

A

WPL 是所有叶子深度乘权重之和

B

哈夫曼编码是前缀码

C

构造用最小堆维护候选集

D

哈夫曼树的形态一定唯一

原创 2026 · 单选第86题｜知识点 KJ-27h

第 87 题单选未作答

高度为 $h$ 的满二叉树第 $h$ 层有（）个结点。

（2 分）

A

$2^{h-1}$

B

$h$

C

$2^h$

D

$h^2$

原创 2026 · 单选第87题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 88 题单选未作答

$n$ 个结点的完全二叉树，度为 $1$ 的结点数可能是（）。

（2 分）

A

$n-1$

B

任意值

C

$0$ 或 $n/2$

D

$0$ 或 $1$ ——完全二叉树中度为 $1$ 的结点至多 $1$ 个

原创 2026 · 单选第88题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 89 题单选未作答

完全二叉树中编号为 $i$ 的结点，其右孩子编号是（）（若存在）。

（2 分）

A

$i + 2$

B

$2i$

C

$2i + 1$

D

$i + 1$

原创 2026 · 单选第89题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 90 题单选未作答

以下连通无向图中，一定可以用不超过两种颜色进行染色的是（）。（2023 年真题）

（2 分）

A

平面图

B

边双连通图

C

欧拉图

D

完全三叉树

原创 2026 · 单选第90题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 91 题单选未作答

关于树的遍历，错误的是（）。

（2 分）

A

前序=中序当且仅当只有右子树

B

前序遍历不能唯一确定一棵二叉树与其他遍历组合也不行

C

中序遍历 BST 得升序

D

后序遍历可用于释放树

原创 2026 · 单选第91题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 92 题单选未作答

关于 BST，错误的是（）。

（2 分）

A

BST 的前序遍历一定升序

B

升序插入 BST 退化为链表

C

BST 查找最好 $O(\log n)$

D

BST 中序遍历升序

原创 2026 · 单选第92题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 93 题单选未作答

关于 LCA，错误的是（）。

（2 分）

A

树上两点距离需要 LCA

B

$\text{LCA}(u, u) = u$

C

任何结点对的 LCA 都可以通过一次比较得出

D

倍增求 LCA 需要 $O(n \log n)$ 预处理

原创 2026 · 单选第93题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 94 题单选未作答

关于树的重心，错误的是（）。

（2 分）

A

重心可能有两个

B

重心最大子树 $\le \lfloor n/2 \rfloor$

C

重心到所有结点距离和最小

D

树的重心一定恰好只有一个

原创 2026 · 单选第94题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 95 题单选未作答

关于树的直径，错误的是（）。

（2 分）

A

任何树的直径都等于其高度的两倍

B

直径端点一定是叶子

C

直径可能不唯一

D

直径可由两次 DFS 求出

原创 2026 · 单选第95题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 96 题单选未作答

关于 DFS 序，错误的是（）。

（2 分）

A

DFS 序即前序遍历

B

子树在 DFS 序中连续

C

DFS 序可将子树查询转为区间查询

D

DFS 序的长度总是结点数的两倍

原创 2026 · 单选第96题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 97 题单选未作答

关于哈夫曼树，错误的是（）。

（2 分）

A

WPL 最小时编码总长度最短

B

每次合并权重最小的两个

C

哈夫曼树一定是满二叉树

D

哈夫曼编码是前缀码

原创 2026 · 单选第97题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 98 题单选未作答

关于树上差分，错误的是（）。

（2 分）

A

差分回收需要一次 DFS

B

树上差分不需要 DFS

C

点差分需要 LCA

D

路径修改每次 $O(1)$

原创 2026 · 单选第98题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 99 题单选未作答

$n$ 个结点的树，边数是（）。

（2 分）

A

$n - 1$

B

$n$

C

$n + 1$

D

$2n$

原创 2026 · 单选第99题｜知识点 KJ-27c、KJ-27i、KJ-27h

第 100 题单选未作答

关于树，错误的是（）。

（2 分）

A

$n$ 个结点的树恰有 $n-1$ 条边

B

树中一定存在环

C

树中任意两点有唯一路径

D

树是无环连通图

原创 2026 · 单选第100题｜知识点 KJ-27c、KJ-27i、KJ-27h

树二叉树 · 考纲词条练习

判分报告

客观题

重置作答

树二叉树 · 考纲词条练习

判 分 报 告

客 观 题

打印

导出 HTML 子卷

判分报告

客观题