DS-7 代码题体系（408 算法设计大题）

数据结构

来源：10-DS7-代码题体系.md · 完整笔记（7 节，未删减）

数据结构收官模块。对应资料库：复习资料 P4（9 模板 + 17 真题手写册）、AI输出的内容（代码题出题规律）。本模块不再讲新知识，而是把 DS-1~DS-6 的全部内容收束成考场上的 25 分钟作战流程。

核心问题

这一部分为什么存在？

408 数据结构有两道大题：一道分析题 + 一道算法设计题（约 13 分）。代码题的难处不在知识——考的全是 DS-1~DS-6 里的基本操作——而在于在 25 分钟内把“问题”翻译成“数据结构 + 技巧”。真题的命题规律（来源：AI输出的内容/408代码题出题规律与做题指南.md）：

题材固定在顺序表、链表、二叉树、图四类载体上轮换；
要求的解几乎都是时间 $O(n)$ 或 $O(n \log n)$ 、空间 $O(1)$ 或 $O(n)$ 的一趟/两趟扫描级别，从不考复杂高级算法；
三问结构固定：设计思想（4~~5 分）+ 代码（7~~9 分）+ 复杂度（2~3 分）。

因此本模块的答案是：把 17 年真题归类成 9 个模板，考场上先套模板、套不上再暴力保底。

概念体系：代码题的“翻译公式”

flowchart TD
    A["读题三步法（30 秒）"] --> A1["1. 划数据结构<br/>链表？数组？顺序存储树？邻接矩阵？"]
    A --> A2["2. 划需求<br/>找/删/改/判定？有'尽可能高效'吗？"]
    A --> A3["3. 验示例<br/>手算题目样例"]
    A1 --> B["四类载体 → 对应模板库"]
    B --> C["写设计思想（三段落）<br/>用什么 → 怎么做 → 为何高效"]
    C --> D["写代码（先框架后细节）"]
    D --> E["复杂度 + 边界自查"]
    B -.10分钟无思路.-> F["暴力保底写法<br/>拿稳 8 分"]

得分结构（来源：复习资料 P4 §一）：设计思想写满 3 条即满分；代码与思想一致 + 关键注释 + 边界正确；复杂度给结论 + 一句话理由。决策线：前 10~12 分钟没有 O(n) 思路就切暴力保底。

实现机制：9 个模板（必须能够手写）

#	模板	适用场景	对应真题
1	快慢指针	链表找中点 / 判环 / 重排	2019-41 重排
2	长度对齐双指针	共同后缀 / 倒数第 k 个 / 交点	2009-42 倒数第 k、2012-42 共同后缀
3	头插逆置	链表反转 / 回文 / 重排后半	2019-41
4	快排 partition	集合划分 / 第 k 小	2016-43 集合划分
5	候选计数（摩尔投票）	出现次数 > n/2 的主元素	2013-41 主元素
6	顺序存储树递归（下标 2i+1/2i+2）	顺序存储树的遍历/判定	2022-41 判 BST
7	邻接矩阵度统计	度/出入度（欧拉、K 顶点）	2021-41 EL 路径、2023-41 K 顶点
8	Kahn 拓扑排序	拓扑序列存在性/唯一性	2024-41 唯一拓扑序列
9	倒序扫描维护后缀最值	“每个位置与其后元素”的最值	2025-41 乘积最大值

三个使用要点：

模板即得分骨架：以模板 2 为例——先各求长度、长表先走差值步、再同步走比结点地址（不是 data），相遇即共同后缀起点；2009-42 是它的特例（第二张“表”是从头走 k 步的同一链表）。
模板可组合：2019-41 = 模板 1（找中点）+ 模板 3（逆置后半）+ 归并交替——设计思想三段落范文即按此展开（来源：P4 §2.2）。
边界是阅卷重灾区：空表、单结点、 $k$ 越界（2009-42 要求找不到返回 0）、奇偶结点（快慢指针循环条件 fast->next && fast->next->next）。

方案比较：代码题的分层掌握标准

层级	算法	要求
必须能够手写	链表插删/逆置/双指针；快排 partition；折半查找；二叉树三种递归遍历；BFS/DFS（树与图）；Kahn 拓扑	默写级，考场直接调用
必须理解（能说清思想、能改写成代码）	堆调整；归并排序；KMP；Dijkstra；Prim/Kruskal；候选计数	说出核心步骤与复杂度
只需识别思想	红黑树插删、B/B+ 树插删调整、KMP 的 next 求法细节、Floyd、关键路径、败者树/置换-选择	选择题认出即可

