数据结构·代码题解题套路
统考 408 的数据结构大题（第 41 题，通常 13 分）几乎固定考察算法设计。本页整理评分规则、答题模板与高频题型。
一、评分规则与答题结构
阅卷按三段式给分，缺一段会明显失分：
| 得分点 | 分值占比 | 要求 |
|---|---|---|
| 算法的基本设计思想 | 约 1/3 | 用自然语言描述思路，说清做法与关键步骤 |
| 算法的实现（代码） | 约 1/2 | C / C++ 描述，伪代码亦可，不要求可编译 |
| 时间与空间复杂度 | 约 1/6 | 必须写，且要与自己的算法一致 |
答题要点
- 先写思想再写代码。只写代码而没有思想描述，会直接扣掉三分之一。
- 复杂度要写自己算法的真实复杂度，不要照抄题目里"要求
"就写 。 - 允许伪代码，但结构体定义、指针操作要写清楚，不能出现自造的库函数。
- 时间不够时，宁可写一个
的正确算法，也不要写一个不完整的最优解。
二、通用答题模板
c
/* 1. 算法的基本设计思想
* （用自然语言写清：用什么数据结构、分几步、每步做什么、为什么正确）
*/
/* 2. 算法实现 */
typedef struct {
ElemType data[MaxSize];
int length;
} SqList;
int Algorithm(SqList *L, ...) {
/* 边界检查 */
if (L->length == 0) return 0;
/* 主体逻辑 */
return 1;
}
/* 3. 复杂度
* 时间复杂度：O(n)，因为只对数组做了一趟扫描
* 空间复杂度：O(1)，只使用了常数个辅助变量
*/三、高频题型与核心思路
1. 线性表
| 题型 | 核心思路 | 复杂度 |
|---|---|---|
| 数组循环左移 | 三次逆置：逆置前 | |
| 两个等长有序序列的中位数（2011） | 双指针同步折半，每次砍掉一半 | |
| 寻找主元素（2013） | 摩尔投票：候选 + 计数，再扫一遍验证 | |
| 最小未出现正整数（2018） | 用长度 | |
| 删除所有值为 | 快慢指针原地覆盖 |
2. 链表
| 题型 | 核心思路 |
|---|---|
| 判断是否有环、找入环点 | 快慢指针相遇后，一指针回头结点同速再走 |
| 找倒数第 | 双指针，前指针先走 |
| 两链表公共后缀（2012） | 先求长度差，长的先走差值，再同步比较 |
| 重排链表 | 找中点 → 后半逆置 → 交替归并 |
| 删除绝对值重复的结点（2015） | 辅助数组按 |
链表题必查三点
① 是否带头结点；② 删除结点后要 free；③ 修改指针的顺序不能反（先接后断）。
3. 树与二叉树
| 题型 | 核心思路 |
|---|---|
| 非递归遍历 | 显式栈模拟；中序最常考 |
| 层序遍历 / 求宽度 | 队列 + 记录每层结点数 |
| 求 WPL（2014） | 层序或递归累加 depth * weight |
| 判断是否二叉搜索树 | 中序遍历应严格递增 |
| 最近公共祖先 | 顺序存储用下标折半；链式用递归回溯 |
4. 图
| 题型 | 核心思路 |
|---|---|
| 判断是否为树 | DFS 一次遍历完且边数 |
| 拓扑排序判环 | 入度为 0 入队，出队计数 |
| 单源最短路 | BFS（无权）/ Dijkstra（正权） |
5. 排序与查找
| 题型 | 核心思路 |
|---|---|
| 快排 partition 的变形 | 找第 |
| 归并的变形 | 求逆序对数 |
| 折半查找变形 | 找第一个 |
四、常见失分点
- 边界未检查：空表、单元素、
越界，这些是阅卷重点。 - 头结点处理不一致：题干说"带头结点"却按不带头结点写。
- 复杂度写错：写了双重循环却标
。 - 只写代码不写思想：直接损失约三分之一分值。
- 使用了不存在的函数：如自造
sort()、length()，需自己实现或说明。