总体知识大纲
第一部分：绪论
| 考点 | 掌握程度 | 关键内容 |
|---|---|---|
| 数据结构三要素 | 理解 | 逻辑结构、存储结构、数据运算 |
| 逻辑结构分类 | 掌握 | 线性、树形、图形、集合 |
| 存储结构分类 | 掌握 | 顺序、链式、索引、散列 |
| 时间复杂度分析 | 熟练 | 大O表示法，各种循环嵌套分析 |
| 空间复杂度分析 | 掌握 | 迭代O(1)，递归O(n) |
第二部分：线性表
| 考点 | 掌握程度 | 关键内容 |
|---|---|---|
| 顺序表操作 | 熟练 | 插入/删除/查找，平均移动次数 |
| 单链表操作 | 熟练 | 头插法、尾插法、插入/删除 |
| 双链表 | 掌握 | 前驱后驱指针的修改顺序 |
| 循环链表 | 了解 | 判空条件 |
| 静态链表 | 了解 | 游标实现 |
| ◆ 链表逆置 | 掌握 | 头插法，O(n) |
| ◆ 链表快慢指针 | 掌握 | 找中间结点、找环 |
第三部分：栈、队列和数组
| 考点 | 掌握程度 | 关键内容 |
|---|---|---|
| 栈（LIFO） | 熟练 | 顺序栈、链式栈 |
| 队列（FIFO） | 熟练 | 循环队列判空判满 |
| 双端队列 | 掌握 | 输入/输出受限 |
| 栈的应用 | 掌握 | 括号匹配、中缀转后缀、函数调用 |
| 队列的应用 | 掌握 | 层次遍历、BFS、缓冲区 |
| 矩阵压缩存储 | 掌握 | 对称/三角/三对角/稀疏 |
第四部分：串
| 考点 | 掌握程度 | 关键内容 |
|---|---|---|
| BF算法 | 掌握 | 暴力匹配，O(nm) |
| ◆ KMP算法 | 熟练 | next数组、nextval数组 |
| KMP匹配过程 | 掌握 | i不回溯，j回退 |
第五部分：树与二叉树
| 考点 | 掌握程度 | 关键内容 |
|---|---|---|
| 二叉树性质 | 熟练 | n₀=n₂+1，完全二叉树公式 |
| 二叉树遍历 | 熟练 | 前/中/后序（递归+非递归）、层序 |
| 由遍历序列确定树 | 掌握 | 前+中、后+中、层+中 |
| 线索二叉树 | 掌握 | 中序线索化，前驱后继查找 |
| 树与森林的转换 | 掌握 | 孩子兄弟表示法 |
| ◆ 哈夫曼树 | 熟练 | 构造过程、WPL计算、哈夫曼编码 |
| 并查集 | 了解 | Find、Union、路径压缩 |
第六部分：图
| 考点 | 掌握程度 | 关键内容 |
|---|---|---|
| 图的存储 | 掌握 | 邻接矩阵、邻接表、十字链表 |
| DFS/BFS | 熟练 | 遍历序列、时间复杂度 |
| ◆ 最小生成树 | 掌握 | Prim（选点）、Kruskal（选边） |
| ◆ 最短路径 | 掌握 | Dijkstra（单源）、Floyd（多源） |
| ◆ 拓扑排序 | 熟练 | AOV网、入度为0出队 |
| ◆ 关键路径 | 掌握 | AOE网、ve/vl/e/l/d |
第七部分：查找
| 考点 | 掌握程度 | 关键内容 |
|---|---|---|
| 顺序查找 | 掌握 | 哨兵优化 |
| 折半查找 | 熟练 | 判定树、ASL计算 |
| BST | 掌握 | 查找/插入/删除 |
| ◆ AVL调整 | 熟练 | LL/RR/LR/RL旋转 |
| 红黑树 | 了解 | 5个性质，黑高 |
| ◆ B树 | 掌握 | 插入分裂、删除合并 |
| ◆ 散列表 | 熟练 | 构造、冲突处理、ASL计算 |
第八部分：排序
| 排序算法 | 时间复杂度 | 空间 | 稳定性 |
|---|---|---|---|
| 直接插入 | O(n²) | O(1) | 稳定 |
| 折半插入 | O(n²) | O(1) | 稳定 |
| 希尔 | O(n^1.3)~O(n²) | O(1) | 不稳定 |
| 冒泡 | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 |
| 简单选择 | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n) | 稳定 |
| 基数排序 | O(d(n+r)) | O(r) | 稳定 |
综合难度分布
难度等级：★ 了解 ★★ 掌握 ★★★ 熟练（高频考点）
p1 绪论 ★★ 基本概念 + 复杂度分析
p2 线性表 ★★★ 链表操作（大题高频）
p3 栈队列数组 ★★★ 循环队列判空判满
p4 串 ★★★ KMP的next数组计算
p5 树与二叉树 ★★★★ 遍历 + 哈夫曼（计算题）
p6 图 ★★★★ 最短路 + 拓扑 + 关键路径
p7 查找 ★★★★ AVL + B树 + 散列表ASL
p8 排序 ★★★★★ 快排 + 堆排 + 外部排序
命题规律分析
408 数据结构部分的题型分布：
- 选择题（11道，约22分）：覆盖各章概念，重点在复杂度、二叉树性质、图算法性质、排序算法比较。
- 综合应用题（1-2道，约23分）：链表操作题、二叉树遍历题、图算法题、排序过程题。
- 出题趋势：越来越注重对算法过程的理解（手工模拟能力），而不仅仅是记忆。
复习策略建议
- 先理解再记忆：数据结构不是背出来的，是理解出来的。先理解逻辑，再记公式。
- 动手画图：链表指针修改、树的旋转、图的遍历——一定要画图帮助理解。
- 手算模拟：快排划分、Dijkstra、AVL调整、B树操作——能从头到尾手算一遍才算真正掌握。
- 代码与算法并重：看懂 ≠ 会写。408统考不要求写完整代码，但算法思想和关键步骤必须写清楚。
- 重点突出：排序、查找、树、图是四大重点章节，占分最多，需要重点投入时间。