手推与逐步模拟：答案是一张过程表

Intro

数据结构的两道大题里，一道通常是算法设计题，另一道有一多半年份是这个专题（18 年里 10 年）：不用写代码，但要你把一个过程从头到尾走一遍。

关键路径、Prim、Kruskal、散列表构造、置换-选择排序、出栈序列——名字来自五六个不同的章节，做起来却是同一件事。

规则是死的，变的只是状态

把这十道题的标准答案并排看，它们共享同一个结构：

一个确定的规则，反复施加在一个逐渐变化的状态上。

每一步该干什么完全没有选择余地——Prim 每轮挑最小的横切边，线性探测每次冲突就往后挪一格，置换-选择每轮输出「不小于上一个输出值的最小者」。规则本身不难，难的是把状态老老实实记下来。

由此直接得到这类题该有的下笔方式：

画一张表，一行一步，每一行写下这一步之后的完整状态。

不要心算，不要只在草稿纸上跳着写关键几步。过程题那部分的失分，几乎全来自中间某一轮抄错，而不是不会。

（这一组也不全是过程题：出栈序列那道有一半分在卡特兰数的推导上，外部排序那道有一问要论证归并段长度的上下界，比较计数排序那道要判稳定性——这些是「会不会」的问题，不是「抄没抄错」。见文末第三组。）

判分点长在过程上，不在结论上

这一点值得单独说，因为它决定了答题的取舍。按本站还原的给分点，中间状态本身常常就是独立的一档分——散列表构造好的内容 3 分、关键路径的 ve 数组 2 分、比较计数排序的 count 数组 1 分（这一档我们直接标成了「过程分」）。然后才是最终那个数字的分。

注意这里给分给的是每一轮的中间状态值，不是你的演算步骤。所以正确的取舍是：把表写完整，并且每一格都核对过——而不是把草稿上的推演誊上去。时间紧的时候先保表，最后一步的结论哪怕来不及化简，前面的分已经在手里了；反过来只写一个孤零零的答案，即使对了也只能拿一小部分。

这和算法设计题那边「写对的暴力解胜过写错的最优解」是同一条判分逻辑的两个侧面：408 的大题给分，给的是你展示出来的思考过程。

表长什么样，只取决于状态是什么

三种常见的表：

这类题	表的列是	每一行记什么
Prim / Dijkstra / 拓扑排序	顶点	这一轮之后，每个还没确定的顶点当前的最好值
关键路径	顶点（正向一遍、逆向一遍）	ve 取入边的 max，vl 取出边的 min
散列表构造	表的下标 0…m−1	这个 key 探查了哪几个位置、最终落在哪
置换-选择 / 出栈序列	工作区（栈）的当前内容	这一步输出了谁、又补进来了谁

关键路径那一类要留意方向：正向算 ve 时每个顶点取所有入边的最大值，逆向算 vl 时取所有出边的最小值。方向搞反是这一类的高频错误。

一个反复出现的问法：唯一吗？有几种？

真题很爱在跑完过程之后追问一句：这棵最小生成树唯一吗、最经济的方案有几种、这个拓扑序唯一吗。

看着像是另一个知识点，其实是同一张表的副产品：

凡是问「唯一吗 / 有几种」，就是在问：每一轮挑选的时候，有没有出现并列最优。

但要问得准一点：并列本身不等于分叉。 判断标准是「这一轮有两个候选一样好，而且只能选其中一个」：

• 2018 年那道题，第一阶段 5 条权 2 的边全部并列——但它们互不成环、全都要选进去，不产生任何分叉。真正的分叉只有连通两个块时的那一处二选一，所以是 2 种方案。
• 2017 年那道题图里也有多条同权边，但每一步能选的最小横切边始终只有一条，MST 仍然唯一——这道题的判分维度专门警告过：答「不唯一」是硬错。

方案数也不是「分叉的个数」，而是各轮独立可选支数的乘积：两处二选一就是 4 种方案。

所以画表时多留一列，记下这一轮有没有「二选一」。追问来的时候不用重跑。

还有一个常被记成「充要」的结论：边权互不相同，最小生成树一定唯一——但这只是充分条件，不是必要条件。 权值有重复的图，最小生成树也可能是唯一的。真题正面考过这一点。

散列表那两道的专属坑

这一组里散列表题最容易在细节上翻车，两个点：

1. 查找失败的 ASL，分母不一定是表长。 分母是散列函数 $H$ 的值域大小——如果表长是 10，而 $H(key)=(key\times 3)mod7$ 只会算出 0~6，那么失败查找只可能从这 7 个位置开始，分母就是 7 不是 10。真题就是这么设计的。
2. 「比较序列」和「探查地址序列」不是一回事。 问比较序列，写的是你真正拿去和目标做比较的那些关键字的值；问探查地址，写的才是下标。看清楚问的是哪个。

怎么画这张表

1. 先把表头画出来：列是什么（顶点 / 下标 / 工作区），一开始的状态是什么。
2. 一行一步往下走，每一步只做规则允许的那一个动作，把变化后的完整状态抄下来。
3. 回头对题——表填对了不等于答完了。问的是路径还是距离、是顺序还是集合、是关键活动还是"与某活动同时进行的活动"？这一组最冤的失分就是表全对、答非所问。

一道题的答卷长什么样

取 2017 年那道 Prim：图 G 的边为 A-B 6、A-D 4、A-E 5、B-C 4、C-D 6、C-E 5、D-E 4，从 A 出发。

卷面上写的就是这张表——一行一轮，列是还没进树的顶点，格子里是它到当前树的最近边权：

轮次	已进树	B	C	D	E	这一轮选谁	有并列吗
初	A	6	∞	4	5	A-D (4)	否
1	A D	6	6	—	4	D-E (4)	否
2	A D E	6	5	—	—	C-E (5)	否
3	A D E C	4	—	—	—	B-C (4)	否

