数据结构大题

数据结构中的查找、图、树与排序，既会要求设计算法，也会要求手工执行算法、解释结果或证明某个判断。本页主要讨论后一类。做这类题，要知道结构里存的是什么，以及一次操作会改变哪些状态。

这个板块包含哪些知识

• 查找：散列函数、冲突处理、装填因子、查找长度与查找概率。
• 图：邻接矩阵和邻接表、遍历、最小生成树、最短路径、拓扑排序与关键路径。
• 树与栈：结点度数、树高、带权路径长度、前缀编码、栈的操作与合法序列。
• 排序：算法的中间状态、稳定性、复杂度，以及外部排序的归并段生成和归并。

这些知识的共同点是：结构规定合法操作，算法规定状态如何变化。例如 Prim 维护已加入生成树的顶点集合，Dijkstra 维护已确定的最短距离，两者都在“选最小”，候选对象和最小值的含义却不同。

可分别回看图、查找、树和排序。涉及递归与运行栈的关系，配合程序执行与内存图谱；写思想、代码和复杂度的题见算法设计题框架。

常见考点与题型

综合题可能组合下面几类小问。先看要求求什么，再确定需要调用哪些知识。

解题前要弄清的关系

同一结构可以对应不同问题。下面先梳理结构与算法的关系，具体执行时仍要核对题设规则。

一、散列表 —— 一张按 H(key) 填的表

1. 表长 m 与装填因子 α 互推：α = 已填个数 ÷ 表长，见 装填因子
2. 冲突后按题给公式继续探查：线性探测 Hᵢ = (H₀ + i) mod m、平方探测 Hₖ = (H₀ + k²) mod m，见 线性探测法、平方探测法
3. 两个 ASL 分母不同：成功除以关键字个数，失败按可能的初始散列地址及其概率求平均，见 查找成功、查找失败

二、图 —— 存储结构与图形之间来回翻译

1. 邻接矩阵 ↔ 图形是双向的，压缩存储要先还原成矩阵，见 邻接矩阵、三角矩阵
2. 对以 0/1 表示边的邻接矩阵，Aᵐ(i, j) 表示从 i 到 j 长度为 m 的游走条数，允许重复经过顶点或边；不是简单路径条数
3. 几种常见算法都需要维护候选集合，但选择依据不同：prim 算法 选边、dijkstra 算法 选点、拓扑排序 选入度为 0 的点
4. 关键路径 用事件最早、最晚时间推导活动的可安排范围，计算式见下

三、树与组合计数 —— 两个恒等式联立

1. 结点数：n = n₀ + 分支结点数，边数：e = n − 1，另一边由度数给出 e = m·k，见 度
2. 带权路径长度与前缀编码都是「根到叶的路径」，见 哈夫曼树、前缀编码
3. 出栈序列计数用 卡特兰数，合法性判据见 不可能的出栈序列

四、排序 —— 先说清语义，再说趟特征

1. 读代码型的题先用一句话讲清辅助数组的含义，结果直接由语义写出，见 排序概念
2. 稳定性只看相等元素的判定条件，见 稳定性
3. 外部排序要区分初始归并段生成、归并路数和读写趟数，见 置换选择排序、多路归并

各类题的解法

这一支没有统一流程：认出对象之后，每类对象各有一套写法，下面几条按对象挑着用。

先认出对象，落笔格式就定了

图算法与归并段生成：按轮记录状态

Prim、Dijkstra、拓扑排序和置换选择都适合记录中间状态。题目要求执行过程时，可以使用下面的格式，但候选集合和更新内容需要随算法调整：

第 k 轮：当前集合 S = {…}
        候选（横跨 S 与 V−S 的边 / 待选顶点）= …
        选中 …，理由：权最小 / 入度为 0

Prim 在连通无向图上选出 n−1 条边后结束；Dijkstra 按题意确定目标或所有可达顶点的距离；拓扑排序还要检查是否输出全部顶点。置换选择则要记录工作区和被冻结到下一段的记录，直至输入及工作区处理完毕。

AOE 网：先求事件时间，再求活动余量

ve(源) = 0，按拓扑序正推：ve(j) = max{ ve(i) + w(i,j) }
vl(汇) = ve(汇)，按逆拓扑序倒推：vl(i) = min{ vl(j) − w(i,j) }
活动 a = <i, j>：e(a) = ve(i)，l(a) = vl(j) − w(i,j)
时间余量 d(a) = l − e = vl(j) − ve(i) − w

