考研笔记

数据结构全书地图

这一页是数据结构的总入口。 上篇是全书结构与分档说明，下篇是第 1~4 章的入口（2026-09-23 补建为 13 页简写档概念页，另有 5 张速查表）。

全书结构

flowchart TD
    C1["第 1 章 绪论<br/>复杂度与渐进符号"]
    C2["第 2 章 线性表<br/>顺序表 · 链表"]
    C3["第 3 章 栈、队列和数组<br/><b>出栈序列 · 表达式求值</b><br/>循环队列 · 特殊矩阵"]
    C4["第 4 章 串<br/>KMP"]
    C5["第 5 章 树与二叉树<br/><b>n₀ = n₂ + 1</b>"]
    C6["第 6 章 图<br/>存储 · 遍历 · 应用"]
    C7["第 7 章 查找<br/><b>ASL 是唯一的尺子</b>"]
    C8["第 8 章 排序<br/><b>表 8.1</b>"]

    C1 --> C2 --> C3 --> C4
    C2 -.->|"链式存储的思想"| C5
    C3 -.->|"栈用于遍历<br/>队列用于层次遍历/BFS"| C5
    C3 -.->|"队列用于 BFS"| C6
    C5 ==>|"BST/AVL/红黑树/B树<br/>全部建立在二叉树性质之上"| C7
    C5 -.->|"堆的下标运算<br/>哈夫曼树与 WPL"| C8
    C6 -.->|"并查集判回路"| C5
    C7 -.->|"折半查找的判定树<br/>与「仅顺序存储」"| C8

    classDef c fill:#eeeeee,stroke:#9e9e9e
    classDef a fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef b fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    class C1,C2,C3,C4 c
    class C7 a
    class C5,C6,C8 b

分档与导航

本套笔记按用户的复习重点分三档建设（2026-09-08 拍板 A + B + C 全做）：

档章做法产出
A · 全深度第 7 章 查找王道级细节 + 手算模板 + 边界11 页 2493 行
B · 差集式第 5、6、8 章不重讲算法，只写「教材口径 − 已会的」18 页 3561 行
C · 简写档第 1~4 章原为速查表；第 3 章的栈 2026-09-16 先建 2 页，2026-09-23 补齐其余 11 页，只写教材口径、手算方法和边界13 页 + 5 张表
章索引名词库页数
第 1~4 章合并索引60 条13（+ 5 张速查表）
第 5 章 树与二叉树索引33 条6
第 6 章 图索引28 条5
第 7 章 查找 ★索引61 条11
第 8 章 排序索引30 条7
合计5 个索引212 条名词 / 217 行范围限定清单42 页

贯穿全书的六条隐线

① 虚构 个失败结点（第 7 章出现三次）

出处叫法数量
7.2.2 折半查找方形叶结点 / 失败结点
7.3.3 红黑树外部叶结点 / NULL 结点
7.4.1 B 树不带信息的叶结点

作用完全一样：把「查找失败」变成一个可以指到的位置，从而让「查找长度」对失败也有定义。B 树最大高度公式正是靠这一条把层数和关键字数接起来的。

② 长出三条独立结论

结论出处
完全二叉树由 的奇偶直接求 5.2.1
二叉链表有 个空链域 → 线索二叉树的全部原料5.2.2 → 5.3.2
哈夫曼树是正则二叉树 ⇒ 结点总数 5.5.1

教材对这条性质加了注意框：「希望读者牢记并灵活应用。」全书少数直接说「牢记」的地方。

③ 「仅顺序存储」的共同原因是需要随机存取

位置算法
7.2.2折半查找
8.2.2 / 8.2.3折半插入排序、希尔排序
8.3.2快速排序
8.4.2堆排序

五个算法一个理由：链表做不到 随机存取。 记住这条，表 8.1 的「适用性」那一栏不用背。

④ 分母不同（第 7 章的最高频失分点）

量分母
成功记录数
不成功失败结点数（一般 ）；散列表是值域大小
装填因子 表长

散列表一道题里 、、 同时出现——见 7.5.4。

⑤ 三个 算法，空间分别是 / /

算法空间原因
堆排序原地筛选
快速排序递归工作栈
二路归并辅助数组