选出的边：A-D(4)、D-E(4)、C-E(5)、B-C(4)，总权 17。

最后一列是特意留的。 题目第 (2) 问「这棵 MST 唯一吗」，答案直接从这一列读出来—— 每一轮的最小值都只有一个候选，所以唯一。不用重跑一遍，也不会因为「图里有好几条同权边」 就慌着答「不唯一」。

⚠️ 第 1 轮那一格容易错：D 进树后要用 D 去更新别人，E 从 5（A-E）被改成 4（D-E）， C 从 ∞ 被改成 6（C-D）。每轮更新只看新进树的那个点连出去的边，别把整张图重算一遍。

真题的三种形态

图上的迭代表——关键路径的 ve/vl、Prim 逐条选边、Kruskal 的最经济方案与方案数、把题面的存储结构还原成图再跑最短路。

散列表构造与 ASL——线性探测与二次探测的构造过程，以及成功／失败两个 ASL。

其它过程模拟——外部排序的置换-选择生成初始归并段、进栈出栈序列的合法性判定、给一段代码让你逐步模拟它到底在干什么。

⚠️ 这一组要留个心：后三道题各有一半分不在过程上——卡特兰数的等价刻画与递推、归并段长度上下界的论证、比较次数与稳定性的判断，考的是推导而不是模拟。那部分的方法在性质推导与最优性论证那个专题里，两边要一起练。

题目要你用文字描述过程时

有些小问不要表，要一段话：「描述拓扑排序的过程」「说明 Find 时如何压缩路径」「写出 Dijkstra 每一轮的结果」。会画表的人，到这里常常写不出来。看得懂、画得出，和能用文字说清楚，是两种能力，后者要单独练。

写法和画表是同一个思路：一轮写一句，每句的格式固定。先交代初始状态，然后逐轮写「这一轮依据什么规则选了谁、状态变成什么」，最后写结束条件和结论。

• Dijkstra：初始 $dist$ 为起点各出边的权值。第 $k$ 轮：在未确定的顶点中选 $dist$ 最小的 $X$，确定起点到 $X$ 的最短路径为 …，长度为 …；再用 $X$ 的出边更新其余顶点的 $dist$。所有可达顶点确定后结束，不可达的顶点 $dist$ 保持 $\mathrm{\infty }$。
• 拓扑排序：求出各顶点入度。第 $k$ 步：从入度为 0 的顶点中选出 $X$ 输出（有多个可选时说明选的依据），删去 $X$ 的全部出边，相应顶点入度减 1。全部输出则得到拓扑序列；若还有顶点未输出、却已没有入度为 0 的顶点，说明图中有回路。
• 栈的括号匹配：从左到右扫描。遇左括号入栈；遇右括号时，栈空则失败，否则弹出栈顶，与当前右括号类型不同也失败。扫描结束时栈空才算匹配成功。
• 并查集 Find（路径压缩）：先从 $x$ 沿 parent 向上走到根，记下根 $r$；再从 $x$ 出发把这条路径上每个结点的 parent 直接改为 $r$。

这类问题只看文字本身是否把规则和每一轮的结果交代清楚，不需要写成伪代码。

自己出一组例子，用可视化核对

手推最怕"自己觉得对"。下面几种过程，可视化工具允许输入你自己的数据：先在纸上推完，再把同一组数据输进去逐步播放，一格一格对。

• BST 的插入与删除、AVL 的插入与旋转：设计不少于 10 个关键字的插入序列，让 LL、RR、LR、RL 四种旋转都出现一次；再删 4 个结点，覆盖叶子、只有左子树、只有右子树、左右子树都有四种情况。
• 开放定址散列、拉链法散列：自定表长和散列函数，插入序列里至少安排 4 次冲突，再分别算成功与失败的 ASL。
• 哈夫曼树：自定 8 到 10 个字符的权值，构造后写出编码，再拿一串编码练译码。
• 希尔排序、堆排序、快速排序、基数排序：用不少于 10 个元素的乱序数组，写出每一趟之后的状态。

图上的算法（Dijkstra、拓扑排序、Prim、Kruskal）和外部排序的可视化目前只有固定的例子，自己出的图只能手推；对答案可以用专题巩固栏里的题。

交卷前扫一眼

先画表头再落笔 · 一行一步抄下完整状态 · 多留一列记「这轮有没有二选一」· 表填完回头对题，问的未必是你算的那个量

配套内容

逐题精讲（建设中）——真题作答与 AI 判分入口见站内大题专题。

基础没打牢的，先回这几篇：

• 关键路径｜Prim｜Kruskal｜Dijkstra｜拓扑排序
• 开放定址散列｜拉链法散列｜外部排序

考纲要求、但这 10 道真题没有正面考过的（专题的巩固栏里配了题，可以直接练）：

• AVL 树的插入与删除调整——四种旋转的判定、自底向上定位第一个失衡结点
• B 树的插入分裂与删除合并——下溢时先借兄弟、借不到才合并

这两样几乎年年在选择题里出现（18 年里有 16 年至少考到其中一个），手推过程却从没进过大题。它们恰恰是最典型的"规则死、状态变"，画表的方法完全通用。

同样规则固定、大题还没正面考过的，巩固栏里也各配了一道：并查集的按大小合并与路径压缩、分块查找的 ASL、BST 的四种删除、树的三种存储结构画图、基数排序和希尔排序的逐趟状态，以及外部排序接在置换-选择后面的最佳归并树与败者树。

真题练习

本专题的真题（10题）

2011Q418分2025Q4210分2017Q428分2018Q4212分2014Q4210分2010Q4110分2024Q4210分2023Q4210分2026Q4210分2021Q428分