高频考点速记
使用方式
- 这一页适合考前 5-10 分钟快速扫一遍。
- 每章只保留最容易考、最容易混、最容易丢分的内容。
- 如果发现某一条完全说不清，立即回主线章节补。
第1章 绪论
| 必背点 | 快速结论 |
|---|---|
| 数据结构三要素 | 逻辑结构、存储结构、数据运算 |
| 逻辑结构 | 集合、线性、树形、图状 |
| 存储结构 | 顺序、链式、索引、散列 |
| 算法五性 | 有穷性、确定性、可行性、输入、输出 |
| 时间复杂度 | 只保留最高阶，忽略常数与低阶 |
| 空间复杂度 | 重点看辅助空间，不算输入本身 |
第2章 线性表
| 高频点 | 快速结论 |
|---|---|
| 顺序表插删 | 平均移动元素，时间 O(n) |
| 顺序表按位查找 | O(1) |
| 单链表按位查找 | O(n) |
| 单链表插入/删除 | 已知前驱时 O(1) |
| 双链表 | 删除结点更方便，但存储开销更大 |
| 循环链表 | 判空和遍历终止条件易错 |
| 静态链表 | 用数组模拟链表，适合理解指针思想 |
| 常考模型 | 反转链表、倒数第 k 个、找公共后缀、去重、重排 |
第3章 栈与队列
| 高频点 | 快速结论 |
|---|---|
| 栈 | 后进先出，适合递归/回溯/表达式 |
| 队列 | 先进先出，适合层序遍历、BFS |
| 顺序栈共享 | 两栈共享数组可提高空间利用率 |
| 循环队列判空 | front == rear |
| 循环队列判满 | (rear + 1) % MaxSize == front |
| 队列长度 | (rear - front + MaxSize) % MaxSize |
| 常考模型 | 括号匹配、表达式求值、层序遍历、滑动窗口 |
第4章 串
| 高频点 | 快速结论 |
|---|---|
| 朴素匹配 | 最坏 O(nm) |
| KMP 核心 | 失配时主串指针不回退 |
| next 数组 | 表示模式串前缀和后缀的最大公共长度信息 |
| nextval | 对 next 的进一步优化，减少无效比较 |
| 常考点 | 手推 next / nextval、说明 KMP 为什么快 |
第5章 树与二叉树
| 高频点 | 快速结论 |
|---|---|
| 树的度 | 结点孩子个数 |
| 树的高度/深度 | 根到最深结点的层数定义要统一 |
| 二叉树性质 | 第 i 层最多 2^(i-1) 个结点 |
| 满二叉树 / 完全二叉树 | 定义一定要分清 |
| 遍历 | 先序、中序、后序、层序 |
| 线索二叉树 | 空指针域改作前驱/后继线索 |
| Huffman 树 | WPL 最小，但不一定是完全二叉树 |
| 并查集 | 合并 + 查找，路径压缩和按秩合并高频 |
第6章 图
| 高频点 | 快速结论 |
|---|---|
| 存储 | 邻接矩阵适合稠密图，邻接表适合稀疏图 |
| BFS | 类似树的层序遍历 |
| DFS | 类似树的先序递归 |
| 最小生成树 | Prim、Kruskal |
| 最短路径 | Dijkstra、Floyd |
| AOV 网 | 拓扑排序 |
| AOE 网 | 关键路径 |
| 常考点 | 度、入度、出度、连通性、欧拉图、拓扑序唯一性 |
第7章 查找
| 高频点 | 快速结论 |
|---|---|
| 顺序查找 | 适合无序表 |
| 折半查找 | 只适合有序顺序表 |
| 分块查找 | 介于顺序和折半之间 |
| BST | 中序遍历有序 |
| AVL | 任一结点左右子树高度差不超过 1 |
| 散列表 | 查找性能取决于装填因子和冲突处理 |
| 常考点 | BST 判定、插删、折半边界、哈希冲突 |
第8章 排序
| 高频点 | 快速结论 |
|---|---|
| 插入类 | 直接插入、折半插入、希尔 |
| 交换类 | 冒泡、快速 |
| 选择类 | 简单选择、堆排序 |
| 归并排序 | 稳定，时间 O(n log n)，需要额外空间 |
| 基数排序 | 不基于比较 |
| 稳定性常考 | 直接插入、冒泡、归并、基数稳定；选择、快速、堆、希尔不稳定 |
| 常考点 | 平均/最坏复杂度、稳定性、是否原地 |
最后一分钟必背
- 单链表删除结点，关键是前驱指针。
- BST 判断不能只看父子，必须看整棵子树的上下界。
- WPL 只统计叶结点。
- 邻接矩阵中：行是出度，列是入度。
- 判断拓扑序是否唯一，看每一步入度为 0 的顶点是否唯一。
- KMP 失配时，主串指针不回退。