---

0. 基础与复杂度（✅ 必考）

• 数据结构三要素：逻辑结构 / 存储结构 / 操作（算法）
• 时间复杂度：
• 符号：O（上界）、Ω（下界）、Θ（紧确界）
• 场景：最好/最坏/平均（如快排、查找）
• 计算方法：求和法、递推法（展开/代入）、主定理（分治类）
• 空间复杂度：
• 关注辅助空间（不包括输入）
• 递归算法：栈空间 = 递归深度
• 算法特性：正确性、可读性、健壮性、效率（时间+空间）

⚠️ 常考题型：三重循环复杂度（如 for i=1..n; for j=1..i; for k=1..j）、递归式求解（如 T(n)=2T(n/2)+n）

---

1. 线性表

1.1 顺序表

• 地址计算：Loc(a[i]) = Loc(a[0]) + i × size
• 随机访问：O(1)；插入/删除平均移动 n/2 个元素 → O(n)
• 扩容：通常倍增（2倍），摊还复杂度 O(1)（了解即可）

1.2 链表（🔥 高频）

• 类型：单链表 / 双链表 / 循环链表 / 静态链表（数组模拟指针）
• 头指针 vs 头结点：
• 带头结点：判空条件为 head->next == NULL
• 不带头结点：判空为 head == NULL
• 操作复杂度：
• 按位查找：O(n)
• 按值查找：O(n)
• 典型题（✅ 必练手写）：
• 建表（头插/尾插）
• 原地逆置（三指针法）
• 合并两个有序链表
• 删除指定值所有结点
• 找中间结点（快慢指针）
• 判环与找环入口（Floyd 快慢指针，⚠️ 常考）

---

2. 栈与队列（✅ 高频）

2.1 栈

• 实现：顺序栈 / 链栈
• 应用：
• 括号匹配
• 表达式求值（中缀 → 后缀；后缀求值）
• 递归调用栈（理解递归本质）
• 合法出栈序列判断（⚠️ 常考选择题）：
• 模拟入栈出栈过程
• 或用“栈混洗”性质（如：3 1 2 不合法）

2.2 队列

• 顺序队列“假溢出”问题 → 引出循环队列
• 循环队列判空/判满（⚠️ 必背）：

方法	队空条件	队满条件	特点
牺牲一单元	front == rear	(rear + 1) % maxSize == front	最常用
引入 size	size == 0	size == maxSize	无浪费
引入 tag	front == rear && tag == 0	front == rear && tag == 1	较少考

• 链队列：带头结点更方便
• 双端队列、优先队列：了解概念即可（如优先队列 ≈ 堆）

---

3. 串（部分院校考）

• 存储：定长顺序串 / 堆分配存储（动态）
• 朴素匹配：O(nm)
• KMP 算法（✅ 必考手算）：
• next[j] = 模式串前 j 个字符的最长相等真前后缀长度
• 构造过程：前缀表 → 右移 → 首位变 -1（或 0，看教材）
• nextval：优化相同字符重复比较
• 复杂度：KMP 为 O(n + m)

⚠️ 考法：给定模式串 “ababc”，手算 next/nextval 数组

---

4. 数组、矩阵与广义表

• 多维数组地址计算（行优先/列优先）：
• 二维行优先：Loc[i][j] = Loc[0][0] + (i×n + j)×size
• 特殊矩阵压缩存储：
• 对称矩阵：只存下三角（含对角线）
• 三角矩阵：类似
• 稀疏矩阵：三元组表 / 十字链表（后者支持高效运算）
• 广义表（若考）：
• 长度 = 第一层元素个数
• 深度 = 嵌套层数（递归定义）
• 表头/表尾：如 (a,(b,c)) 的 head = a，tail = ((b,c))

---

5. 树与二叉树（🔥 超高频）

5.1 树的基本概念

• 度、层次、深度（根为1）、高度（叶为1）
• 存储结构：
• 双亲表示法（查父快）
• 孩子表示法（查子快）
• 孩子兄弟表示法 → 可转为二叉树（左孩右兄）

5.2 二叉树性质（✅ 必背）

• 第 i 层最多 $2^{i-1}$ 个结点
• 高度为 h 的二叉树最多 $2^h – 1$ 个结点
• 完全二叉树：
• 按层编号，从 1 到 n
• 父子关系：parent = i/2，left = 2i，right = 2i+1
• 区分：满二叉树 ⊂ 完全二叉树 ⊂ 二叉树

5.3 二叉树遍历（✅ 必考）

• 四种遍历：先序（根左右）、中序（左根右）、后序（左右根）、层序（队列）
• 递归 & 非递归实现：
• 先/中/后：用栈模拟
• 层序：用队列
• 由遍历序列建树（⚠️ 高频）：
• 先+中 → 唯一
• 后+中 → 唯一
• 先+后 → 不唯一（除非是真二叉树）
• 线索二叉树：
• 线索：空指针改为前驱/后继
• 中序线索树可直接找前驱后继（无需栈）

5.4 哈夫曼树与编码（✅ 高频）

