1
Include 必须有（公共功能）
2
Extend 可以有（可选增强）
3
Generalization 是一种（继承关系）

1
无向完全图：n(n-1)/2 条边
2
有向完全图：n(n-1) 条边（有向 = 无向 × 2）

1
Prim 选点（就近扩展）→ 密图 O(n²)
2
Kruskal 选边（最短优先）→ 疏图 O(eloge)

1
有向图：非零元素 = E（边数）
2
无向图：非零元素 = 2E（矩阵对称）

1
核心公式：
2
  n（总结点数）= 分支数 + 1
3
  分支数 = Σ 各结点度数之和
4

5
度：结点的子树个数
6
叶子结点：度为0的结点
7

8
解题步骤：
9
  1. 已知总结点数 n 和各结点度数之和 → 求分支数 → 求叶子数
10
  2. 分支数 = n - 1（树中除了根结点每个结点都有一条边进入）

1
总度数 = 1×n1 + 2×n2 + ... + m×nm = 分支数 = n - 1
2
总结点 n = n0 + n1 + n2 + ... + nm
3
→ n0 = 1 + Σ(k-1)×nk

1
ASL成功 = (各层结点数 × 该层层数) / 元素总数
2

3
树高：⌊log₂n⌋ + 1
4
第1层：1个结点，比较1次
5
第2层：2个结点，比较2次
6
第3层：4个结点，比较3次
7
...

1
ASL失败 = Σ（外部结点比较次数）/（n+1）
2

3
外部结点 = 叶子结点（查找失败的位置）= n + 1 个

1
ASL = (m+1)/2 + (n/m+1)/2

1
分：将问题划分为若干子问题
2
治：递归求解各子问题
3
合：将子问题的解合并为原问题的解

1
if → 1个判定结点
2
while/for → 1个判定结点
3
switch(n个case) → n-1 个判定结点
4
A && B 复合条件 → 2个判定结点
5
A || B 复合条件 → 2个判定结点

1
if (A > 0)       // 1个判定
2
    while (B < 10) // 1个判定
3
        if (C && D) // 2个判定
4

5
P = 4 → V(G) = 5

1
DFD 管功能（数据怎么流）
2
E-R  管数据（实体什么关系）
3
STD 管行为（状态怎么变）

1
- 事务开始（BEGIN TRANSACTION）
2
- 事务结束（COMMIT / ROLLBACK）
3
- 对数据库的每次操作（INSERT/DELETE/UPDATE）

1
WAL（Write-Ahead Logging，先写日志原则）：
2
任何对数据库的修改，必须先写日志记录，再修改数据库
3

4
Checkpoint（检查点）：
5
定期将缓冲区内容写入数据文件，缩短恢复时需要扫描的日志范围

1
日志先写后操作（WAL）
2
事务故障只撤销（UNDO）
3
系统故障撤加重（UNDO+REDO）
4
介质故障备份+日志