“算法题代码写不出来，时间复杂度和空间复杂度算不对”“二叉树遍历的递归和非递归总是搞混”“图的DFS和BFS代码一写就错”——数据结构算法题是408中区分度最高的模块，也是跨考生最头疼的拦路虎。

数据结构在408中占45分（约30%），是四门课中分值最高的模块。其中算法相关题目（代码实现、时间复杂度、空间复杂度分析）约占20-25分（即数据结构部分的45%-55%）。这部分不仅考查基础理论，更注重实际应用，常以大题形式出现，分值高、难度大。

一、数据结构分值构成与算法题定位

| 模块 | 分值占比 | 核心特征 |
|---|---|---|
| 数据结构总分 | 45分 | 408中分值最高的科目 |
| 算法题（大题） | 20-25分 | 代码实现+复杂度分析 |
| 选择题+其他 | 20-25分 | 概念、性质、推导 |

数据结构考点集中在“线性表、树、图、查找、排序”五大模块。近5年（2020-2024年）真题统计：树与二叉树占22%、图占18%、排序占10%、查找占8%、线性表占7%，综合应用题占35%。

二、算法题四大题型分类

从408应试的角度来看，算法题主要分为四部分——①线性表(包括数组和链表)、②二叉树、③图、④查找。

题型一：线性表（数组+链表）

数组类：两个有序表合并为一个新的有序表、数组元素逆置、删除重复元素、找出第k大元素等。

链表类：单链表、双向链表、循环链表的插入、删除操作及边界条件处理。高频题型包括反转链表、合并有序链表。链表题的核心技巧是哨兵节点+虚拟头，插入/删除只需改`dummy->next`，避免头节点特判。

题型二：树与二叉树

绝对核心考点，近10年考察约15次。

遍历：前序、中序、后序（递归与非递归）、层次遍历的代码实现。高频题型包括最近公共祖先、层序遍历等。

特殊二叉树：二叉搜索树（BST）的插入、删除及查找效率分析；平衡二叉树（AVL）的平衡因子计算与旋转调整；哈夫曼树的构造与编码方法。

递归三问法：“当前节点做什么？”“左右子树返回值？”“最终向上返回？”

题型三：图

近10年考察约14次。

存储结构：邻接矩阵（稠密图）vs 邻接表（稀疏图）的适用场景。

遍历算法：DFS与BFS的代码实现及应用（连通分量、拓扑排序）。

最短路径与最小生成树：Dijkstra算法（单源，边权非负）、Floyd算法（多源）；Prim算法与Kruskal算法。

DFS三色标记法：白色未访问，灰色已访问未回溯，黑色已回溯——环检测、路径记录一次完成。

题型四：查找与排序

查找：近10年考察约12次。折半查找的条件（有序表）、判定树构建及平均查找长度计算；哈希表的构造方法（除留余数法）、冲突处理（开放定址法、链地址法）。

排序：近10年考察约14次。快速排序、归并排序、堆排序的时间复杂度（平均与最坏）、空间复杂度及稳定性对比。重点是快速排序的partition过程、堆排序的建堆与调整逻辑。

三、算法题答题规范与模板

408算法题通常按“算法设计思想→C语言描述→时空复杂度”三问格式出题。阅卷按步骤给分，即使代码写不完整，写出思路和复杂度也能拿到部分分数。

答题“四步法”

第一步：概括算法功能（1-2句话）

简要描述代码的整体目的，例如“该算法实现了两个有序顺序表的合并，通过双指针依次比较元素大小，将较小者放入新表”。

第二步：分析代码逻辑

逐行或逐段解释关键逻辑——循环变量、终止条件、每次迭代的作用；递归的递归基和递归过程。

第三步：计算时空复杂度

时间复杂度：分析最坏、平均情况，用大O表示法。空间复杂度：考虑递归栈或额外数据结构。

第四步：回答具体问题或指出改进

根据题目要求回答“代码是否正确？”“如何优化？”等问题。

完整答题模板示例

以“两个有序顺序表合并”为例：