• 构造：每次选两个最小权值合并（可用 priority_queue）
• WPL = 所有叶结点（权值 × 路径长度）之和
• 哈夫曼编码：
• 前缀码（任一编码不是另一编码前缀）
• 编码长度 = 路径长度
• 不唯一，但 WPL 唯一

⚠️ 考法：给权值 {5,29,7,8,14,23,3,11}，构造哈夫曼树并求 WPL

---

6. 图（✅ 高频）

6.1 基本概念

• 有向图/无向图、简单图、度（无向）、入度/出度（有向）
• 连通（无向）/强连通（有向）
• 存储结构对比：

	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V+E)
适合图类型	稠密图	稀疏图
查边存在	O(1)	O(度)

6.2 遍历

• DFS：递归或栈，生成深度优先生成树
• BFS：队列，生成广度优先生成树
• 复杂度：O(V+E)

6.3 经典算法（✅ 必会手算）

• 最小生成树（MST）：
• Prim：从点出发，适合稠密图（邻接矩阵）
• Kruskal：从边出发 + 并查集，适合稀疏图（邻接表）
• 最短路径：
• Dijkstra：单源、非负权（⚠️ 高频手算）
• Floyd：多源、可有负权（但不能有负环），动态规划
• Bellman-Ford：了解（可处理负权，检测负环）
• 拓扑排序（AOV 网）：
• 入度为 0 的顶点入队
• 若无法排完 → 有环
• 关键路径（AOE 网）：
• 事件最早时间 ve、最迟时间 vl
• 活动最早开始 e、最迟开始 l
• 关键活动：e == l
• 总工期 = 最后事件的 ve

---

7. 查找（🔥 超高频）

7.1 线性表查找

• 顺序查找：O(n)，可用于无序表
• 折半查找（✅ 必考）：
• 前提：有序顺序表
• 判定树：完全二叉树（不成功查找的外部结点）
• ASL 成功 ≈ log₂(n+1) – 1

7.2 树表查找

• 二叉排序树（BST）：
• 中序遍历为有序序列
• 平均查找 O(log n)，最坏（退化为链）O(n)
• 删除：分三种情况（无子、单子、双子）
• 平衡二叉树（AVL）（⚠️ 必考旋转）：
• 平衡因子 ∈ {-1, 0, 1}
• 四种旋转：
  • LL：右旋
  • RR：左旋
  • LR：先左旋再右旋
  • RL：先右旋再左旋
• 插入后从最低不平衡点开始调整
• B⁻/B⁺树（概念题）：
• m 阶 B⁻树：根至少 2 个子，非根至少 ⌈m/2⌉ 个子
• B⁺树：所有关键字在叶结点，叶结点链式连接（数据库索引）

7.3 散列（哈希）（✅ 高频）

• 冲突处理：
• 开放定址：线性探测（易聚集）、二次探测（缓解）、双散列
• 链地址法（拉链法）：更常用，删除方便
• 装填因子 α = n / m（n: 元素数，m: 表长）
• 查找效率：
• 成功 ASL：与 α 正相关
• 失败 ASL：开放定址需探到空单元

⚠️ 考法：给关键字序列和哈希函数，画出哈希表，计算 ASL

---

8. 排序（🔥 超高频）

8.1 基本概念

• 稳定性：相等元素相对位置是否改变
• 原地性：是否只用 O(1) 辅助空间
• 比较类 vs 非比较类（如基数排序）
• 内排序 vs 外排序（了解）

8.2 重点排序算法（✅ 必会手推）

算法	时间（最好/平均/最坏）	稳定	原地	备注
直接插入	O(n) / O(n²) / O(n²)	✅	✅	初始有序时最优
希尔排序	依赖增量	❌	✅	增量序列常考（如 n/2, n/4…）
冒泡排序	O(n) / O(n²) / O(n²)	✅	✅	可加 flag 优化
快速排序	O(n log n) / O(n log n) / O(n²)	❌	⚠️（递归栈）	⚠️ 高频大题：手写 partition
简单选择	O(n²) 全部	❌	✅	交换次数少
堆排序	O(n log n) 全部	❌	✅	大根堆 → 升序；建堆 O(n)
归并排序	O(n log n) 全部	✅	❌	需 O(n) 辅助空间
基数排序	O(d(n+r))	✅	❌	d: 位数，r: 基数

💡 口诀：快希选堆不稳定，插冒归基都稳定
⚠️ 常考：给初始序列，写出快排/堆排序每一趟结果；问稳定性/比较次数

---

9. 常考综合题型清单（刷题优先级）

题型	典型考法	建议
复杂度	三重循环、递推式	掌握求和与主定理
链表	判空（带头/不带头）、逆置、合并、快慢指针	手写代码，注意边界
栈	表达式转换、合法出栈序列	模拟 + 规律记忆
树	遍历互推、完全二叉树编号、哈夫曼 WPL	画图辅助
图	Dijkstra/Floyd 手算、MST、拓扑序、关键路径	步骤化训练
查找	BST 删除、AVL 旋转、哈希冲突处理	熟悉调整过程
排序	手推每一趟、问稳定性/趟数/比较次数	对比记忆

---

---