数据结构大题
手工推导题的固定动作：先认对象，再按该对象唯一的那套恒等式或逐轮表落笔。
数据结构的两道综合题分工很稳定：一道算法设计题，一道手工推导题。
- 算法设计题（写思想 + 写代码 + 写复杂度）有独立一页：算法设计题解题框架，本页不重复。
- 手工推导题 18 套卷子里一共 15 道，是本页的主体。它不写代码，只要求「按规则走一遍并把过程写出来」，是整张卷子上最不该丢分的一支。
知识框架概要
手工推导题没有统一模型，但每一类对象只有一套固定写法。认出对象，写法就定了。
一、散列表 —— 一张按 H(key) 填的表
- 表长 m 与装填因子 α 互推：
α = 已填个数 ÷ 表长，见 装填因子 - 冲突后按题给公式继续探查：线性探测
Hᵢ = (H₀ + i) mod m、平方探测Hₖ = (H₀ + k²) mod m，见 线性探测法、平方探测法 - 两个 ASL 分母不同：成功除以关键字个数，失败除以散列函数的地址个数，见 查找成功、查找失败
二、图 —— 存储结构与图形之间来回翻译
- 邻接矩阵 ↔ 图形是双向的，压缩存储要先还原成矩阵，见 邻接矩阵、三角矩阵
Aᵐ(i, j)= 从 i 到 j 长度为 m 的路径条数- 四个算法都是「逐轮选一个东西加入」：prim 算法 选边、dijkstra 算法 选点、拓扑排序 选入度为 0 的点
- 关键路径 是唯一有公式的一类，四式见下
三、树与组合计数 —— 两个恒等式联立
- 结点数：
n = n₀ + 分支结点数，边数：e = n − 1，另一边由度数给出e = m·k，见 度 - 带权路径长度与前缀编码都是「根到叶的路径」，见 哈夫曼树、前缀编码
- 出栈序列计数用 卡特兰数，合法性判据见 不可能的出栈序列
四、排序 —— 先说清语义，再说趟特征
解题注意点
这一支没有统一流程：认出对象之后，每类对象各有一套写法，下面几条按对象挑着用。
先认出对象，落笔格式就定了
| 题干里出现 | 对象 | 第一笔写什么 |
|---|---|---|
| 散列函数、装填因子、探查、ASL | 散列表 | 先定表长，再逐个填表并记比较次数 |
| 邻接矩阵、压缩数组、Aᵐ | 图的存储 | 先还原成图形，再看问什么 |
| 活动、事件、工期、最早最晚 | AOE 网 | 正推 ve、倒推 vl |
| 结点数、叶结点数、高度、编码 | 树 | 写 n = n₀ + 分支结点数 与 e = n − 1 |
| 给了一段排序代码或工作区 | 排序 | 先用一句话写清辅助结构的语义 |
| 「能否」「是否唯一」「是否稳定」 | 论证题 | 先给结论，再举最小反例 |
过程题一律写成「逐轮表」
Prim、Dijkstra、拓扑排序、置换选择、置换算法都属于这一类，评分是按轮给的，只写最终结果会大面积失分。固定格式：
第 k 轮：当前集合 S = {…}
候选（横跨 S 与 V−S 的边 / 待选顶点）= …
选中 …，理由：权最小 / 入度为 0
写到第 n−1 条边为止，最后再按加入顺序把结果列一遍。
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 分开算
- 给了装填因子先反推表长：2010#41 是 7 ÷ 0.7 = 10；
- 按插入顺序填表，每个关键字记比较次数，从 1 起算，即比较次数 = 冲突次数 + 1；
ASL成功 = Σ比较次数 ÷ 关键字个数；ASL失败 = Σ比较次数 ÷ 散列地址个数——分母是散列函数的模值，不是表长；- 问「查找某个不在表中的关键字失败时的散列地址」，答第一个探到空位的地址。2024#42 查 8 走 2 → 3 → 6 → 0 → 7，答 7。
查找概率不等时不能默认折半更优，一律算加权 ASL = Σ pᵢ·cᵢ 再比。2013#42 里顺序存储按概率降序排是 2.1，改建二叉排序树把高概率放浅层是 2.0。
论证题的三段式
「能不能」「是否唯一」「是否稳定」这类问法不接受只写结论：
- 先给结论（「不一定能」）；
- 再举一个尽量小的反例并说明它为什么反；
- 最后一句点出原因（例如「局部最优不等于全局最优」）。
2009#41 的评分说明写明：答「能」的无论怎么证都不给分。问最小生成树是否唯一要给具体理由，问一般条件只需给充分条件「任一环内的边权互不相同」。
历年题索引
对象和落笔格式是通用的，下面这张表只用来查「某一年考的是哪个对象、额外拐了什么弯」。
| 真题 | 主线 | 这一年特别问了什么 |
|---|---|---|
| 2009#41 | 最短路径的贪心法 | 「每步选离 u 最近的点」能否求最短路，不能就举反例 |
| 2010#41 | 散列表 + 两个 ASL | 装填因子 0.7 要先反推表长 |
| 2011#41 | 上三角压缩还原 + 关键路径 | 先由一维数组还原邻接矩阵并画图，再求关键路径 |
| 2012#41 | 哈夫曼思想定归并次序 | 6 段有序表的最坏比较总次数，并推广到 N 段 |
| 2013#42 | 按查找概率选存储与查找法 | 顺序、链式各怎么排列，ASL 各是多少 |
| 2015#42 | 邻接矩阵与 A² 的含义 | A² 中某一格的含义，再推广到 Bᵐ |
| 2016#42 | 正则 k 叉树结点数推导 | 叶结点数表达式；高为 h 时结点最多、最少各多少 |
| 2017#42 | Prim 最小生成树 | 逐条列出选中的边；该图 MST 是否唯一；唯一的条件 |
| 2018#42 | 最小生成树（城市光缆） | 给出所有最经济方案；第 3 小问跨到网络 TTL |
| 2020#42 | 前缀编码的二叉树表示 | 用什么结构保存、译码过程、怎么判定前缀特性 |
| 2021#42 | 比较计数排序 | 给定 a 求 b；比较次数；是否稳定，不稳定就改 |
| 2023#42 | 置换选择生成初始归并段 | m = 4 时生成几段各是什么；第一段长度的最大最小值 |
| 2024#42 | 平方探测散列表 | 画表算装填因子；查 14 的比较序列；查 8 失败的地址 |
| 2025#42 | AOE 关键路径 + 时间余量 | 与某活动可并行的活动；余量最大的活动；推迟到时刻 6 |
| 2026#42 | 栈的合法出栈序列计数 | 非法序列中三个下标的大小关系；用 M 表示 n = k 的总数 |
易错清单
- 失败 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 个段。 - 过程题只写最终结果。逐轮的候选和选择理由是分点，省掉就只剩结论分。
下一页：数的表示与运算。