知识库
先学知识点，再做题检验。当前：数据结构与算法
01. 计算机系统知识 (13个)
02. 程序语言基础 (3个)
03. 操作系统 (8个)
04. 软件工程 (8个)
05. 数据结构与算法 (23个)
06. 数据库系统 (11个)
07. 计算机网络 (12个)
08. 面向对象技术 (10个)
09. 信息安全 (4个)
10. 知识产权与标准化 (4个)
11. 多媒体基础 (2个)
12. 项目管理 (4个)
线性结构
数组与矩阵存储
重点 难度 2/3
通俗理解
数组就像一排连续编号的储物柜（编号从0开始），想要拿第i个柜子的东西，直接走过去就行，一步到位（O(1)读取）。矩阵就是二维的储物柜阵列——比如教室座位表，第2排第3列直接定位。计算机里矩阵按"行优先"（一行存完再存下一行）或"列优先"存成一维数组。
核心公式/考点
• 一维数组：Loc(ai) = Loc(a0) + i × sizeof(元素)
• 二维数组（行优先）：Loc(a[i][j]) = Loc(a[0][0]) + [i×n + j] × sizeof(元素) （n为列数）
• 二维数组（列优先）：Loc(a[i][j]) = Loc(a[0][0]) + [j×m + i] × sizeof(元素) （m为行数）
• 对称矩阵压缩存储（下三角）：k = i(i-1)/2 + j - 1（i≥j）
• 三角矩阵、带状矩阵、稀疏矩阵（三元组表、十字链表）
表格对比
| 存储方式 | 访问速度 | 插入/删除 | 适用场景 |
| 数组（顺序存储） | O(1) 随机访问 | O(n) | 频繁读取、大小固定 |
|---|---|---|---|
| 链表（链式存储） | O(n) 顺序访问 | O(1) | 频繁插入删除 |
真题演练
例题：设二维数组A[1..5][1..6]按行优先存储，每个元素占2字节，首地址SA=100。求A[3][4]的地址。
解：行优先公式 Loc = SA + [(i-1)×n + (j-1)]×sizeof
Loc = 100 + [(3-1)×6 + (4-1)]×2
= 100 + [12 + 3]×2 = 100 + 30 = 130
注意事项
• 注意数组下标是从0还是从1开始，公式差一个偏移量
• 矩阵压缩存储只存非零元或三角部分，题目常考"给定下标k求原下标i,j"
• 稀疏矩阵的三元组表格式：(行, 列, 值)，注意排序规则（先行后列）
栈(LIFO)与队列(FIFO)
重点 难度 2/3
通俗理解
栈就像一摞盘子——你只能从最上面拿（后放上去的先拿走），这叫"后进先出LIFO"。队列就像食堂打饭排队——先来的人先打到饭先走，这叫"先进先出FIFO"。栈只有一端操作（栈顶），队列两端操作（队头出、队尾入）。
核心公式/考点
• 栈：push（入栈）、pop（出栈）、top/peek（取栈顶）、isEmpty
• 队列：enqueue（入队）、dequeue（出队）、front（取队头）
• 栈的经典应用：括号匹配、表达式求值（中缀→后缀）、函数调用栈
• 队列的经典应用：BFS广度优先搜索、缓冲区、打印任务队列
• 循环队列：front=(front+1)%MAXSIZE, rear=(rear+1)%MAXSIZE
• 循环队列判满：(rear+1)%MAXSIZE == front（牺牲一个空间）
表格对比
| 操作 | 栈（LIFO） | 队列（FIFO） |
| 添加 | push → 栈顶 | enqueue → 队尾 |
|---|---|---|
| 删除 | pop ← 栈顶 | dequeue ← 队头 |
| 访问限制 | 只开放一端 | 两端各自开放 |
| 类比 | 浏览器的"后退"按钮 | 打印机任务队列 |
真题演练
例题：一个栈的入栈顺序为ABCDE，以下哪个不可能是出栈顺序？
A) EDCBA B) DCEBA C) DECAB D) ABCDE
解：栈是LIFO，关键看"压入后必须从栈顶弹出才能拿下面的"。
A: 全部push再pop → 可行
B: push A,B,C,D → pop D → push E → pop C → pop B → pop A → 可行
C: push A,B,C,D → pop D → push E → pop E → ... 此时栈中[A,B,C]，想pop A必须先pop C和B → 不可行 ✅ 答案C
注意事项
• 栈和队列通常用数组或链表实现，注意判空判满条件
• 递归的本质就是栈——递归过深会导致"栈溢出"
• 循环队列要区分空和满：空时front==rear，满时(rear+1)%n==front
• 双端队列(Deque)介于两者之间，两端都可入可出
树
链表
重点 难度 2/3
通俗理解
链表就像寻宝游戏——每个宝箱里除了有宝藏，还写着一句话"下一个宝箱在XXX"。你只能从第一个宝箱开始，顺着线索一个一个找下去。不像数组能直接"走到第3个柜子"，链表要"第1个→第2个→第3个"这样走。
核心公式/考点
• 单链表：每个结点有 data + next(指向下一个结点)
• 双链表：每个结点有 prev(指向前一个) + data + next(指向后一个)
• 循环链表：最后一个结点的next指向头结点
• 插入操作：修改指针指向（O(1)）
在p后插入新结点s：s.next = p.next; p.next = s
• 删除操作：修改指针绕过被删结点（O(1)，但查找前驱是O(n)）
删除p的后继q：p.next = q.next
• 头结点（dummy node）：简化边界处理
表格对比
| 操作 | 数组 | 单链表 |
| 随机访问 | O(1) | O(n) |
|---|---|---|
| 表头插入 | O(n) | O(1) |
| 表尾插入 | O(1)摊还 | O(n)（无尾指针） |
| 空间 | 连续空间（可能碎片） | 离散空间（多存指针） |
| 内存占用 | 仅数据 | 数据 + 指针开销 |
真题演练
例题：给定单链表L（带头结点），写出删除所有值为x的结点的算法思路。
解：
1.定义指针p=head, prev=NULL
2.遍历链表：
若p.data == x：prev.next = p.next（跳过p），free(p)
否则：prev = p（前驱后移）
p = p.next
3.注意：删除第一个结点时要用头结点辅助；释放内存
核心思想：用prev记录前驱，保证O(n)一次遍历完成。
注意事项
• 链表常考"快慢指针"技巧——找中点、判断环（Floyd判圈）
• 边界处理：空链表、只有一个结点、删除头/尾结点
• 注意区分"带头结点"和"不带头结点"——头结点不存数据，简化统一操作
• 双链表插入/删除需同时修改prev和next两个指针
二叉树性质
重点 难度 2/3
通俗理解
二叉树就像家族谱系图——每个人最多有两个孩子（左孩子、右孩子）。计算机用这种结构来组织有层级关系的数据。比如文件目录树：一个文件夹里可以有子文件夹和文件，每个文件夹最多分"左右"两个子文件夹。
核心公式/考点
性质1：第i层最多有 2^(i-1) 个结点（i≥1）
性质2：深度为k的二叉树最多有 2^k - 1 个结点（k≥1）
性质3：n0 = n2 + 1（叶结点数 = 度为2的结点数 + 1）
性质4：n个结点的完全二叉树深度 = ⌊log₂n⌋ + 1
性质5：完全二叉树的顺序存储中，结点i的左孩子为2i，右孩子为2i+1，父节点为⌊i/2⌋
表格对比
| 类型 | 定义 | 结点数范围 |
| 满二叉树 | 每层都满，共2^k-1个结点 | 精确2^k-1 |
|---|---|---|
| 完全二叉树 | 最后一层左满右缺，编号连续 | 2^(k-1) ≤ n ≤ 2^k-1 |
| 平衡二叉树 | 左右子树高度差≤1 | 视具体结构 |
| 二叉排序树BST | 左<根<右 | 视具体结构 |
真题演练
例题：一棵完全二叉树有1001个结点，求叶子结点个数。
解：完全二叉树最后一个非叶子结点编号为⌊n/2⌋ = ⌊1001/2⌋ = 500
所以叶子结点编号为 501 ~ 1001，共 1001-500 = 501个
验证 n0 = n2 + 1，设n2=x，则 n1=0或1
1001 = n0 + n1 + n2 = (x+1) + n1 + x = 2x + 1 + n1
→ 若n1=0，2x+1=1001→x=500，n0=501 ✅
→ 若n1=1，2x+2=1001→x=499.5不整 ❌
故叶子=501个。
注意事项
• 性质3 n0=n2+1是最重要公式，牢记推导（总边数 = n-1 = n1+2n2）
• 完全二叉树用数组存储时，编号从1开始，左子=2i，右子=2i+1
• 区分"深度"和"高度"：深度从根向下，高度从叶向上
• 哈夫曼树无度为1的结点（严格二叉树）
二叉树遍历
重点 难度 2/3
通俗理解
遍历就是按一定规则"走一遍"二叉树的所有结点，像逛博物馆一样。先序遍历：先看馆长大厅（根）→再看左边展厅（左子树）→再看右边展厅（右子树）。中序遍历：先逛左边→再看中间→再逛右边。后序遍历：先逛完所有分馆→最后回到总馆。
核心公式/考点
• 先序遍历（Preorder/前序）：根 → 左 → 右
• 中序遍历（Inorder）：左 → 根 → 右（BST下得到递增序列）
• 后序遍历（Postorder）：左 → 右 → 根
• 层序遍历（Level Order）：逐层从左到右（队列实现）
• 已知两种遍历序列→唯一确定二叉树（必须有中序+任一前序/后序）
表格对比
| 遍历方式 | 访问顺序 | 递归实现 | 典型应用 |
| 先序 | 根→左→右 | pre(root){visit;pre(left);pre(right)} | 打印树结构、复制树 |
|---|---|---|---|
| 中序 | 左→根→右 | in(root){in(left);visit;in(right)} | BST排序输出 |
| 后序 | 左→右→根 | post(root){post(left);post(right);visit} | 释放树、表达式求值 |
| 层序 | 逐层 | 队列实现 | 最短路径、BFS |
真题演练
例题：已知二叉树先序为ABDECFG，中序为DBEAFCG，求后序。
解：1) 先序第一个A是根 → 中序分左右：左子树DBE，右子树FCG
2) 左子树：先序BDE，中序DBE → B是左子根，D是B的左子，E是B的右子
3) 右子树：先序CFG，中序FCG → C是右子根，F是C的左子，G是C的右子
4) 后序 = 左→右→根 = (D→E→B) + (F→G→C) + A = DEB FGCA
注意事项
• 先序+中序 或 后序+中序才能唯一确定二叉树，先序+后序不行
• 递归实现简单但深度大时栈溢出，迭代要手动维护栈
• 线索二叉树（Threaded Tree）把空指针改成前驱/后继线索
• 层序遍历用队列，其他三种用栈（递归本质是系统栈）
哈夫曼树
重点 难度 2/3
通俗理解
哈夫曼树是最优二叉树——就像整理快递车，把最常送的快递放最外面（离车门最近），最不常送的放最里面。这样每次拿快递走的路程最短。哈夫曼编码就是给字符重新分配二进制码——出现越频繁的字，编码越短（比如"的"用01，"饕"用0101101）。
核心公式/考点
• WPL(带权路径长度) = Σ 叶结点权值 × 路径长度
• 构造步骤：
1.将n个权值作为n棵单结点树（最小堆）
2.取权值最小的两棵合并，新权值为和
3.重复直到剩一棵树
• 哈夫曼编码前缀码性质：任一编码不是另一编码的前缀
• 哈夫曼树无度为1的结点：n0 = n2 + 1，总结点 = 2n0 - 1
表格对比
| 编码方式 | 是否前缀码 | 编码效率 | 应用 |
| 等长编码 | 是 | 固定长度，冗余多 | ASCII |
|---|---|---|---|
| 哈夫曼编码 | 是（最优前缀码） | 最短平均长度 | ZIP压缩、JPEG |
| 非前缀码 | 否（歧义） | 不可解码 | ❌ 不实用 |
真题演练
例题：字符集{a,b,c,d,e}频率分别为{5,9,12,13,16}，构建哈夫曼树并求WPL。
解：
1) 最小两个5+9=14 → 池：[12,13,14,16]
2) 最小两个12+13=25 → 池：[14,16,25]
3) 最小两个14+16=30 → 池：[25,30]
4) 合并25+30=55 → 根
树结构：
55
/ \
25 30
/ \ / \
12 13 14 16
/ \
5 9
WPL = (12+13)×2 + 5×3 + 9×3 + 16×2 = 50 + 15 + 27 + 32 = 124
= 12*2 + 13*2 + 16*2 + 5*3 + 9*3 = 124 ✅
注意事项
• WPL计算注意路径长度是从根到叶的边数
• 哈夫曼编码"左0右1"是习惯约定，反过来也行
• 构造时每次取最小的两个，相同权值时任选
• 哈夫曼树不唯一（相同权值顺序不同），但WPL唯一最小
二叉排序树BST
重点 难度 2/3
通俗理解
二叉排序树就像一本自动整理的词典：左边全是比当前单词"小"的词，右边全是"大"的词。查一个词时，先跟中间词比，小就往左翻，大就往右翻——每次排除一半，效率超高。插入新词也按这个规则找位置挂上去。
核心公式/考点
• BST性质：左子树所有结点 < 根 < 右子树所有结点
• 中序遍历BST = 递增有序序列
• 查找：平均O(log₂n)，最坏O(n)（退化为链表）
• 插入：先查找，找到空位插入（新结点总在叶子处）
• 删除三种情况：
1.叶子结点：直接删
2.一个孩子：子承父位
3.两个孩子：找前驱（左子树最大）或后继（右子树最小）替换
表格对比
| 树类型 | 查找平均 | 查找最坏 | 插入 | 删除 |
| 普通BST | O(log n) | O(n) | O(log n) | O(log n) |
|---|---|---|---|---|
| 平衡BST | O(log n) | O(log n) | O(log n) | O(log n) |
| 有序数组 | O(log n)二分 | O(log n) | O(n) | O(n) |
真题演练
例题：将序列{50,30,80,20,40,35,90}依次插入空BST，画出树。
解：
1) 50为根
2) 30<50 → 50左子
3) 80>50 → 50右子
4) 20<50→左→20<30→30左子
5) 40<50→左→40>30→30右子
6) 35<50→左→35>30→右→35<40→40左子
7) 90>50→右→90>80→80右子
50
/ \
30 80
/ \ \
20 40 90
/
35
中序遍历：20,30,35,40,50,80,90 ✅ 递增
注意事项
• BST查找性能取决于树的平衡程度——最坏是有序输入（变链表）
• 删除有两个孩子的结点时，找前驱/后继替换，然后删前驱/后继
• BST的插入新结点一定是叶子，不会改变已有结构
• BST允许相同值吗？通常左≤根<右或左<根≤右，要约定好
平衡二叉树AVL
重点 难度 2/3
通俗理解
AVL树是"强迫症版"的BST——它要求每个结点的左右子树高度差不超过1，但凡超过就立刻"扭一扭"调整。就像堆放箱子，要求两边高度差不超过1层，歪了就搬动一些箱子重新平衡。
核心公式/考点
• 平衡因子 = 左子树高度 - 右子树高度（绝对值≤1）
• 四种失衡情况及调整：
LL（左左）：右旋一次 → 新根为失衡结点的左子
RR（右右）：左旋一次 → 新根为失衡结点的右子
LR（左右）：左子先左旋，再右旋 → 新根为左子的右子
RL（右左）：右子先右旋，再左旋 → 新根为右子的左子
• 最少结点递推：N₀=0, N₁=1, Nₕ=Nₕ₋₁+Nₕ₋₂+1（类似斐波那契）
表格对比
| 旋转类型 | 失衡形态 | 第一步 | 第二步 | 新根 |
| LL | 左子左子树高 | 无 | 右旋 | 左子 |
|---|---|---|---|---|
| RR | 右子右子树高 | 无 | 左旋 | 右子 |
| LR | 左子右子树高 | 左子左旋 | 右旋 | 左子的右子 |
| RL | 右子左子树高 | 右子右旋 | 左旋 | 右子的左子 |
真题演练
例题：依次插入3,2,1,4,5,6,7到空AVL树，画出每次调整后的树。
解：
1) 插入3 → 根3
2) 插入2 → 3左子2，平衡
3) 插入1 → 3失衡（左高2-右高0=2），LL型 → 右旋
2
/ \
1 3
4) 插入4 → 2右子4，平衡
5) 插入5 → 3的右子5，3失衡RR型 → 左旋
2 2
/ \ / \
1 3 → 1 4
\ / \
5 3 5
再检查2平衡因子=左1-右2=-1，平衡
6) 插入6 → 5失衡RR型→4左旋...（继续练习）
注意事项
• AVL插入后从插入点向上回溯更新平衡因子，找到第一个失衡点调整
• 调整后子树高度恢复，上层祖先不用再调
• 删除也可能导致失衡，调节方式同上
• LR和RL是双旋，先旋转"孩子"再旋转"自己"
图
图的存储
重点 难度 2/3
通俗理解
图就像一张社交网络——人是结点，朋友关系是边。存图有两种方式：邻接矩阵就是一张"关系表格"——行是人A，列是人B，格子打✓表示认识。邻接表就是每个人的"朋友名单"——张三的朋友：李四、王五、赵六...
核心公式/考点
• 邻接矩阵：n×n矩阵，A[i][j]=1表示i到j有边
无向图：对称矩阵，度为行/列和
有向图：出度=行和，入度=列和
空间复杂度：O(n²)
• 邻接表：每个顶点一个链表，存所有邻接点
空间复杂度：O(n+e)（n顶点，e边）
无向图每条边存两次
• 十字链表（有向图）和邻接多重表（无向图）：更高效的存储
表格对比
| 存储方式 | 空间 | 判邻接 | 找所有邻接点 | 适用 |
| 邻接矩阵 | O(n²) | O(1) | O(n) | 稠密图 |
|---|---|---|---|---|
| 邻接表 | O(n+e) | O(度) | O(度) | 稀疏图 |
| 十字链表 | O(n+e) | O(度) | O(度) | 有向图 |
| 邻接多重表 | O(n+e) | O(度) | O(度) | 无向图 |
真题演练
例题：有向图G有4个顶点，边集{1→2,1→3,2→4,3→4,4→1}，画出邻接矩阵和邻接表。
解：
邻接矩阵：
1 2 3 4
1: 0 1 1 0
2: 0 0 0 1
3: 0 0 0 1
4: 1 0 0 0
出度：1→2, 2→1, 3→1, 4→1
邻接表：
1: [2, 3]
2: [4]
3: [4]
4: [1]
注意事项
• 邻接矩阵找所有邻接点要遍历整行O(n)，邻接表只要O(度)
• 有向图邻接表求入度麻烦，可以建"逆邻接表"（入边表）
• 网络流/带权图在矩阵中存权值，无边用∞或0
• 稠密图用矩阵，稀疏图用邻接表——面试常问选型理由
图的遍历
重点 难度 2/3
通俗理解
图的遍历就是"走遍所有城市"——DFS（深度优先）像探险家：一条路走到黑，走不通了再倒回岔路口换条路。BFS（广度优先）像病毒传播：从起点开始，一圈一圈向外扩散，先感染所有邻居，再感染邻居的邻居。
核心公式/考点
• DFS（深度优先搜索）：栈实现（递归/栈）
伪代码：DFS(v){ visited[v]=true; for(邻接点w) if(!visited[w]) DFS(w); }
• BFS（广度优先搜索）：队列实现
伪代码：BFS(v){ queue.offer(v); visited[v]=true; while(!queue.isEmpty()){ v=queue.poll(); for(邻接点w) if(!visited[w]){visited[w]=true; queue.offer(w);} } }
• 时间复杂度：邻接表O(n+e)，邻接矩阵O(n²)
• 连通分量：DFS/BFS一次能访问到的所有顶点构成一个连通分量
表格对比
| 特性 | DFS | BFS |
| 数据结构 | 栈（递归/栈） | 队列 |
|---|---|---|
| 策略 | 先深入再回溯 | 逐层扩散 |
| 路径性质 | 不一定最短 | 一定最短（无权图） |
| 空间最坏 | O(n)（链表情况） | O(n)（满叉树情况） |
| 应用 | 拓扑排序、连通分量 | 最短路径、社交网络"六度" |
真题演练
例题：以下各图，从顶点1出发，分别写出DFS和BFS的遍历序列。
图：1-2, 1-3, 2-4, 2-5, 3-6, 3-7（无向图，形如二叉树）
解：
DFS（递归，按编号从小到大选）：1→2→4→5→3→6→7
从1出发，选最小邻接2；从2选最小邻接4；4无未访邻接→回退2→选5；回退1→选3→6→7
BFS（队列）：1→2→3→4→5→6→7
第1层：1；第2层：2,3；第3层：4,5,6,7
注意事项
• 图可能有环和孤立点——visited数组防止死循环
• DFS用递归要小心栈溢出（超深图），可用栈迭代
• BFS的队列实现注意不要把顶点重复入队（入队时标记visited）
• 非连通图需要对每个未访问顶点调用一次DFS/BFS
最小生成树
重点 难度 2/3
通俗理解
最小生成树就像给几个村庄修路，要求所有村都通且总路长度最短。你不需要每个村之间都直接相连（太浪费），只要选n-1条路把所有n个村连起来，且总造价最低。Prim算法是"从一个村开始，每次拉最近的村入伙"；Kruskal是"把所有路按长度排序，从最短的开始，不形成环就加进来"。
核心公式/考点
• Prim算法：从起点出发，每次选已选集合到未选集合的最小边
时间复杂度：O(n²)（邻接矩阵），O((n+e)log n)（堆优化）
适合稠密图
• Kruskal算法：按权值从小到大选边，不构成环就加入
时间复杂度：O(e log e)（排序）
适合稀疏图
• 最小生成树性质（MST性质/MST-cut性质）：最小权值的边一定在某棵MST中
表格对比
| 算法 | 策略 | 时间复杂度 | 数据结构 | 适用 |
| Prim | 加点 | O(n²) / O((n+e)log n) | 数组/堆+邻接表 | 稠密图 |
|---|---|---|---|---|
| Kruskal | 加边 | O(e log e) | 并查集 | 稀疏图 |
真题演练
例题：边集{(1,2,6),(1,3,1),(1,4,5),(2,3,5),(2,5,3),(3,4,5),(3,5,6),(3,6,4),(4,6,2),(5,6,6)}，求MST总权值。
解：Kruskal：
1) 最小边(1,3,1)→选
2) (4,6,2)→选
3) (2,5,3)→选
4) (3,6,4)→选（1-3-6-4连通）
5) (1,4,5)→会形成环(1-3-6-4-1)，跳过
(2,3,5)→选（2-5连通，3-1连通，合并两组件）
总权 = 1+2+3+4+5 = 15
6条边（n=7顶点需6条？检查顶点数：1-6共6个顶点→需5条边→已完成）
总权值=1+2+3+4+5=15 ✅
注意事项
• Prim和Kruskal的结果权值相同但边集可能不同（有平行最小边时）
• Kruskal判环用并查集——两个端点在同一集合则跳过（会成环）
• 最小生成树不是唯一的（有等权边时），但总权值唯一最小
• 带负权边的图，最小生成树算法仍然适用（Kruskal/Prim不受影响）
最短路径
重点 难度 2/3
通俗理解
最短路径就是导航地图的"算路"功能——从家到公司怎么走最近？Dijkstra算法像"贪心扩散"：从起点开始，先标记最近的路口，逐步扩大已知最短区域。Floyd算法更暴力：一口气算完所有路口之间的最短路线，就像地图App里"所有地点之间的距离表"。
核心公式/考点
• Dijkstra（单源最短路径，边权非负）：
dist[v] = min(dist[v], dist[u] + w(u,v))
时间复杂度：O(n²) 或 O((n+e)log n)（堆优化）
• Floyd（所有点对最短路径，可负权）：
D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])
时间复杂度：O(n³)
• Bellman-Ford（单源，可负权，可判负环）：O(n×e)
表格对比
| 算法 | 功能 | 边权 | 时间复杂度 | 空间 |
| Dijkstra | 单源最短路 | 非负 | O(n²)/O((n+e)log n) | O(n) |
|---|---|---|---|---|
| Floyd | 全源最短路 | 任意（无负环） | O(n³) | O(n²) |
| Bellman-Ford | 单源最短路 | 任意 | O(n×e) | O(n) |
真题演练
例题：用Dijkstra求顶点1到其他顶点的最短路径，边集：1-2(2),1-3(5),2-3(2),2-4(6),3-4(1)
解：
初始化：dist=[0,2,5,∞], visited=[✓,×,×,×]
第1轮：选最小未访2(dist=2)，更新：
dist[3]=min(5, 2+2=4)→4
dist[4]=min(∞, 2+6=8)→8
第2轮：选最小未访3(dist=4)，更新：
dist[4]=min(8, 4+1=5)→5
第3轮：选4(dist=5)
最终最短路径：1→2=2, 1→2→3=4, 1→2→3→4=5
注意事项
• Dijkstra不能处理负权边——负权会破坏"已选中即最优"的性质
• Floyd的k循环必须在最外层（因为k是中转点，逐次引入）
• Bellman-Ford做n-1轮松弛后，第n轮还能松弛则说明有负环
• 记录前驱结点可以还原完整路径
查找
查找算法对比
重点 难度 2/3
通俗理解
查找就是在数据堆里找目标。不同的查找方式就像不同的找东西策略：二分查找像翻字典——每次翻到中间，比目标大就往后翻，小就往前翻。哈希查找像按编号找快递柜——目标直接映射到柜号，一步到位。
核心公式/考点
• 顺序查找（线性查找）：O(n)，ASL成功=(n+1)/2
• 二分查找（折半查找）：O(log n)，前提有序
ASL≈log₂(n+1)-1，树高⌊log₂n⌋+1
• 分块查找：块间有序块内无序，先二分找块再顺序找元素
ASL≈log₂(n/s+1) + s/2（s为块大小）
• 哈希查找（散列查找）：O(1)平均
哈希函数：除留余数法 H(key)=key%p
冲突处理：开放定址（线性探测、平方探测）、链地址法
装填因子α = 表中记录数/散列表长度
表格对比
| 算法 | 平均时间 | 最坏时间 | 空间 | 前提条件 |
| 顺序查找 | O(n) | O(n) | O(1) | 无 |
|---|---|---|---|---|
| 二分查找 | O(log n) | O(log n) | O(1) | 有序 |
| 分块查找 | O(log n+s) | O(n) | O(n) | 块间有序 |
| 哈希查找 | O(1) | O(n) | O(n) | 设计好哈希函数 |
真题演练
例题：有序序列1~15，二分查找元素7需要比较几次？
解：二分查找判定树：
第1层（mid=8）：8>7，找左半[1~7]
第2层（mid=4）：4<7，找右半[5~7]
第3层（mid=6）：6<7，找右半[7~7]
第4层（mid=7）：7==7 ✅
需要比较4次。ASL=(1×1+2×2+3×4+4×8)/15≈3.27
注意事项
• 二分查找要求顺序存储（数组），链表不行（无法随机访问）
• 哈希表"堆积"现象：线性探测法会形成连续占用区，降低效率
• 哈希表的删除不能用真的删除（会影响探测链），用"删除标记"
• 分块查找的块大小选择影响性能：s=√n时ASL最小≈√n
排序
插入排序类
重点 难度 2/3
通俗理解
插入排序就像打扑克牌摸牌——每摸到一张新牌，就把它插入到手牌中合适的位置，保持手牌一直有序。一开始左手是空的，摸第一张直接放左手，后面每张都跟左手牌从右到左比，找到位置插进去。
核心公式/考点
• 直接插入排序：
将待排序元素插入到已有序的子序列中
最好O(n)（已有序），最坏O(n²)（逆序），平均O(n²)
稳定排序
• 希尔排序（Shell Sort）：
缩小增量排序，先远距离交换再逐步缩小间距
增量序列常用：gap=n/2, gap/=2
时间复杂度：O(n^1.3)~O(n²)（取决于增量序列）
不稳定排序
表格对比
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 |
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | ✅稳定 |
|---|---|---|---|---|---|
| 希尔排序 | O(n) | O(n²) | O(n^1.3) | O(1) | ❌不稳定 |
真题演练
例题：用直接插入排序对序列[5,2,4,6,1,3]进行排序，写出每趟结果。
解：
| 初始：[5 | 2,4,6,1,3]（ | 前为已排序部分） |
第1趟：[2,5| 4,6,1,3] ← 2插入[5]前
第2趟：[2,4,5| 6,1,3] ← 4插入[2,5]中
第3趟：[2,4,5,6| 1,3] ← 6最大，位置不变
第4趟：[1,2,4,5,6| 3] ← 1插入最前
第5趟：[1,2,3,4,5,6] ← 3插入[1,2,4,5,6]中
注意事项
• 直接插入排序在基本有序时效率极高O(n)
• 希尔排序的增量序列选择影响性能，最后一步必须是1
• 希尔排序是不稳定的——相同元素可能因分组被交换位置
• 折半插入排序减少了比较次数（用二分找位置），但移动次数不变
交换排序类
重点 难度 2/3
通俗理解
冒泡排序像水里的气泡——大的元素像大气泡一样慢慢"浮"到水面（尾部）。每次相邻两个比，大的往后移，一趟下来最大的就到了最后。快速排序像"分治擂台"——选一个擂主（基准），比他小的站左边，大的站右边，然后左右各自继续打擂台。
核心公式/考点
• 冒泡排序：
相邻比较，大者后移，每趟确定一个最大元素
最好O(n)（优化版加flag检测），最坏O(n²)，平均O(n²)
稳定排序
• 快速排序（Quick Sort）：
选基准pivot，划分成左小右大，递归排序
最好O(n log n)，最坏O(n²)（有序/逆序），平均O(n log n)
不稳定排序
空间O(log n)（递归栈）
表格对比
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | ✅稳定 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | ❌不稳定 |
真题演练
例题：对序列[3,7,8,5,2,1,9,5,4]进行快速排序（选第一个为基准），写出第一趟划分结果。
解：pivot=3
i→3 7 8 5 2 1 9 5 4←j
j从右找<3：找到1→交换i(j)：
1 7 8 5 2 3 9 5 4
i从左找>3：找到7→交换：
1 3 8 5 2 7 9 5 4
j继续找<3：找到2→交换：
1 2 8 5 3 7 9 5 4
i找>3：找到8→交换：
1 2 3 5 8 7 9 5 4
i=3,j=3→相遇，第一趟结束
结果：基准3在位置3，左边[1,2]，右边[8,5,7,9,5,4]
注意事项
• 快速排序最坏O(n²)发生在每次选取的基准是最大/最小元素
• 优化：随机选取基准、三数取中（左中右取中位数）
• 快速排序不稳定，但它是"实际最快的排序算法"
• 冒泡排序可以提前结束（没有元素交换时），这是优化关键
选择排序类
重点 难度 2/3
通俗理解
简单选择排序就像"每次挑最小的"——你去果园摘水果，先在整个果园里找最小的摘下来（放到第一位），然后继续在剩下的里面找最小的...简单直接但效率不高。堆排序像"自动排序的山"——先把数据堆成一个"大根堆"（老大在顶上），每次把山顶的最大值拿走，然后用剩下的重新调整出新的山顶。
核心公式/考点
• 简单选择排序：
每趟选最小元素放到已排序末尾
O(n²)（无论什么情况），不稳定
• 堆排序：
建堆：从最后一个非叶子结点开始向下调整 O(n)
排序：堆顶与堆尾交换，堆长度-1，向下调整 O(n log n)
不稳定排序
表格对比
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | ❌不稳定 |
|---|---|---|---|---|---|
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌不稳定 |
真题演练
例题：序列[4,6,8,5,9]建大根堆（从最后一个非叶子结点开始调整）。
解：数组： [4, 6, 8, 5, 9]
索引：0 1 2 3 4
最后一个非叶子 = ⌊n/2⌋-1 = 2（元素8）
检查结点2(8)：左子=2*2+1=5(不存在)，右子=2*2+2=6(不存在)→不动
检查结点1(6)：左子=3(5)，右子=4(9)，9最大→6和9交换：
[4, 9, 8, 5, 6]
检查结点0(4)：左子=1(9)，右子=2(8)，9最大→4和9交换：
[9, 4, 8, 5, 6]
检查结点1(4)（被交换下来需继续调整）：左子3(5)，右子4(6)，6最大→4和6交换：
[9, 6, 8, 5, 4]
堆已建好 ✅ 大根堆：[9,6,8,5,4]
注意事项
• 堆排序在建堆时通常用数组，下标从0或1开始，孩子公式不同
下标0开始：左子=2i+1，右子=2i+2，父=(i-1)/2
下标1开始：左子=2i，右子=2i+1，父=i/2
• 堆排序不稳定——相同元素的相对顺序可能改变
• 建堆O(n)而非O(n log n)的理由：大部分结点深度小，调整代价小
归并与基数排序
重点 难度 2/3
通俗理解
归并排序像"合并有序名单"——把一摞无序的试卷先分成单人份（每个就是有序的），然后两人一组合并成有序的小组，再两组一组合并成有序的班级...最终全班有序。基数排序像"按多关键字分级整理"——比如整理扑克牌，先按花色分4堆，再按点数分13堆，或者反过来。
核心公式/考点
• 归并排序（Merge Sort）：
分治：分到单个元素，再两两合并
时间复杂度：O(n log n)（每层O(n)，共log₂n层）
空间复杂度：O(n)（需要临时数组）
稳定排序
• 基数排序（Radix Sort）：
LSD（最低位优先）：按个位→十位→百位分配收集
MSD（最高位优先）
时间复杂度：O(d×(n+r))（d位数，r基数）
空间复杂度：O(r+n)
稳定排序
表格对比
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅稳定 |
|---|---|---|---|---|---|
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r+n) | ✅稳定 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | ❌不稳定 |
真题演练
例题：对序列[38,27,43,3,9,82,10]进行归并排序，画出归并过程。
解：
初始：[38] [27] [43] [3] [9] [82] [10]
第1趟（两两合并）：
[27,38] [3,43] [9,82] [10]
第2趟：
[3,27,38,43] [9,10,82]
第3趟：
[3,9,10,27,38,43,82] ✅
注意事项
• 归并排序是稳定排序中效率最高的（O(n log n)）
• 归并排序的空间复杂度O(n)是主要缺点——原地归并实现复杂
• 基数排序适用于整数或字符串等有"多关键字"的数据
• 归并排序外部排序中的应用：内存放不下时用归并处理大文件
算法策略
分治法
重点 难度 2/3
通俗理解
分治法就是"分而治之"——遇到大问题，先拆成若干个小问题（分），小问题解决了再合并成整个答案（治）。就像整理一个大仓库：分成几个区域→每个区各自整理→最后汇总。二分查找、归并排序、快速排序都是分治法的经典应用。
核心公式/考点
• 分治三步法：
1.分解：将原问题分解为若干个规模更小的子问题
2.解决：递归求解各子问题
3.合并：将子问题的解合并为原问题的解
• 主定理（Master Theorem）：T(n) = aT(n/b) + f(n)
f(n)=O(n^log_b(a-ε)) → T(n)=Θ(n^log_b(a))
f(n)=Θ(n^log_b(a) log^k n) → T(n)=Θ(n^log_b(a) log^(k+1) n)
f(n)=Ω(n^log_b(a+ε)) → T(n)=Θ(f(n))
• 典型应用：二分查找、归并排序、快速排序、大整数乘法、最大子数组和
表格对比
| 算法 | 分解方式 | 子问题数 | 合并复杂度 | 总复杂度 |
| 二分查找 | 对半 | 1 | O(1) | O(log n) |
|---|---|---|---|---|
| 归并排序 | 对半 | 2 | O(n) | O(n log n) |
| 快速排序 | 按基准划分 | 2 | O(1) | O(n log n)平均 |
| 大整数乘法 | 分半 | 4→3(优化) | O(n) | O(n^1.585) |
真题演练
例题：用分治法求数组[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]的最大子数组和。
解：分治思路：
1) 分解：从中间mid=7（18）分成左[13..-23]和右[18..7]
2) 解决：递归求左最大子数组、右最大子数组
3) 合并：求跨越中点的最大子数组（左半从mid向左扩展 + 右半从mid+1向右扩展）
左半从右向左累加最大：18(索引7)+20(索引8)=38
右半从左向右累加最大：-7+12=5
跨中点最大 = 38+5 = 43（[18,20,-7,12]）
递归求左最大=20（[20]），右最大=18+20-7+12-5+...需要完整计算
最终最大子数组在左半边?跨中点?右半边? 取三者最大值。
注意事项
• 分治法的子问题必须相互独立（不重叠），否则用DP
• 合并步骤往往是最难的部分——要保证合并结果正确
• 主定理不适用于所有递推式（如T(n)=T(n-1)+O(n)→O(n²)）
• 分治的递归深度影响空间复杂度（递归栈深度）
动态规划DP
重点 难度 2/3
通俗理解
动态规划像"记住过往经验的路径规划"——你从家到公司有很多岔路口，与其每条路都从头走到尾，不如在每个路口记录"从起点到这里最短走了多远"，后面的人直接查记录就行，不用重复走。跟分治不同，分治是拆成不同的独立子问题，DP是拆成重叠的子问题，并且把子问题答案记下来（备忘录）。
核心公式/考点
• 动态规划三要素：
1.最优子结构：问题的最优解包含子问题的最优解
2.重叠子问题：子问题重复出现
3.无后效性：当前状态确定后，后面决策不受之前决策路径影响
• 解题步骤：
1.定义状态（dp数组含义）
2.状态转移方程
3.初始化和边界条件
4.计算顺序（自底向上/自顶向下记忆化）
• 经典DP问题：
斐波那契、爬楼梯（一维DP）
背包问题（0-1背包、完全背包）
最长公共子序列LCS、最长递增子序列LIS
矩阵连乘、最短编辑距离
表格对比
| 对比维度 | 分治法 | 动态规划 | 贪心算法 |
| 子问题关系 | 独立 | 重叠 | 无 |
|---|---|---|---|
| 决策方式 | 合并子解 | 状态转移 | 局部最优选择 |
| 最优保证 | ✅ | ✅ | ❌（需证明） |
| 典型 | 归并排序 | 背包问题 | 哈夫曼编码 |
真题演练
例题：0-1背包问题——容量C=10，物品：w=[2,3,4,5], v=[3,4,5,6]，求最大价值。
解：
dp[i][j]表示前i个物品，容量j的最大价值
初始：dp[0][*]=0, dp[*][0]=0
转移：dp[i][j]=max(dp[i-1][j]（不选）, dp[i-1][j-w[i]]+v[i]（选）)
计算dp表（简化）：
i=1,w=2,v=3: dp[1][2..10]=3
i=2,w=3,v=4: dp[2][3]=4, dp[2][5]=max(3,0+4)=4→选法不同...
dp[2][5]=3+4=7, dp[2][6]=3+4=7 ...
i=3,w=4,v=5: dp[3][4]=5, dp[3][6]=max(7,3+5)=8,
dp[3][7]=max(7,4+5)=9, dp[3][9]=max(7,7+5)=12
i=4,w=5,v=6: dp[4][5]=6, dp[4][7]=max(8,3+6)=9,
dp[4][9]=max(12,4+6)=12, dp[4][10]=max(12,7+6)=13
最大价值=13（选物品2,3,4：价值4+5+6=15?检查：w=3+4+5=12>10...
选物品1,3,4：w=2+4+5=11>10... 选物品1,2,4：2+3+5=10, v=3+4+6=13 ✅）
注意事项
• DP最难的是"状态定义"——定义对了，转移方程自然就出来了
• 滚动数组优化：如果dp[i]只用dp[i-1]，可以用一维数组（注意遍历顺序！）
• 背包问题中0-1背包一维优化要倒序遍历，完全背包要正序遍历
• 无后效性意味着状态只封装了"足够做决策的信息量"
贪心算法
重点 难度 2/3
通俗理解
贪心算法像"只顾眼前利益"的决策策略——每次选择当前看起来最优的方案，不回头调整。就像吃自助餐，每次只拿当前最想吃的（不考虑后面可能更好吃的）。贪心不一定得到全局最优，适合"贪婪有道理"的问题，比如找零钱（用大面额先找）通常最优。
核心公式/考点
• 贪心选择性质：局部最优选择能导致全局最优解
• 最优子结构：同DP
• 贪心 vs DP：贪心只做一次决策，不回头；DP记录所有可能
• 典型贪心问题：
活动选择（选最早结束的活动）
哈夫曼编码（最小频率优先合并）
最小生成树（Prim/Kruskal）
找零钱（某些币制下最优）
部分背包（按单位价值排序）
表格对比
| 问题 | 贪心策略 | 是否最优 | 如果不能贪心 |
| 活动选择 | 最早结束优先 | ✅ | DP |
|---|---|---|---|
| 部分背包 | 单位价值最高优先 | ✅ | — |
| 0-1背包 | 单位价值最高优先 | ❌ | DP |
| 找零(1,5,10,50) | 最大面额优先 | ✅ | — |
| 找零(1,3,4) | 最大面额优先 | ❌（如6=4+1+1×3个，最优=3+3×2个） | DP |
真题演练
例题：活动选择——活动列表{(1,4),(3,5),(0,6),(5,7),(3,8),(5,9),(6,10),(8,11),(8,12),(2,13),(12,14)}，括号内为(开始,结束)。选最多不冲突的活动。
解：贪心策略——选最早结束的活动
按结束时间排序：
(1,4)→结束4 → 选
(3,5)→开始3<4冲突→跳过
(0,6)→冲突→跳过
(5,7)→开始5≥4→选
(3,8)→冲突→跳过
(5,9)→冲突→跳过
(6,10)→冲突→跳过
(8,11)→开始8≥7→选
(8,12)→冲突→跳过
(2,13)→冲突→跳过
(12,14)→开始12≥11→选
最多选4个：{(1,4),(5,7),(8,11),(12,14)} ✅
注意事项
• 贪心算法必须证明贪心选择性质——不能想当然就用
• 很多问题"看起来可以贪心"但实际上是错的（如0-1背包）
• 找零问题在特殊币制下贪心不是最优（如1,3,4找6）
• 先排序再贪心是标准模式——排序的key很重要
高级数据结构
B树与B+树
重点 难度 2/3
通俗理解
B树是"多叉版"的平衡树——就像大型图书馆的索引系统：每层索引卡上有多个"分界词"，告诉你应该去哪个区域找书。B+树更极端，把所有数据都放在叶子层，上层索引只做"路标"。MySQL的InnoDB索引底层就是B+树。
核心公式/考点
• m阶B树性质：
根至少2个孩子，非根至少⌈m/2⌉个孩子
每个结点最多m个孩子、m-1个键值
所有叶子在同一层（绝对平衡）
• B+树特点：
所有数据存叶子，叶子间链表连接（范围查询高效）
内部结点只存索引（可以存更多层）
两个指针：根指针 + 叶子链头指针
表格对比
| 特性 | B树 | B+树 |
| 数据位置 | 所有结点 | 仅叶子结点 |
|---|---|---|
| 叶子链表 | 无 | 有（顺序访问） |
| 内部结点 | 存数据+索引 | 仅索引 |
| 范围查询 | 需要中序遍历 | 链表直接遍历 |
| 单点查找 | O(log n) | O(log n) |
| 典型应用 | 文件系统（HFS, NTFS） | 数据库索引（MySQL InnoDB） |
真题演练
例题：一棵3阶B树（即2-3树），插入键值序列{10,20,30,40,50,60}。
解：3阶→每个结点最多2个键值、3个孩子
1) 插入10,20 → [10,20]
2) 插入30 → [10,20,30]溢出→分裂：20上升为根，10左子，30右子
[20]
/ \
[10] [30]
3) 插入40 → [30,40]
4) 插入50 → [30,40,50]→分裂：40上升
[20,40]
/ | \
[10] [30] [50]
5) 插入60 → [50,60]
注意事项
• B树/B+树的高度比二叉树低得多（扇形出大），磁盘IO次数少
• 分裂操作：中间键上升，左右各一半
• 合并操作：删除时键数少于⌈m/2⌉-1则向兄弟借或合并
• B+树比B树更适合数据库的原因：范围查询 + 内部结点可存更多索引
KMP字符串匹配
重点 难度 2/3
通俗理解
KMP是"聪明版"的字符串查找——普通的暴力匹配（BF）发现不匹配就"退回重来"，KMP却说"不用退，我已经记住了你刚才匹配过的部分"。就像翻词典找词时，查到"abandon"发现下一个字母不是d而是x，你不会退回a重新查，而是直接用"x"和下一个位置比。
核心公式/考点
• next[j]：模式串P中前j-1个字符的最长相等前后缀长度
next[1] = 0（或-1，取决实现）
当P[j]≠P[i]时，k=next[k]回溯
• 时间复杂度：O(n+m) 线性（BF为O(n×m)）
• next数组手动计算："前缀"="后缀"的最长匹配
表格对比
| 算法 | 时间复杂度 | 空间 | 是否回溯主串指针 |
| BF暴力 | O(n×m) | O(1) | 是（回溯到i-j+2） |
|---|---|---|---|
| KMP | O(n+m) | O(m) | 否（i永不倒退） |
| BM | O(n/m)~O(n×m) | O(m) | 否（从右到左匹配） |
真题演练
例题：模式串P="abaabcac"，求next数组。
解：
P: a b a a b c a c
j: 1 2 3 4 5 6 7 8
next[1]=0
next[2]=1（前缀"a"无相等前后缀→默认1）
next[3]：前2个"ab"无相等前后缀→1
next[4]：前3个"aba"→前缀"a"=后缀"a"→最长=1→next=2
next[5]：前4个"abaa"→前缀"a"=后缀"a"→最长=1→next=2
next[6]：前5个"abaab"→前缀"ab"=后缀"ab"→最长=2→next=3
next[7]：前6个"abaabc"→无相等前后缀→1
next[8]：前7个"abaabca"→前缀"a"=后缀"a"→最长=1→next=2
next = [0,1,1,2,2,3,1,2]
注意事项
• next数组和nextval数组的区别：nextval是优化版，跳过必然失败的比较
• 注意不同教材next数组起始值不同（0还是1）——KMP的核心思想一致
• KMP不适合短模式串（O(m)预处理开销不划算）
• 手算next数组的关键：找"最长相等前后缀长度+1"
算法策略
回溯法与分支限界
重点 难度 2/3
通俗理解
回溯法像"走迷宫时带了一捆绳子"——走不通就原路返回，换另一个岔路口继续试。本质是"暴力搜索+剪枝"：把所有可能的路径走一遍，但走之前先判断这条路有没有希望，没希望就剪掉（剪枝）。分支限界类似，但它用"广搜+限界函数"，每层都评估哪个分支最有前途。
核心公式/考点
• 回溯法（Backtracking）：
DFS遍历解空间树（子集树、排列树）
时间复杂度：O(2^n)或O(n!) 指数级
约束函数（剪去不满足约束的分支）
限界函数（剪去不可能得到更优解的分支）
• 分支限界法（Branch & Bound）：
BFS/优先队列遍历解空间树
上界/下界函数评估
常用在求最优解问题
• 经典应用：
N皇后问题、图着色、子集和、0-1背包
旅行商TSP、迷宫问题
表格对比
| 对比维度 | 回溯法 | 分支限界法 |
| 搜索方式 | DFS | BFS/优先队列 |
|---|---|---|
| 目标 | 找所有解/任一解 | 找最优解 |
| 剪枝 | 约束函数+上界 | 限界函数（界） |
| 空间 | O(解空间深度) | O(解空间宽度) |
| 适用 | 约束满足问题 | 优化问题 |
真题演练
例题：N皇后问题——在4×4棋盘上放4个皇后，互不攻击（同行同列同对角线）。
解：回溯法过程
1) 第1行放第1列(1,1) → 递归第2行
2) 第2行从第1列试：(2,1)同列冲突→(2,2)同对角线冲突→(2,3)不行→(2,4)不行→回溯
发现第2行无法放，回溯第1行
3) 第1行放第2列(1,2) → 递归第2行
4) 第2行(2,4)可行 → 递归第3行
(3,1)可行 → 递归第4行
(4,3)不可行(与(2,4)同对角线)→回溯
第3行(3,1)需回溯→(3,?)...
最终一个解：(1,2),(2,4),(3,1),(4,3)
注意事项
• 回溯法最坏情况O(n!)，但剪枝能大幅减少实际搜索量
• 排列树（如TSP）和子集树（如0-1背包）的剪枝策略不同
• 分支限界的优先队列用估价函数f(n)=g(n)+h(n)（类似A*）
• 活结点表的组织方式：FIFO队列（BFS分支限界）或优先队列