题目导航

林老师 · 客观题题库 · 专题 S05 树与二叉树 · 复习强化

专题 S05 树与二叉树 · 复习强化

100 题 · 每题对应一个知识细节 · 全部原创

真题
复刻

试卷编号ORIG-专题S05树与二叉树-复习强化

题目总数108 题 · 100 分

试卷类型客观题

考生须知：
① 本卷共 9 大部分，合计 108 题 · 100 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。

判分报告

0 / 100 分

答对 · 得 0 分

答错 · 失 0 分

未作答

当前筛选下没有题目

壹

二叉树 S 级深入

12 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

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

（1 分）

$10$

$2021$

$11$

$12$

第 2 题 A2 未作答

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

（1 分）

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

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

只有 $1$ 个点的二叉树

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

第 3 题 A3 未作答

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

（1 分）

所有二叉树

满二叉树

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

完全二叉树

第 4 题 A4 未作答

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

（1 分）

$96$

$95$

$97$

$98$

第 5 题 A5 未作答

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

（1 分）

$\lfloor i/k \rfloor$

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

$i - k$

$\lceil i/k \rceil$

第 6 题 A6 未作答

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

（1 分）

$h^k$

$k \times h$

$k^{h-1}$

$2^h$

第 7 题 A7 未作答

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

（1 分）

$2^h - 1$

$2^{h+1}$

$2^h$

$2^{h+1} - 1$

第 8 题 A8 未作答

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

（1 分）

$2^h$

$2^{h-1}$

$0$

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

第 9 题 A9 未作答

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

（1 分）

$\sqrt{n}$

$n-1$

$n/3$

$(n+1)/2$

第 10 题 A10 未作答

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

（1 分）

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

$2i + 1 > n$

$i > n/2$

$i$ 是偶数

第 11 题 A11 未作答

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

（1 分）

$100$ 和 $100$

$99$ 和 $7$

$50$ 和 $10$

$100$ 和 $7$

第 12 题 A12 未作答

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

（1 分）

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

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

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

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

贰

二叉搜索树 BST

14 QUESTIONS · 2 POINTS EACH

第 13 题 B1 未作答

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

（1 分）

所有结点值都相同

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

是完全二叉树

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

第 14 题 B2 未作答

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

（1 分）

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

不确定

原插入顺序

降序序列

第 15 题 B3 未作答

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

（1 分）

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

随机选择位置

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

插入到根

第 16 题 B4 未作答

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

（1 分）

$O(1)$

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

$O(n \log n)$

$O(n)$

第 17 题 B5 未作答

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

（1 分）

左子树值等于根值

只有左孩子 < 根 < 右孩子

没有固定关系

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

第 18 题 B6 未作答

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

（1 分）

不确定

两者相等

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

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

第 19 题 B7 未作答

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

（1 分）

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

需要旋转

不能删除叶子

需要重建整棵树

第 20 题 B8 未作答

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

（1 分）

$\log_2 n$

$n/2$

$\sqrt{n}$

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

第 21 题 B9 未作答

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

（1 分）

$1$

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

$n/2$

$n$

第 22 题 B10 未作答

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

（1 分）

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

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

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

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

第 23 题 B11 未作答

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

（1 分）

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

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

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

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

第 24 题 B12 未作答

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

（1 分）

根结点是最大值

中序遍历结果严格递增

树是完全二叉树

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

第 25 题 B13 未作答

BST 与排序的关系是（）。

（1 分）

BST 与排序无关

BST 只能处理已排序数据

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

BST 就是快速排序

第 26 题 B14 未作答

关于 BST，错误的是（）。

（1 分）

升序插入退化为链表

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

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

中序遍历升序

叁

树的遍历与序

14 QUESTIONS · 2 POINTS EACH

第 27 题 C1 未作答

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

（1 分）

按结点编号从小到大

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

广度优先的顺序

随机顺序

第 28 题 C2 未作答

DFS 序的核心性质是（）。

（1 分）

