Appearance
手推与逐步模拟：答案是一张过程表
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 种方案。
所以画表时多留一列，记下这一轮有没有「二选一」。追问来的时候不用重跑。
还有一个常被记成「充要」的结论：边权互不相同，最小生成树一定唯一——但这只是充分条件，不是必要条件。 权值有重复的图，最小生成树也可能是唯一的。真题正面考过这一点。
散列表那两道的专属坑
这一组里散列表题最容易在细节上翻车，两个点：
- 查找失败的 ASL，分母不一定是表长。 分母是散列函数
的值域大小——如果表长是 10，而 只会算出 0~6，那么失败查找只可能从这 7 个位置开始，分母就是 7 不是 10。真题就是这么设计的。 - 「比较序列」和「探查地址序列」不是一回事。 问比较序列，写的是你真正拿去和目标做比较的那些关键字的值；问探查地址，写的才是下标。看清楚问的是哪个。
怎么画这张表
- 先把表头画出来：列是什么（顶点 / 下标 / 工作区），一开始的状态是什么。
- 一行一步往下走，每一步只做规则允许的那一个动作，把变化后的完整状态抄下来。
- 回头对题——表填对了不等于答完了。问的是路径还是距离、是顺序还是集合、是关键活动还是"与某活动同时进行的活动"？这一组最冤的失分就是表全对、答非所问。
一道题的答卷长什么样
取 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。
其它过程模拟——外部排序的置换-选择生成初始归并段、进栈出栈序列的合法性判定、给一段代码让你逐步模拟它到底在干什么。
⚠️ 这一组要留个心：后三道题各有一半分不在过程上——卡特兰数的等价刻画与递推、归并段长度上下界的论证、比较次数与稳定性的判断，考的是推导而不是模拟。那部分的方法在性质推导与最优性论证那个专题里，两边要一起练。
交卷前扫一眼
先画表头再落笔 · 一行一步抄下完整状态 · 多留一列记「这轮有没有二选一」· 表填完回头对题，问的未必是你算的那个量
配套内容
逐题精讲（建设中）——真题作答与 AI 判分入口见站内大题专题。
基础没打牢的，先回这几篇：
考纲要求、但这 10 道真题没有正面考过的（专题的巩固栏里配了题，可以直接练）：
这两样几乎年年在选择题里出现（18 年里有 16 年至少考到其中一个），手推过程却从没进过大题。它们恰恰是最典型的"规则死、状态变"，画表的方法完全通用。