```
（1）算法设计思想：
采用双指针法。设i、j分别指向两个有序表的起始位置，k指向新表的起始位置。
依次比较a[i]和b[j]，将较小者放入c[k]，相应指针后移。
当一个表遍历完时，将另一个表的剩余元素直接复制到c中。

（2）C语言描述：
bool mergeTwo(SqList a, SqList b, SqList *c) {
if (a.length + b.length > c->capacity) return false;
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
if (a.data[i] <= b.data[j])
c->data[k++] = a.data[i++];
else
c->data[k++] = b.data[j++];
}
while (i < a.length) c->data[k++] = a.data[i++];
while (j < b.length) c->data[k++] = b.data[j++];
c->length = k;
return true;
}

（3）时空复杂度：
时间复杂度：O(m+n)，其中m、n分别为两个顺序表的长度。
空间复杂度：O(1)，仅使用了常数个辅助变量。
```

四、高频考点与备考策略

按考频排序的必背考点

| 排名 | 考点 | 近10年考频 | 核心要求 |
|---|---|---|---|
| 1 | 树与二叉树 | 15次 | 遍历（递归/非递归）、BST、AVL、哈夫曼 |
| 2 | 图 | 14次 | 存储结构、DFS/BFS、拓扑排序、最短路径 |
| 3 | 排序算法 | 14次 | 快排/归并/堆排的时空复杂度与稳定性 |
| 4 | 查找 | 12次 | 折半查找、哈希表、B树 |
| 5 | 线性表 | 11次 | 链表操作、顺序表特性 |
| 6 | 栈和队列 | 8次 | 循环队列判空判满、进出序列合法性 |

三大高频陷阱

| 陷阱 | 后果 | 应对 |
|---|---|---|
| AVL旋转判断错误 | 后续全盘皆输 | 熟记LL/RR/LR/RL四种失衡类型 |
| DFS/BFS漏写visited | 死循环，年均扣3分 | 每次遍历前初始化visited数组 |
| 排序稳定性写错 | 直接丢2分 | 快排“不稳定”必须记牢 |

备考三阶段

筑基期（6-8周）：精读严蔚敏《数据结构》+王道《高分笔记》，手写“万能模板卡”——链表逆置5行、二叉树前中后序递归/非递归双版本、Kruskal+Prim伪代码。每天手写1-2道算法题（如链表反转、二叉树层序遍历）。

强化期（4-5周）：近10年408数据结构大题，按“读题→画模型→写伪代码→算复杂度”四步限时25分钟。把王道课后题彻底搞懂，其中的知识点融会贯通。

冲刺期（3周）：周三、周六上午8:30-11:30全真模考。错题用三色笔标记——红色思路漏洞、绿色边界条件、蓝色笔误。

五、三大模块核心代码模板

1. 链表：哨兵节点模板

```c
ListNode dummy = (ListNode)malloc(sizeof(ListNode));
dummy->next = head;
// 插入/删除只需改dummy->next，避免头节点特判
```

反转链表（双指针三步走）：
```c
ListNode reverseList(ListNode head) {
ListNode prev = NULL, curr = head, *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
```

2. 二叉树：递归三问模板

```c
// 前序遍历（递归）
void preorder(TreeNode* root) {
if (root == NULL) return;
visit(root); // 当前节点做什么？
preorder(root->left); // 左子树
preorder(root->right); // 右子树
}

// 层序遍历（队列）
void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
visit(node);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
```

3. 图：DFS三色标记模板

```c
// visited数组：0=未访问，1=访问中，2=已回溯
void dfs(Graph G, int v, int visited) {
visited[v] = 1; // 灰色：正在访问
for (每个邻接点 w) {
if (visited[w] == 0) dfs(G, w, visited);
else if (visited[w] == 1) // 发现环
}
visited[v] = 2; // 黑色：已回溯
}
```

六、考场速查卡

| 题型 | 答题要点 | 时间建议 |
|---|---|---|
| 算法设计题 | 思路说明（1-2句）→ 伪代码/代码 → 复杂度分析 | 15-20分钟 |
| 代码阅读题 | 功能概括 → 逻辑分析 → 时空复杂度 → 改进建议 | 10-15分钟 |
| 复杂度分析题 | 循环/递归深度分析，大O表示法 | 5分钟 |

数据结构45分，是408中最能拉开差距的模块。算法题20-25分，完全可以通过模板+真题+手写的系统训练拿到。不用去刷LeetCode海量题目，把王道课后题彻底搞懂就足够了。从现在开始，每天手写1-2道算法题（链表反转、二叉树遍历、排序实现），把“三问格式”（设计思想→代码→复杂度）练成肌肉记忆。考场上遇到算法题，按照“读题→画模型→写伪代码→算复杂度”四步走，即使代码写不完整，写出思路和复杂度也能拿到大部分分数。数据结构算法题的每一分，都值得你用手写代码去换。