数据结构¶
方法速览¶
| 任务 | 方法 | 口诀 |
|---|---|---|
| 哈希线性探查 | 冲突就 +1 往后找空位（到尾绕回 0） | 撞了往后挪 |
| 最小堆插删 | 插入上浮、删除堆顶末元素下沉 | 插上沉、删下沉 |
| BST 还原 | 后序末位 / 前序首位定根，按大小切左右 | 定根切半 |
| 完全二叉树 h 层 | 最多 \(2^h - 1\) 个结点 | 层满减一 |
| 线段树查询 | 整段覆盖即停，半覆盖下推——数访问结点 | 整段停、半段推 |
| Trie 结点数 | 所有插入串的互异前缀数 + 1（根） | 数前缀加根 |
| LCA | 祖先的传递：$LCA(u,\text{根}) = $ 根 | 与根的 LCA 是根 |
哈希表与线性探查¶
哈希函数 \(h(x)\) 把关键字映射到地址；不同关键字撞到同一地址 = 冲突。
线性探查：\(h(x)\) 被占就试 \(h(x)+1,\ h(x)+2,\dots\)（到表尾绕回 0），找到第一个空位放下。
【例】（2022 真题）表长 10、\(h(x) = x \bmod 10\)，依次插 (71, 23, 73, 99, 44, 79, 89)：
| 关键字 | h(x) | 探查路径 | 落点 |
|---|---|---|---|
| 71 | 1 | 1 空 | 1 |
| 23 | 3 | 3 空 | 3 |
| 73 | 3 | 3 占 → 4 | 4 |
| 99 | 9 | 9 空 | 9 |
| 44 | 4 | 4、5 | 5 |
| 79 | 9 | 9、0（绕回） | 0 |
| 89 | 9 | 9、0、1、2 | 2 |
装载因子 \(\alpha = \dfrac{\text{元素数}}{\text{表长}}\)：开放定址法平均查找代价 \(\dfrac{1}{1-\alpha}\)，但最坏（全挤在一起）是 \(O(n)\)。
选无冲突哈希函数（2020 真题型）：把候选函数逐个算一遍四个值，看是否互异。
堆（优先队列）¶
最小堆：父 ≤ 孩子；数组存，push 尾部上浮、pop 堆顶换末下沉。
【例】（2025 真题）空最小堆依次插 \(20,12,15,8,10,5\)：
| 步骤 | 动作 | 堆数组（层序） |
|---|---|---|
| 插 20 | — | [20] |
| 插 12 | 12 < 20 上浮 | [12, 20] |
| 插 15 | 15 < 20 上浮 | [12, 20, 15] |
| 插 8 | 8 上浮到顶 | [8, 12, 15, 20] |
| 插 10 | 10 < 20 上浮 | [8, 10, 15, 20, 12] |
| 插 5 | 5 上浮到顶 | [5, 10, 8, 20, 12, 15] |
delete-min 两次（弹 5、弹 8）后堆顶 = 10。priority_queue 默认大根堆，小根要 greater<int>。
BST 与遍历还原¶
中序 = 升序；后序末位是根，小于根的是左子树、大于根的是右子树。
【例】（2025 真题）后序 2, 5, 4, 8, 12, 10, 6 求前序：
| 步骤 | 根 | 切分 |
|---|---|---|
| 1 | 6 | 左 \(\{2,5,4\}\)、右 \(\{8,12,10\}\) |
| 2（左） | 4 | 左 \(\{2\}\)、右 \(\{5\}\) |
| 3（右） | 10 | 左 \(\{8\}\)、右 \(\{12\}\) |
前序 = 根 + 左 + 右 = 6, 4, 2, 5, 10, 8, 12。
前序 = 中序的树：中序“左根右”要等于前序“根左右”，只有左子树恒空（每结点只有右孩子）才行。
完全二叉树与完全三叉树¶
- h 层完全二叉树最多 \(2^h - 1\) 个结点；
- n 个结点的二叉树高度至少 \(\lceil \log_2(n+1) \rceil\)（2021 真题：2021 个结点 → 11）；
- 完全三叉树前序编号：前序下结点 k 的孩子从 \(k+1\) 起、第 i 个孩子 = \(k + 1 + (i-1)\cdot\dfrac{3^d-1}{2}\)（d 为孩子子树深度）——考场上更快的办法是按前序模拟数格子（2022 真题：100 号的父 = 97）。
线段树、Trie 与 LCA¶
线段树查询：结点区间被查询区间完全包含 → 计数 1 停；部分相交 → 计数 1 并下推两孩子。
【例】（2025 真题）16 叶满线段树查 [3,11]：拆成 \([3,3]+[4,7]+[8,11]\) 三段整覆盖——路径与覆盖结点共 8 个。
Trie 结点数 = 所有串的互异前缀数 + 1（根）。cat/car/cart/case/dog/do：前缀 c、ca、cat、car、cart、cas、case、d、do、dog 共 10 → 11 结点。
LCA 三条性质：
- \(LCA(u, v) = w\) 且 \(w\) 是 \(u\) 的祖先 ⟹ \(LCA(u, w) = w\)；
- \(LCA(u, \text{根}) = \text{根}\)（根是所有人的祖先）；
- \(LCA(LCA(a,b),c) = LCA(a,b,c)\)（可结合）。
练习题目¶
练习 1 · 线性探查¶
题目
表长 7、\(h(x) = x \bmod 7\)，线性探查依次插 15, 22, 29，29 落在（ ）号位。
- A. \(1\)
- B. \(2\)
- C. \(3\)
- D. \(0\)
答案与解析
答案：C
\(15 \bmod 7 = 1\) 落 1；\(22 \bmod 7 = 1\) 冲突落 2；\(29 \bmod 7 = 1\) 冲突，探 1（占）、2（占）→ 落 3。
干扰项思路：A 忘了 22 先占了 1；D 误以为探查失败绕回 0。
练习 2 · 线性探查（绕回）¶
题目
表长 7、\(h(x) = x \bmod 7\)，依次插 7, 14, 21，21 落在（ ）。
- A. \(3\)
- B. \(0\)
- C. \(2\)
- D. \(1\)
答案与解析
答案：C
\(7 \bmod 7 = 0\) 落 0；\(14 \bmod 7 = 0\) 冲突落 1；\(21 \bmod 7 = 0\) 冲突，探 0（占）、1（占）、2（空）→ 落 2。
干扰项思路：D 少探了一步停在 1；B 误以为 mod 7 结果为 0 就绕回。
练习 3 · 探查链¶
题目
表长 11、\(h(x)=x \bmod 11\)，依次插 11, 22, 33, 44，44 探查的地址序列是（ ）
- A. \(0\) 一次成功
- B. \(0 \to 1 \to 2\)
- C. \(1 \to 2 \to 3 \to 4\)
- D. \(0 \to 1 \to 2 \to 3\)
答案与解析
答案：D
11→0、22→0 冲突落 1、33→0/1 占落 2；44 探 0（占）→1（占）→2（占）→3（空）落 3——冲突越多链越长，这就是堆积（聚集）现象。
练习 4 · 装载因子¶
题目
哈希表装载因子 \(\alpha\) 越接近 1，则（ ）
- A. 冲突越少
- B. 查询变快
- C. 冲突越频繁、平均探查越长
- D. 没有影响
答案与解析
答案：C
\(\alpha = n/\text{表长}\)：表快满时空位稀少，探查链拉长——所以要扩容（rehash）保住 \(\alpha\)。
练习 5 · 开放定址最坏复杂度¶
题目
开放定址法哈希表，最坏情况查找一个元素的时间复杂度是（ ）
- A. \(O(1)\)
- B. \(O(\log n)\)
- C. \(O(n)\)
- D. \(O(1/(1-\alpha))\)
答案与解析
答案：C
所有元素挤成一条探查链时挨个试——\(O(n)\)；\(1/(1-\alpha)\) 只是平均情形。
练习 6 · 最小堆插入¶
题目
空最小堆依次插 5, 3, 8 后的堆数组（层序）是（ ）
- A.
[5, 3, 8] - B.
[5, 8, 3] - C.
[3, 8, 5] - D.
[3, 5, 8]
答案与解析
答案：D
插 5；插 3：3 < 5 上浮 → [3,5]；插 8：8 > 3 不动 → [3,5,8]。
练习 7 · delete-min¶
题目
最小堆 [2, 4, 3, 9, 6] 执行一次 delete-min 后堆顶是（ ）
- A. \(3\)
- B. \(4\)
- C. \(6\)
- D. \(9\)
答案与解析
答案：A
弹 2 后末元素 6 接顶：6 与孩子 4、3 中较小者 3 交换 → [3,4,6,9]，堆顶 3。
干扰项思路：B 忘了下沉、以为次小值自动上顶。
练习 8 · 大根堆判断¶
题目
数组 [90, 70, 80, 30, 40, 60]（层序）是大根堆吗？再插 85 上浮到哪层？
- A. 不是
- B. 是；85 升到第 2 层
- C. 是；85 留在第 4 层
- D. 是；85 升到根
答案与解析
答案：B
每个父 ≥ 孩子（90≥70,80；70≥30,40；80≥60）✓。插 85 在 30 下：85 > 30 上浮，85 < 90 停——落在第 2 层（70 的位置被顶替后 70 下沉）。
练习 9 · BST 后序还原¶
题目
BST 后序 1, 3, 2, 5, 7, 6, 4 的根与左子树是（ ）
- A. 根 1，左子树为空
- B. 根 6，左子树 \(\{1,3,2,5\}\)
- C. 根 4，左子树 \(\{1,3,2,5\}\)
- D. 根 4，左子树 \(\{1,3,2\}\)
答案与解析
答案：D
后序末位 4 为根；小于 4 的 \(\{1,3,2\}\) 是左子树、\(\{5,7,6\}\) 是右子树。
练习 10 · BST 查找¶
题目
BST 中查找值为 x 的结点，比较次数不超过（ ）
- A. 树的高度
- B. 结点数
- C. 度数
- D. 叶子数
答案与解析
答案：A
每比较一次下一层；最坏走一条根到叶的路径——这就是 BST 期望 \(O(\log n)\)、退化 \(O(n)\)（链形）的原因。
练习 11 · 完全二叉树结点上限¶
题目
6 层完全二叉树最多（ ）个结点。
- A. \(64\)
- B. \(63\)
- C. \(32\)
- D. \(127\)
答案与解析
答案：B
\(2^6 - 1 = 63\)；A 是 \(2^6\)（多数一层少减一）。
练习 12 · 高度下界¶
题目
1000 个结点的二叉树高度至少为（ ）
- A. \(9\)
- B. \(11\)
- C. \(1000\)
- D. \(10\)
答案与解析
答案：D
\(\lceil \log_2 1001 \rceil = 10\)（\(2^9 = 512 < 1000 \le 1024 = 2^{10}\)）。
练习 13 · 前序 = 中序¶
题目
一棵二叉树前序遍历与中序遍历完全相同，则它（ ）
- A. 每个结点只有右孩子
- B. 每个结点只有左孩子
- C. 是满二叉树
- D. 只有一个结点
答案与解析
答案：A
前序根左右、中序左根右，要相等只能左恒空；只有左孩子的树前序“根左”与中序“左根”恰好互为倒序。
练习 14 · 后序 = 中序¶
题目
一棵二叉树后序遍历与中序遍历完全相同，则它（ ）
- A. 每个结点只有右孩子
- B. 每个结点只有左孩子
- C. 是完全二叉树
- D. 不存在这样的树
答案与解析
答案：B
后序左右根、中序左根右，要相等只能右恒空——与上一题互为镜像。
练习 15 · 线段树单点性质¶
题目
n 个元素的线段树高度为 \(O(\log n)\)，因为（ ）
- A. 每层区间长度减半
- B. 它是完全平衡的二叉树且每往下一层区间折半
- C. 元素有序
- D. 它是链
答案与解析
答案：B
区间折半 → 层数 \(\log n\) → 单点修改/区间查询都沿一条 log 级路径。
练习 16 · Trie 结点数（小例）¶
题目
将 he, she 插入空 Trie（含根），结点总数是（ ）
- A. \(5\)
- B. \(6\)
- C. \(4\)
- D. \(7\)
答案与解析
答案：B
互异前缀：he 贡献 h、he；she 贡献 s、sh、she——共 5 个前缀，加根 1 个 = 6。
干扰项思路：A 忘了数根结点。
练习 17 · Trie 的查找¶
题目
在 Trie 中查找一个长度为 m 的串，时间复杂度（ ）
- A. \(O(m)\)
- B. \(O(m \log \sigma)\)
- C. \(O(\text{串总数})\)
- D. \(O(m^2)\)
答案与解析
答案：A
每个字符沿边走一步、共 m 步——与库里存了多少串无关（哈希/数组转移 \(O(1)\)）。
练习 18 · LCA 传递性¶
题目
\(LCA(x, y) = z\) 且 \(z\) 是 \(x\) 的祖先，则 \(LCA(x, z) = (\) ）
- A. 根
- B. \(x\)
- C. \(z\)
- D. 不确定
答案与解析
答案：C
z 是 x 的祖先时两者的最近公共祖先就是 z 本身——“到祖先的 LCA 是祖先”。
练习 19 · LCA 与根¶
题目
树中任意非根结点 u 与根 r 的 \(LCA(u, r)\) 是（ ）
- A. \(u\)
- B. \(u\) 的孩子
- C. 不确定
- D. \(r\)
答案与解析
答案：D
根是所有结点的祖先，最近公共祖先就是根——2025 真题 D 项正是违反了这条。
练习 20 · LCA 结合性¶
题目
\(LCA(LCA(a,b), c)\) 等于（ ）
- A. \(LCA(a, LCA(b,c))\)
- B. \(LCA(a, b)\)
- C. \(LCA(a, c)\)
- D. 三者中最深的结点
答案与解析
答案：A
LCA 满足结合律：三个点的公共最近祖先与结合顺序无关，都等于 \(LCA(a,b,c)\)。
练习 21 · 栈的操作模拟¶
题目
空栈依次执行：push a、push b、pop、push c、push d、pop，此时栈底到栈顶（ ）
- A.
a c d - B.
a b - C.
c d - D.
a c
答案与解析
答案：D
push a,b → pop 弹 b → push c,d → pop 弹 d：剩 a c。
练习 22 · 连续退栈限制¶
题目
a,b,c,d,e,f 依次进栈、可交替进出，但不允许连续三次退栈。序列 f e d c b a（ ）
- A. 可行
- B. 不可行：它要求全部压完后连弹六次
- C. 可行但只一种方式
- D. 不可行：f 不能第一个出
答案与解析
答案：B
要 f 先出必须六个全压栈，随后连弹 6 次——远超“不许连续三次”的红线（2022 真题 D 项同型）。
练习 23 · BFS 的结构¶
题目
广度优先搜索（BFS）一定用到的数据结构是（ ）
- A. 栈
- B. 队列
- C. 堆
- D. 并查集
答案与解析
答案：B
一层层扩展 = 先发现先处理 = 队列；DFS 才是栈（递归栈）。
练习 24 · 二分查找前提¶
题目
对数组进行二分查找，必须满足（ ）
- A. 元素互不相同
- B. 数组长度是 2 的幂
- C. 数组有序
- D. 元素都是整数
答案与解析
答案：C
有序才能每比较一次砍对半；长度任意、可重复、浮点也行。
练习 25 · 开散列与闭散列¶
题目
哈希冲突解决中，“拉链法”属于（ ）
- A. 开散列（同地址元素链成表）
- B. 闭散列（在表内探查空位）
- C. 再哈希
- D. 溢出表
答案与解析
答案：A
开散列 = 链地址法（桶外挂链）；闭散列 = 开放定址（线性探查在表内挪）——两大流派。
练习 26 · 数据结构表述¶
题目
下列表述不恰当的是（ ）
- A. 队列是先进先出的线性结构
- B. 哈夫曼树的构造过程主要为了实现图的深度优先搜索
- C. 散列表通过散列函数把关键字映射到存储位置
- D. 二叉树每个结点最多两个子结点
答案与解析
答案：B
哈夫曼树服务于编码压缩（WPL 最小），与 DFS 毫无关系。
练习 27 · 完全三叉树编号¶
题目
深度 5 的完全三叉树共（ ）个结点；前序编号下第 1 号是（ ）
- A. \(121\)；根
- B. \(120\)；根
- C. \(121\)；最左叶
- D. \(243\)；根
答案与解析
答案：A
\(1+3+9+27+81 = \dfrac{3^5-1}{2} = 121\)；前序编号从根开始（根 = 1 号）。
历年真题¶
2020 年 · 第 4 题¶
题目
今有一空栈 \(S\)，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行：进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈底元素为（ ）。
- A.
b - B.
a - C.
d - D.
c
答案与解析
答案：B
进 a、进 b → 弹 b；进 c、进 d → 弹 d。剩 a c e f（c 在 a 上）——栈底永远是最先进来没被弹掉的 a。
2020 年 · 第 5 题¶
题目
将 \((2,7,10,18)\) 分别存储到某个地址区间为 \(0\sim10\) 的哈希表中，如果哈希函数 \(h(x)=\)（ ），将不会产生冲突。
- A. \(x^2\bmod11\)
- B. \(2x\bmod11\)
- C. \(x\bmod11\)
- D. \([x/2]\bmod11\)，其中 \([x/2]\) 表示 \(x/2\) 下取整
答案与解析
答案：D
逐个代入算四个关键字：
| 候选 | \((2,7,10,18)\) 的像 | 冲突？ |
|---|---|---|
| A \(x^2\bmod 11\) | \(4, 5, 1, 5\) | 7、18 撞 5 ✗ |
| B \(2x\bmod 11\) | \(4, 3, 9, 3\) | 7、18 撞 3 ✗ |
| C \(x\bmod 11\) | \(2, 7, 10, 7\) | 7、18 撞 7 ✗ |
| D \(\lfloor x/2\rfloor\bmod 11\) | \(1, 3, 5, 9\) | 互异 ✓ |
2020 年 · 第 9 题¶
题目
广度优先搜索时，一定需要用到的数据结构是（ ）。
- A. 栈
- B. 二叉树
- C. 队列
- D. 哈希表
答案与解析
答案：C
层序扩展，先进先处理。
2021 年 · 第 6 题¶
题目
现有一个地址区间为 \(0\sim10\) 的哈希表，对于出现冲突的情况，会往后找第一个空的地址存储（到 \(10\) 冲突了就从 \(0\) 开始往后）。现在要依次存储 \((0,1,2,3,4,5,6,7)\)，哈希函数为 \(h(x)=x^2\bmod 11\)。请问 \(7\) 存储在哈希表哪个地址中（ ）。
- A. \(5\)
- B. \(6\)
- C. \(7\)
- D. \(8\)
答案与解析
答案：C
\(x^2 \bmod 11\)：\(0,1,4,9,5,3,3,5\)。放 0→0、1→1、2→4、3→9、4→5、5→3；6→3、4、5 全占落 6；7→5、6 全占，落 7。
2021 年 · 第 8 题¶
题目
令根结点的高度为 \(1\)，则一棵含有 \(2021\) 个结点的二叉树的高度至少为（ ）。
- A. \(10\)
- B. \(11\)
- C. \(12\)
- D. \(2021\)
答案与解析
答案：B
高 h 最多 \(2^h-1\) 个：\(2^{10}-1 = 1023 < 2021 \le 2047 = 2^{11}-1\) → 至少 11。
2021 年 · 第 9 题¶
题目
前序遍历和中序遍历相同的二叉树为且仅为（ ）。
- A. 只有 \(1\) 个点的二叉树
- B. 根结点没有左子树的二叉树
- C. 非叶子结点只有左子树的二叉树
- D. 非叶子结点只有右子树的二叉树
答案与解析
答案：D
前序根左右 = 中序左根右，必须左子树恒空——每个非叶结点只有右孩子（B 只说根，是必要不充分）。
2022 年 · 第 3 题¶
题目
若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（ ）。
- A.
dcebfa - B.
cbdaef - C.
bcaefd - D.
afedcb
答案与解析
答案：D
afedcb：f 先出 ⇒ 六个全压栈，随后 连弹 6 次，违反不许连三；A/B/C 的退栈都被入栈隔开。
2022 年 · 第 7 题¶
题目
一个深度为 \(5\)（根结点深度为 \(1\)）的完全 \(3\) 叉树，按前序遍历的顺序给结点从 \(1\) 开始编号，则第 \(100\) 号结点的父结点是第（ ）号。
- A. \(95\)
- B. \(96\)
- C. \(97\)
- D. \(98\)
答案与解析
答案：C
前序模拟：结点 k 的孩子从 \(k+1\) 起连续编；孩子 i 的编号 = \(k + 1 + (\text{前面兄段子树大小})\)。逐层定位（或程序模拟前序）：100 号的父 = 97。
2022 年 · 第 12 题¶
题目
给定地址区间为 \(0\sim9\) 的哈希表，哈希函数为 \(h(x)=x\%10\)，采用线性探查的冲突解决策略。哈希表初始为空表，依次存储 (71, 23, 73, 99, 44, 79, 89) 后，请问 89 存储在哈希表哪个地址中。（ ）
- A. \(9\)
- B. \(0\)
- C. \(1\)
- D. \(2\)
答案与解析
答案：D
71→1；23→3；73→3 占落 4；99→9；44→4 占落 5；79→9 占绕回 0；89→9 占、0 占、1 占、2 空 → 落 2（完整探查表见教学节）。
2023 年 · 第 5 题¶
题目
以下对数据结构的表述不恰当的一项是（ ）。
- A. 队列是一种先进先出（
FIFO）的线性结构。 - B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索。
- C. 散列表是一种通过散列函数将关键字映射到存储位置的数据结构。
- D. 二叉树是一种每个结点最多有两个子结点的树结构。
答案与解析
答案：B
哈夫曼树 = 带权路径长度最小的编码树，与 DFS 无关。
2024 年 · 第 5 题¶
题目
下面哪个数据结构最适合实现先进先出（FIFO）的功能？
- A. 栈
- B. 队列
- C. 线性表
- D. 二叉搜索树
答案与解析
答案：B
队列的定义就是 FIFO；栈是 LIFO。
2024 年 · 第 8 题¶
题目
对数组进行二分查找的过程中，以下哪个条件必须满足？（ ）
- A. 数组必须是有序的
- B. 数组必须是无序的
- C. 数组长度必须是 \(2\) 的幂
- D. 数组中的元素必须是整数
答案与解析
答案：A
有序是砍半的依据；长度、元素类型都无要求。
2024 年 · 第 10 题¶
题目
在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 \(n\) 个键值对，表的装载因子为 \(a\)（\(0 < a \le 1\)）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为？
- A. \(O(1)\)
- B. \(O(\log n)\)
- C. \(O\left(\frac{1}{1 - a}\right)\)
- D. \(O(n)\)
答案与解析
答案：D
最坏全挤成一条链：挨个探查 \(O(n)\)；\(1/(1-a)\) 是平均代价。
2024 年 · 第 11 题¶
题目
假设有一棵 \(h\) 层的完全二叉树，该树最多包含多少个结点？
- A. \(2^h - 1\)
- B. \(2^{h+1} - 1\)
- C. \(2^h\)
- D. \(2^{h+1}\)
答案与解析
答案：A
每层取满 \(1+2+\cdots+2^{h-1} = 2^h-1\)。
2025 年 · 第 3 题¶
题目
对一个大小为 \(16\)（下标 \(0\)-\(15\)）的数组上构建满线段树。查询区间 [3, 11] 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？
- A. \(7\)
- B. \(8\)
- C. \(9\)
- D. \(10\)
答案与解析
答案：B
\([3,11]\) 拆成整覆盖段 \([3,3],[4,7],[8,11]\)：从根下推的两条路径结点 + 三个覆盖段，递归计数共 8。
2025 年 · 第 4 题¶
题目
将字符串 "cat"、"car"、"cart"、"case"、"dog"、"do" 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？
- A. \(8\)
- B. \(9\)
- C. \(10\)
- D. \(11\)
答案与解析
答案：D
互异前缀：c、ca、cat、car、cart、cas、case、d、do、dog 共 10，加根 = 11。
2025 年 · 第 8 题¶
题目
如果一棵二叉搜索树的后序遍历序列是 \(2, 5, 4, 8, 12, 10, 6\)，那么该树的前序遍历是什么？
- A.
6, 4, 2, 5, 10, 8, 12 - B.
6, 4, 5, 2, 10, 12, 8 - C.
2, 4, 5, 6, 8, 10, 12 - D.
4, 2, 5, 10, 8, 12, 6
答案与解析
答案：A
后序末位 6 为根：左 \(\{2,5,4\}\) 右 \(\{8,12,10\}\)；左子树后序 2,5,4 → 根 4（左 2 右 5）；右子树后序 8,12,10 → 根 10（左 8 右 12）。前序 = 6 + (4,2,5) + (10,8,12)。
2025 年 · 第 10 题¶
题目
在一棵以结点 \(1\) 为根的树中，结点 \(12\) 和结点 \(18\) 的最近公共祖先（\(LCA\)）是结点 \(4\)。那么下列哪个结点的 \(LCA\) 组合是不可能出现的？
- A. \(LCA(12, 4) = 4\)
- B. \(LCA(18, 4) = 4\)
- C. \(LCA(12, 18, 4) = 4\)
- D. \(LCA(12, 1) = 4\)
答案与解析
答案：D
根 1 是 12 的祖先：\(LCA(12, 1) = 1\)，不可能是 4；A/B/C 符合“与祖先的 LCA 是祖先”及结合律。
2025 年 · 第 12 题¶
题目
在一个初始为空的最小堆（min-heap）中，依次插入元素 \(20, 12, 15, 8, 10, 5\)。然后连续执行两次删除最小值（delete-min）操作。请问此时堆顶元素是什么？
- A. \(10\)
- B. \(12\)
- C. \(15\)
- D. \(20\)
答案与解析
答案：A
插完堆为 [5,10,8,20,12,15]（完整上浮表见教学节）；弹 5（20 接顶下沉换 8→10）、再弹 8：堆顶剩 10，堆 [10,12,15,20]。
易错小结¶
- 线性探查撞了 +1 往后、到尾绕回 0——逐关键字号列表格，别跳步（2021/2022 两年原题）；装载因子高会堆积；
- 最坏哈希查找 \(O(n)\)、平均 \(O(1/(1-\alpha))\)——问“最坏”别答平均；
- 最小堆：插入上浮、删顶末元素接顶下沉；
priority_queue默认大根； - BST 还原看后序末位/前序首位 + 按大小切分；前序=中序 ⟺ 只有右链、后序=中序 ⟺ 只有左链；
- h 层完全二叉树最多 \(2^h-1\)；n 点高度至少 \(\lceil\log_2(n+1)\rceil\)；
- 线段树查询数结点：整覆盖停、半覆盖下推；Trie 结点 = 互异前缀 + 根；
- LCA：与根的 LCA 是根、与祖先的 LCA 是该祖先、可结合；
- 无限递归 / 大数组递归 = 栈溢出（2021/2024 两次）；BFS 用队列、DFS 用栈。