DFS 序与结点编号相同

DFS 序是严格递增的

DFS 序长度小于结点数

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

第 29 题 C3 未作答

树的欧拉序是指（）。

（1 分）

只记录叶子结点

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

与 DFS 序完全相同

按层遍历的顺序

第 30 题 C4 未作答

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

（1 分）

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

不确定

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

$[1, n]$

第 31 题 C5 未作答

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

（1 分）

求最短路

排序

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

字符串匹配

第 32 题 C6 未作答

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

（1 分）

欧拉序的第一个是 LCA

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

欧拉序的最后一个是 LCA

欧拉序与 LCA 无关

第 33 题 C7 未作答

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

（1 分）

最短路

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

不需要转化

图中连通块计数

第 34 题 C8 未作答

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

（1 分）

完全不同

只对满二叉树相同

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

互为逆序

第 35 题 C9 未作答

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

（1 分）

最左边的孩子

值最大的孩子

最右边的孩子

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

第 36 题 C10 未作答

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

（1 分）

$\sqrt{n}$

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

$O(1)$

$n$

第 37 题 C11 未作答

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

（1 分）

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

都在递归前

不需要计算

都在递归后

第 38 题 C12 未作答

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

（1 分）

$14$ 和 $7$

$3$ 和 $6$

$7$ 和 $14$

$7$ 和 $7$

第 39 题 C13 未作答

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

（1 分）

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

$[2, 3]$

$[4, 5]$

$[1, 7]$

第 40 题 C14 未作答

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

（1 分）

DFS 序中子树连续

欧拉序可用来求 LCA

欧拉序长度为 $2n$

DFS 序长度为 $2n$

肆

LCA 最近公共祖先

12 QUESTIONS · 2 POINTS EACH

第 41 题 D1 未作答

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

（1 分）

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

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

$u$ 和 $v$ 的父结点

根结点

第 42 题 D2 未作答

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

（1 分）

$w$ 一定是叶子

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

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

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

第 43 题 D3 未作答

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

（1 分）

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

$u \to v$ 直接一条边

不确定

$u \to$ 根 $\to v$

第 44 题 D4 未作答

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

（1 分）

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

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

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

$0$

第 45 题 D5 未作答

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

（1 分）

Dijkstra 最短路

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

Tarjan 离线算法

欧拉序 + RMQ

第 46 题 D6 未作答

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

（1 分）

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

用哈希表

随机猜测

逐层向上走

第 47 题 D7 未作答

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

（1 分）

无法用 DFS 序判断

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

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

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

第 48 题 D8 未作答

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

（1 分）

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

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

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

根结点

第 49 题 D9 未作答

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

（1 分）

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

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

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

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

第 50 题 D10 未作答

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

（1 分）

$1$

$4$

$5$

$2$

第 51 题 D11 未作答

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

（1 分）

求树上两点距离

树链剖分的基础

求图的连通分量

树上路径修改/查询

第 52 题 D12 未作答

关于 LCA，错误的是（）。

（1 分）

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

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

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

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

伍

树的重心与直径

12 QUESTIONS · 2 POINTS EACH

第 53 题 E1 未作答

树的重心是指（）。

（1 分）

度数最大的结点

深度最大的结点

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

值最大的结点

第 54 题 E2 未作答

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

（1 分）

重心一定是叶子

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

重心就是根

重心一定只有一个

第 55 题 E3 未作答

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

（1 分）

$7$ 个结点的树

$4$ 个结点的树

$6$ 个结点的树

$8$ 个结点的树

第 56 题 E4 未作答

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

（1 分）

取中间结点

找深度最大的

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

找度数最大的

第 57 题 E5 未作答

树的直径是指（）。

（1 分）

最深的两个叶子

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

结点数

树的所有边权之和

第 58 题 E6 未作答

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

（1 分）

只需一次 DFS

Floyd

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

Dijkstra

第 59 题 E7 未作答

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

（1 分）

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

直径一定通过根结点

直径等于结点数减一

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

