来源：
c:\Users\26947\Desktop\考试\专业课速记\04_数据结构与算法.md用途：分类保存“原文完整迁移”基准，供完整阅读与逐字核对；以下正文保持源文件原样，不压缩、不改写。
数据结构与算法¶
1. 复杂度必背¶
| 操作/算法 | 常见复杂度 |
|---|---|
| 数组随机访问 | O(1) |
| 顺序查找 | O(n) |
| 二分查找 | O(log n) |
| 哈希表平均查找 | O(1) |
| 平衡二叉搜索树查找 | O(log n) |
| 普通二叉搜索树最坏查找 | O(n) |
| 冒泡排序 | O(n²) |
| 插入排序 | O(n²)，近乎有序时较快 |
| 归并排序 | O(n log n) |
| 快速排序平均 | O(n log n) |
| 快速排序最坏 | O(n²) |
| 堆排序 | O(n log n) |
2. 线性表与广义表¶
线性表：n 个原子元素（不可再分）的有限序列。
广义表：线性表的推广——元素既可以是原子，也可以是子表（另一个广义表）。记作 LS = (a₁, a₂, …, aₙ)。
| 广义表 | 含义 | 长度 | 深度 |
|---|---|---|---|
| A = () | 空表 | 0 | 1 |
| B = (e) | 只含一个原子 | 1 | 1 |
| C = (a, (b, c)) | 原子 + 子表 | 2 | 2 |
| D = (A, B, C) = ((), (e), (a, (b, c))) | 元素全是子表 | 3 | 3 |
| E = (a, E) | 递归表（自己包含自己） | 2 | ∞ |
- 长度 = 最外层元素的个数。
- 深度 = 括号最大嵌套层数（原子深度为 0，空表深度为 1，递归表深度为无穷）。
表头与表尾运算（最高频考点）¶
- 表头 GetHead(LS)：第一个元素——可以是原子，也可以是子表。
- 表尾 GetTail(LS)：除去第一个元素后，剩余元素组成的表——永远是一个广义表。
例：L = (a, (b, c), d)
- GetHead(L) = a（原子）
- GetTail(L) = ((b, c), d)——注意外面套一层括号，因为表尾本身是"装着剩余元素的表"
- GetHead(GetTail(L)) = (b, c)（子表）
运算链套路："取第 k 个元素 = 先取 k−1 次表尾，再取一次表头"。
例：L = (a, b, c, d)，取第 2 个元素：GetHead(GetTail(L)) = b。
三个易错点¶
- 表尾永远套一层括号：GetTail((a, (b, c))) = ((b, c))，不是 (b, c)。
- 空表不能取表头表尾：() 没有第一个元素，运算无意义。
- 表头可以是原子或子表，表尾一定是表——两者类型不对称，这是与"第一个元素/其余元素"直觉的最大区别。
存储结构：广义表常用链式存储（头尾指针存储法），原子节点与表节点分开表示。
银行场景类比：客户资产清单 = (活期存款, (股票组合A, (债券, 国债逆回购)), 黄金)——清单里既有单笔资产（原子），也有整包的投资组合（子表），组合里还能再嵌套组合。
3. 排序特点¶
- 稳定排序：相同关键字元素的相对顺序不变。
- 归并排序、插入排序、冒泡排序稳定。
- 快速排序、堆排序通常不稳定。
3. 树¶
- 二叉搜索树：左子树所有节点小于根，右子树所有节点大于根。
- 二叉搜索树中序遍历结果是递增序列。
- 大顶堆：根节点最大；小顶堆：根节点最小。
- AVL 树通过旋转保持平衡。
- B+ 树常用于数据库索引和文件系统。
4. 图算法¶
- BFS：广度优先，适合求无权图最短路径。
- DFS：深度优先，适合遍历、连通性、拓扑相关问题。
- Dijkstra：非负权图单源最短路。
- Floyd：多源最短路，复杂度通常为 O(n³)。
- Kruskal、Prim：最小生成树。
- 拓扑排序：有向无环图。
🟡 本分册解释为通用计算机知识补充，可能与你老师讲的不完全一致；专业范围以《考试大纲》"金融监管计算机类"部分为准。