一页纸总结

考前一天看这一页

线性表

• 顺序表：随机访问快，插删慢。
• 链表：访问慢，局部插删快。
• 单链表题三板斧：前驱、快慢指针、反转。

栈与队列

• 栈：递归、回溯、表达式。
• 队列：层序、BFS、滑动窗口。
• 循环队列三公式必须直接默写。

串

• 朴素匹配：主串回退。
• KMP：主串不回退。
• 必会手推 next。

树

• 遍历：先、中、后、层。
• BST：中序有序。
• AVL：高度差不超过 1。
• WPL：只算叶子。

图

• BFS：队列。
• DFS：递归/栈。
• MST：Prim / Kruskal。
• 最短路：Dijkstra / Floyd。
• DAG：拓扑排序。

查找

• 折半查找只用于有序顺序表。
• 散列表重冲突处理和装填因子。

排序

稳定	不稳定
插入、冒泡、归并、基数	选择、快速、堆、希尔

最坏 O(n^2)	最坏 O(n log n)
插入、冒泡、选择、快排	堆排、归并

高频失分点

• 头结点 != 首元结点
• 行出列入
• BST 不是只看父子
• 快排不稳定
• Dijkstra 不能有负权边
• 拓扑排序只对 DAG 有意义

高频真题模型

• 链表指针：2009、2012、2019
• 二分变体：2011
• 原地哈希：2018
• 三指针区间：2020
• 欧拉图 / 入度 / 拓扑：2021、2023、2024