第 60 题 E8 未作答

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

（1 分）

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

两者无关

重心一定不在直径上

重心就是直径的中点

第 61 题 E9 未作答

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

（1 分）

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

拓扑排序

字符串匹配

求最短路

第 62 题 E10 未作答

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

（1 分）

排序

并查集

哈希

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

第 63 题 E11 未作答

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

（1 分）

$\sqrt{n}$

$n-1$

$n$

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

第 64 题 E12 未作答

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

（1 分）

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

直径可能不唯一

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

两次 DFS 可求直径

陆

树上差分与子树和

10 QUESTIONS · 2 POINTS EACH

第 65 题 F1 未作答

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

（1 分）

$u$ 自身的权值

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

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

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

第 66 题 F2 未作答

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

（1 分）

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

$\text{val}[u]$

所有结点之和

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

第 67 题 F3 未作答

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

（1 分）

路径上每个点逐个加

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

只给 $u$ 加 $1$

不能差分

第 68 题 F4 未作答

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

（1 分）

边差分更复杂

边差分不能实现

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

没有区别

第 69 题 F5 未作答

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

（1 分）

直接读 diff 数组

排序后取前缀和

不需要求

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

第 70 题 F6 未作答

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

（1 分）

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

用 BFS

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

不需要代码

第 71 题 F7 未作答

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

（1 分）

$O(n \log n)$

$O(\log n)$

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

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

第 72 题 F8 未作答

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

（1 分）

代码最短

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

不需要 LCA

空间为 $O(1)$

第 73 题 F9 未作答

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

（1 分）

$[4, 8]$

$[5, 9]$

$[1, 4]$

$[5, 8]$

第 74 题 F10 未作答

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

（1 分）

子树和由 DFS 自底向上累加

树上差分不需要知道 LCA

差分回收时一次 DFS 即可

树上差分需 LCA

柒

哈夫曼 S 级

12 QUESTIONS · 2 POINTS EACH

第 75 题 G1 未作答

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

（1 分）

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

每次取最大的两个

随机组合

按权重排序后从大到小挂

第 76 题 G2 未作答

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

（1 分）

$15$

$20$

$14$

$33$

第 77 题 G3 未作答

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

（1 分）

$5$

$15$

$33$

$150$

第 78 题 G4 未作答

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

（1 分）

编码按字典序排列

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

每个编码都以 $0$ 开头

编码长度都相同

第 79 题 G5 未作答

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

（1 分）

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

每次合并最大的两个

按顺序合并

随机合并

第 80 题 G6 未作答

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

（1 分）

$28$

$74$

$56$

$35$

第 81 题 G7 未作答

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

（1 分）

WPL 可能不同

完全随机

形态唯一

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

第 82 题 G8 未作答

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

（1 分）

叶子编号

插入顺序

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

树的形态

第 83 题 G9 未作答

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

（1 分）

数据量小

没有保证

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

随机性

第 84 题 G10 未作答

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

（1 分）

深度最大的两个

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

第一个和最后一个

任意两个

第 85 题 G11 未作答

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

（1 分）

$24$

$14$

$19$

$10$

第 86 题 G12 未作答

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

（1 分）

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

哈夫曼编码是前缀码

构造用最小堆维护候选集

哈夫曼树的形态一定唯一

捌

综合与真题

14 QUESTIONS · 2 POINTS EACH

第 87 题 H1 未作答

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

（1 分）

$2^{h-1}$

$h$

$2^h$

$h^2$

第 88 题 H2 未作答

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

（1 分）

$n-1$

任意值

$0$ 或 $n/2$

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

第 89 题 H3 未作答

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

（1 分）

$i + 2$

$2i$

$2i + 1$

$i + 1$

第 90 题 H4 未作答

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

（1 分）

平面图

边双连通图

欧拉图

完全三叉树

第 91 题 H5 未作答

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

（1 分）

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

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

中序遍历 BST 得升序

后序遍历可用于释放树

第 92 题 H6 未作答