判断依据：17 年真题代码大题全部落在第一、二层（来源：P4 手写册、AI输出的内容/历年408代码题汇总.md）。

“最优解 vs 暴力解”的比较：408 评分按“算法效率分档给分”—— $O(n)$ 满分档、 $O(n \log n)$ 次之、 $O(n^2)$ 暴力也能拿大部分分数（约 8/13）。所以暴力保底不是失败而是策略：在时间约束下，写对的 $O(n^2)$ 优于写错的 $O(n)$ （来源：P4 §1.2、§5.4）。

应用与考法：17 年真题全景归类

数组/链表类（9 道）：

年份题号	题材	模板
2009-42	单链表倒数第 k 个	2
2010-42	顺序表循环左移 p 位	三次逆置（模板 3 的数组版思想）
2011-42	两等长升序序列求中位数	折半思想（理解级）
2012-42	两链表共同后缀	2
2013-41	主元素（> n/2）	5
2015-41	链表按绝对值去重	辅助数组标记（空间换时间）
2016-43	数组划分为	$S_1$
2018-41	找数组中未出现的最小正整数	原地哈希（值为 x 放 x−1 位）
2025-41	$A[i] \times A[j]$ （ $i<j$ ）最大值	9

树/图类（8 道）：

年份题号	题材	模板
2014-41	二叉树 WPL	DFS 记深度累加叶权（递归模板）
2017-41	表达式树转中缀（带括号）	递归 + 层级判断
2019-41	链表重排（归此类的链表题）	1+3
2020-41	三点组合距离最小	排序 + 双指针/一趟
2021-41	EL 路径存在性（邻接矩阵）	7（数奇度顶点 ≤2）
2021-42	计数排序 + 稳定性修改	排序模板
2022-41	顺序存储树判 BST	6（中序严格递增）
2023-41	K 顶点（出度>入度）统计	7
2024-41	拓扑序列唯一性判定	8

近年趋势：图类代码题增多（2021、2023、2024 连续三年），但都是**“遍历 + 统计”**级别，模板 7/8 直接覆盖。

考场标准动作（来源：P4 §1.2、§5）：

读题三步法定位载体与需求；
设计思想套三段落（用什么 → 怎么做 → 为何高效，万能句式见 P4 §5.1）；
代码先写框架（结点定义、函数签名、主循环）再填细节，关键行写注释；
10 分钟无最优思路 → 切暴力保底（双重循环 + 正确边界）；
交卷前用题目示例手算一遍。

做题触发词：看到“倒数第 k / 共同”→ 双指针；看到“> n/2”→ 摩尔投票；看到“划分”→ partition；看到“链表 + 重排/回文”→ 找中点 + 逆置；看到“邻接矩阵 + 路径/顶点性质”→ 度统计；看到“拓扑”→ Kahn。

来源：复习资料 P4 全文；AI输出的内容/408代码题出题规律与做题指南.md、历年408代码题汇总.md。

前后联系

向前依赖：DS-1/2（链表/顺序表操作）、DS-3（树递归）、DS-4（图的矩阵与拓扑）、DS-5（折半、BST）、DS-6（partition、归并、堆、稳定性）——代码题是前五章的“综合应用考场”。
向后引出 / 跨学科：
- 链表/数组思维 → OS 空闲链表、FAT（OS-7）；双指针/一趟扫描 → 网络滑动窗口实现（理解级）；
- 代码题中的“边界与防御性检查” → 工程素养在 CO-2 机器级代码分析题（如 2019-45/2024-45 的汇编阅读）中同样适用。

闭卷回忆链

代码大题三问各占多少分？每问怎么拿满？
读题 30 秒内要划出哪三件事？
设计思想三段落怎么写？（用什么 → 怎么做 → 为何高效）
链表的四个核心模板各解决什么场景？（快慢指针/对齐双指针/头插逆置/归并）
数组的三个核心模板？（partition/摩尔投票/后缀最值）
树的代码题为什么几乎都是“递归 + 全局量/参数”？顺序存储树孩子下标怎么算？
图的代码题近两年为什么都是“度统计 + Kahn”级别？
哪些算法必须默写、哪些只需理解、哪些只识别？
想不出 O(n) 时的决策线和保底策略是什么？
写完代码后的两个自查动作？（边界：空/单结点/越界；示例手算）
从 2009 到 2025 的真题题材轮换规律是什么？（链表 → 数组 → 树 → 图循环，模板全覆盖）