教材 8.6.2 因此说「堆排序所需的辅助空间少于快速排序」。 见 8.6。

⑥ 教材口径 ≠ 真题 / 工程口径（有算竞背景最容易踩）

位置教材口径另一种口径
7.4.1 B 树的「叶结点」失败结点（不带信息）408 真题：最底层的终端结点（教材脚注明说）
7.4.2 B+树分支结点存子树的最大关键字工程实现常存最小
5.5.2 并查集的根S[x] 为负数，绝对值是成员数量算竞 fa[x]==x 自环
4.2.2 KMP 的 next教材正文：下标从 1，next[1]=0算竞 fail[0]=-1；2015、2019、2024 的王道解析也按从 0 起算
8.3.2 快排的 Partition枢轴取末位、填坑、先 后 Hoare / Lomuto 随意
6.4.2 Dijkstra朴素 逐轮填表堆优化
3.1.1 出栈序列计数公式只给结论，带条件一律穷举组合数学的反射法 / 递推

这一栏是本套笔记特有的价值来源——OS/CO 笔记里对应的位置是「用户提过的疑问」，DS 没有素材，改用这个。

下篇 · 第 1~4 章入口

四章合成一张总览：数据结构第 1~4 章总览。13 页简写档概念页，覆盖 41 道统考选择题和 1 道队列设计题；第 2 章的 9 道算法大题在代码附录。

章页真题最密的一页
第 1 章 绪论21.2 算法和算法评价：6 道复杂度题
第 2 章 线性表32.3.3~2.3.6 双链表、循环链表与静态链表：指针语句题
第 3 章 栈、队列和数组63.1.1 + 3.3：14 道；3.4：6 道
第 4 章 串24.2.2~4.2.3 KMP：3 道手工模拟

5 张速查表保留，作为公式和对照表的集中出处：

表覆盖核心内容
全书复杂度总表1.2.2 + 全书渐进符号；查找/排序/图/树的复杂度汇总
顺序表与链表2.2 + 2.32.3.6 的四个维度；四种链表对照；静态链表
栈与队列的判空判满3.1 + 3.2循环队列的三种方案；假溢出；共享栈
特殊矩阵压缩存储的下标公式3.4.2~3.4.4对称 / 三角 / 三对角（）/ 稀疏
KMP 的 next 与 nextval4.2.2 + 4.2.3两个教材例的逐项验算；next[1]=0、next[2]=1 固定

第 1~4 章最值得单独看一眼的五个点：

  1. 出栈序列的个数是卡特兰数（ 时是 5 不是 6），带条件计数一律「锁死栈内容 + 数空位」——见 3.1.1。
  2. 循环队列换了指针约定就先画空队列、再入队一个元素（2011、2014）——见 3.2。
  3. 矩阵下标不背公式，数目标元素前面有几个元素（2016、2018、2020）——见 3.4。
  4. KMP 真题的下标口径看题干；比较次数、右滑距离与口径无关——见 4.2.2。
  5. 两层循环不一定是 ：2014 是 ，2022 是 ——见 1.2。

全书复习顺序

步内容理由
1第 5 章 的 5.2（二叉树性质）第 7 章全部建立在它之上
2第 7 章 全章★分值最集中
3第 5 章其余（遍历、线索、转换、哈夫曼、并查集）第 7、8 章都要用
4第 8 章，从 8.6 的表 8.1 倒着看先建框架再补细节
5第 6 章 的 6.2（四种存储）+ 6.4.5（关键路径）算竞不覆盖的两块
6第 6 章其余算竞背景可快速通过
7第 1~4 章：先 3.1.1 + 3.3，再 1.2、3.4、3.2、4.241 道选择题，总览里有顺序
85 张速查表公式集中复查
9五个名词库的范围限定清单（合计 217 行）考前扫

时间紧时的最小集：5.2 的性质 → 第 7 章全章 → 表 8.1 默写 → 表 6.1 默写 → 关键路径一道 → 出栈序列判定准则 + 中缀转后缀 → 1.2 复杂度 + 3.4 矩阵下标 → 5 张速查表 → 217 行清单。

跨科链接

链接

反向链接