关于 BST，错误的是（）。

（1 分）

BST 的前序遍历一定升序

升序插入 BST 退化为链表

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

BST 中序遍历升序

第 93 题 H7 未作答

关于 LCA，错误的是（）。

（1 分）

树上两点距离需要 LCA

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

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

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

第 94 题 H8 未作答

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

（1 分）

重心可能有两个

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

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

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

第 95 题 H9 未作答

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

（1 分）

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

直径端点一定是叶子

直径可能不唯一

直径可由两次 DFS 求出

第 96 题 H10 未作答

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

（1 分）

DFS 序即前序遍历

子树在 DFS 序中连续

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

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

第 97 题 H11 未作答

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

（1 分）

WPL 最小时编码总长度最短

每次合并权重最小的两个

哈夫曼树一定是满二叉树

哈夫曼编码是前缀码

第 98 题 H12 未作答

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

（1 分）

差分回收需要一次 DFS

树上差分不需要 DFS

点差分需要 LCA

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

第 99 题 H13 未作答

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

（1 分）

$n - 1$

$n$

$n + 1$

$2n$

第 100 题 H14 未作答

关于树，错误的是（）。

（1 分）

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

树中一定存在环

树中任意两点有唯一路径

树是无环连通图

玖

真题演练

8 QUESTIONS · 真题演练不计分

第 1 题单选未作答

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

（0 分）

$10$

$11$

$12$

$2021$

CSP-S 2021 · 单选第8题｜知识点完全二叉树、完全二叉树

第 2 题单选未作答

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

（0 分）

只有 $1$ 个点的二叉树

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

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

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

CSP-S 2021 · 单选第9题｜知识点二叉树概念、二叉树概念

第 3 题单选未作答

一个深度为 $5$ （根结点深度为 $1$ ）的完全 $3$ 叉树，按前序遍历的顺序给结点从 $1$ 开始编号，则第 $100$ 号结点的父结点是第（）号。

（0 分）

$95$

$96$

$97$

$98$

CSP-S 2022 · 单选第7题｜知识点二叉树概念、二叉树性质

第 4 题单选未作答

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

（0 分）

完全三叉树

平面图

边双连通图

欧拉图

CSP-S 2023 · 单选第6题｜知识点邻接矩阵、二叉树性质

第 5 题单选未作答

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。下面哪种树一定只有一个重心？（）

（0 分）

$4$ 个结点的树

$6$ 个结点的树

$7$ 个结点的树

$8$ 个结点的树

CSP-S 2023 · 单选第12题｜知识点二叉树性质、二叉树性质

第 6 题单选未作答

假设有一棵 $h$ 层的完全二叉树，该树最多包含多少个结点？

（0 分）

$2^h - 1$

$2^{h+1} - 1$

$2^h$

$2^{h+1}$

CSP-S 2024 · 单选第11题｜知识点完全二叉树、二叉树性质

第 7 题单选未作答

如果一棵二叉搜索树的后序遍历序列是 $2, 5, 4, 8, 12, 10, 6$ ，那么该树的前序遍历是什么？

（0 分）

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

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

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

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

CSP-S 2025 · 单选第8题｜知识点满二叉树、二叉树概念、二叉树概念

第 8 题单选未作答

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（ $LCA$ ）是结点 $4$ 。那么下列哪个结点的 $LCA$ 组合是不可能出现的？

（0 分）

$LCA(12, 4) = 4$

$LCA(18, 4) = 4$

$LCA(12, 18, 4) = 4$

$LCA(12, 1) = 4$

CSP-S 2025 · 单选第10题｜知识点线性DP、二叉树性质

重置作答

专题 S05 树与二叉树 · 复习强化

判 分 报 告

二叉树 S 级深入

二叉搜索树 BST

树的遍历与序

LCA 最近公共祖先

树的重心与直径

树上差分与子树和

哈夫曼 S 级

综合与真题

真 题 演 练

打印

导出 HTML 子卷

判分报告

真题演练