d = 0 的活动是关键活动，串起来才是关键路径，长度 = ve(汇) = 最短工期。附加问也都从这四式来：可并行是两个活动的执行区间有重叠，最多能推迟多久是对它所在的整条路径列不等式「路径长度 ≤ 关键路径长度」求解。2011#41 的工期是 16，2025#42 是 12。

散列表把两个 ASL 分开算

1. 给了装填因子先反推表长：2010#41 是 7 ÷ 0.7 = 10；
2. 按插入顺序填表，每个关键字记比较次数，从 1 起算，即本页开放定址题中探查次数 = 冲突次数 + 1；
3. ASL成功 = Σ比较次数 ÷ 关键字个数；
4. 若各初始散列地址等概率，ASL失败 = 各起点失败探查次数之和 ÷ 起点个数；起点范围由散列函数决定，不能直接拿表长作分母；
5. 问「查找某个不在表中的关键字失败时的散列地址」，答第一个探到空位的地址。2024#42 查 8 走 2 → 3 → 6 → 0 → 7，答 7。

查找概率不等时不能默认折半更优，一律算加权 ASL = Σ pᵢ·cᵢ 再比。2013#42 里顺序存储按概率降序排是 2.1，改建二叉排序树把高概率放浅层是 2.0。

论证题的三段式

「能不能」「是否唯一」「是否稳定」这类问法不接受只写结论：

1. 先给结论，明确回答题目中的命题；
2. 否定一般命题时，举一个尽量小的反例；肯定命题时，给出适用条件和推理；
3. 最后一句点出原因（例如「局部最优不等于全局最优」）。

2009#41 的评分说明写明：答「能」的无论怎么证都不给分。问最小生成树是否唯一要给具体理由，题目要求充分条件时，可给“图连通且所有边权互不相同”；判断某个具体图时，重复边权本身不能直接说明不唯一，需要检查能否等权替换生成树中的边。

树与栈：先找计数对象，再列关系

树的结点统计先约定高度按层数还是边数计算，再用两种方式数边。若有 m 个 k 度分支结点，其余全是叶结点，则 e=mk，同时 e=n−1=m+n₀−1，联立得到 n₀=(k−1)m+1。公式来自结构条件，不能拿来计算任意一棵度数混合的树。

哈夫曼或归并次序题，把每次合并的权值相加；它等于相应合并树的带权路径长度。前缀编码题则沿编码树从根走到叶，叶子不能再是其他编码的祖先。

出栈序列先尝试模拟：为弹出目标元素，只能按输入次序压栈；目标已入栈却不是栈顶时，该序列不合法。若要求计数，再以第一个元素匹配的出栈位置分解子问题，建立递推，说明边界，最后才使用卡特兰数。

排序：解释中间状态，再判断性质

读排序代码时，先写清“执行到这里，哪一段已经满足什么条件”。判断稳定性，可给相同关键字加上 a、b 标签，观察比较或交换是否会颠倒其原有次序；一个反例足以否定稳定性。

置换选择题维护工作区中的可选记录与冻结记录：输出当前段可选的最小记录，新读入记录若小于本段最后输出值，就冻结到下一段；没有可选记录时结束本段。生成归并段后，归并路数和缓冲区分配属于后续问题，需要另外计算归并趟数与 I/O。

历年题索引

对象和落笔格式是通用的，下面这张表只用来查「某一年考的是哪个对象、额外拐了什么弯」。

易错清单

• 失败 ASL 未看起点范围与概率。等概率时按散列函数可能产生的地址平均。2010#41 表长 10 而 H(key) 是 mod 7，失败 ASL 是 18/7。
• 比较次数从 0 起算。无冲突也是 1 次比较，本页开放定址题中探查次数 = 冲突次数 + 1。
• 只看顶点 ve = vl 就判关键活动。关键活动的判据只有 l − e = 0。2011#41 里顶点 0 与顶点 2 都满足 ve = vl，但它们之间那条活动的余量是 3。
• 关键活动和关键路径混说。关键活动是边，关键路径是这些边首尾相连的完整路径，只有路径长度才等于工期。
• 边权有重复时只给一棵最小生成树。题目问「所有可能的方案」就必须都画出来并说明总费用相同，2018#42 有两种方案。
• 置换选择里把 m 当成归并段个数。m 是工作区容量，第一个归并段的长度范围是 [m, n]，2023#42 里 m = 4 生成的是 3 个段。
• 过程题只写最终结果。逐轮的候选和选择理由是分点，省掉就只剩结论分。

下一页：数的表示与运算。