主题
字号
CHAPTER 07 ≈ 31 MIN READ

手算专项与考前速查

这本练习册专攻「机械送分题」——KMP、还原树、BST/AVL、哈夫曼、Dijkstra、哈希 ASL、排序模拟、DP 表。这些题会就一定全对、不会就丢大块，靠的是手熟，不是灵感。

用法：每题先盖住「详解」自己动手做（一定要动笔，不要光看），做完再对答案。错了别只改答案，要回去看错在哪一步。每类至少独立做对 2 题，才算过关。

7.1 时间复杂度分析

7.1.1 题 1.1

写出下列代码段的时间复杂度：

(a) for(i=0;i<n;i++) for(j=0;j<n;j++) x++;
(b) for(i=0;i<n;i++) for(j=0;j<i;j++) x++;
(c) i=1; while(i<n) i=i*2;
(d) for(i=0;i<n;i++) for(j=1;j<n;j=j*2) x++;

详解：

7.1.2 题 1.2

T(n) = 100n² + 50000n + 9999，写出大 O，并说明 n 多大时 n² 项才「占主导」。

详解：O(n²)（只保留最高阶、去系数）。当 n 较大时 100n² 压倒 50000n——令 100n² > 50000n 得 n > 500，即 n 超过约 500 后二次项主导。这说明大 O 描述的是「足够大的 n」时的趋势，小 n 时系数和低阶项可能更重要，但分析复杂度只看趋势。

7.1.3 题 1.3

顺序查找长度为 n 的表，写出成功查找的最好、最坏、平均比较次数。

详解：最好 1（第一个就是）；最坏 n（最后一个或不存在）；平均（等概率）= (1+2+...+n)/n = (n+1)/2。三者数量级：最好 O(1)、最坏与平均都是 O(n)。

7.2 KMP 求 next 数组

约定：next[j] = 模式串 P[0..j−1] 这段的「最长相等前后缀」的长度，next[0] = −1（哨兵）。不同教材定义略有差异（有的从 1 计、有的用 nextval），但「最长相等前后缀」这个本质不变。下面用这个常见定义。

7.2.1 题 2.1

求 P = a b a b c 的 next 数组。

详解：逐位算 P[0..j−1] 的最长相等前后缀长度。

j P[j] 考察的前缀 P[0..j-1] 最长相等前后缀 next[j]
0 a （空） — −1（约定）
1 b "a" 单字符，无 0
2 a "ab" 无相等前后缀 0
3 b "aba" 前缀"a"=后缀"a"，长 1 1
4 c "abab" 前缀"ab"=后缀"ab"，长 2 2

next = [−1, 0, 0, 1, 2]。

7.2.2 题 2.2

求 P = a a a a b 的 next 数组。

详解：

j P[0..j-1] 最长相等前后缀 next[j]
0 （空） — −1
1 "a" 无 0
2 "aa" "a"，长 1 1
3 "aaa" "aa"，长 2 2
4 "aaaa" "aaa"，长 3 3

next = [−1, 0, 1, 2, 3]。（全相同字符时 next 递增，体现「失配能往前借很多」）

7.2.3 题 2.3

求 P = a b a a b c a c 的 next 数组。

详解：

j P[0..j-1] 最长相等前后缀 next[j]
0 （空） — −1
1 "a" 无 0
2 "ab" 无 0
3 "aba" "a"，长 1 1
4 "abaa" "a"，长 1 1
5 "abaab" "ab"，长 2 2
6 "abaabc" 无 0
7 "abaabca" "a"，长 1 1

next = [−1, 0, 0, 1, 1, 2, 0, 1]。

关键看 j=5："abaab" 开头 "ab" 和结尾 "ab" 相等，长 2。j=6 加了 c，"abaabc" 没有相等前后缀，跌回 0。

7.3 二叉树性质计算

7.3.1 题 3.1

一棵二叉树有 20 个度为 2 的节点、10 个度为 1 的节点，问叶子有多少个？总节点数多少？

详解：用性质 n₀ = n₂ + 1 → n₀ = 20 + 1 = 21 个叶子。总数 n = n₀ + n₁ + n₂ = 21 + 10 + 20 = 51。

7.3.2 题 3.2

一棵完全二叉树有 1000 个节点，问：① 高度多少？② 叶子节点多少个？③ 度为 1 的节点有几个？

详解： ① 高度 = ⌊log₂1000⌋ + 1 = ⌊9.96⌋ + 1 = 9 + 1 = 10。 ③ 完全二叉树里度为 1 的节点最多 1 个（且只能是有左孩子无右孩子）。1000 是偶数 → 最后一个节点（编号 1000）是左孩子，它的父亲（编号 500）只有左孩子无右孩子 → n₁ = 1。 ② 由 n₀ = n₂ + 1 且 n = n₀+n₁+n₂：1000 = n₀ + 1 + (n₀−1) = 2n₀ → n₀ = 500 个叶子。（n₂ = 499）

7.3.3 题 3.3

高度为 5 的二叉树，最多有多少个节点？最少呢？

详解：最多 = 满二叉树 = 2⁵ − 1 = 31。最少 = 每层只有 1 个节点（退化成链）= 5。

7.4 遍历与还原

7.4.1 题 4.1

已知二叉树：

        A
       / \
      B   C
     /   / \
    D   E   F
     \
      G

写出前序、中序、后序、层序遍历。

详解：

7.4.2 题 4.2

已知前序 = A B D E C F G，中序 = D B E A C F G，还原二叉树并写出后序。

详解：

还原的树：

        A
       / \
      B   C
     / \   \
    D   E   F
             \
              G

后序（左右根）：D E B G F C A → D E B G F C A。

7.4.3 题 4.3

已知后序 = D E B F C A，中序 = D B E A C F，还原并写出前序。

详解：

树：

      A
     / \
    B   C
   / \   \
  D   E   F

前序（根左右）：A B D E C F。

7.5 二叉搜索树 BST

7.5.1 题 5.1

依次插入 45, 24, 53, 12, 28, 90 建 BST，画出结果，并写出中序遍历验证有序。

详解：

插45: 45
插24: 24<45 → 左
插53: 53>45 → 右
插12: 12<45→左,12<24→左
插28: 28<45→左,28>24→右
插90: 90>45→右,90>53→右
        45
       /  \
      24    53
     / \      \
    12  28     90

中序（左根右）：12 24 28 45 53 90，升序 ✓。

7.5.2 题 5.2

在题 5.1 的树上，分别删除 12（叶子）、53（一个孩子）、45（两个孩子，根），各画出删除后的树。

详解：

删45后:   53
         /  \
        24    90
       / \
      12  28

也可用中序前驱（左子树最大 = 28）替换，得到另一棵合法 BST，根为 28。

7.6 AVL 平衡二叉树

7.6.1 题 6.1

依次插入 16, 3, 7, 11, 9, 26, 18, 14, 15，画出最终 AVL 树（标出每次旋转）。

详解（只列触发旋转的关键步）：

最终（一种标准答案）：

            11
          /    \
         7      16
        / \    /  \
       3   9  14   26
               \   /
               15 18

此题旋转多、易错，强烈建议自己从头独立画一遍。重点是每插一个都从插入点往上查 BF，第一个 ±2 处定旋转类型。

7.6.2 题 6.2

判断下列插入序列各触发什么旋转：(a) 1,2,3 (b) 3,2,1 (c) 1,3,2 (d) 3,1,2

详解：

7.7 哈夫曼树 + WPL + 编码

7.7.1 题 7.1

权值 {5, 29, 7, 8, 14, 23, 3, 11}，构造哈夫曼树，求 WPL。

详解：每次取最小两个合并：

WPL = 各叶子权 × 路径长之和。更快的算法：WPL = 所有「合并产生的新节点权值」之和（每次合并的和会被它的所有后代各计一次）。 WPL = 8 + 15 + 19 + 29 + 42 + 58 + 100 = 271。

记住这个技巧：WPL = 全部内部节点（合并新节点）权值之和，比逐叶子算路径长快且不易错。

7.7.2 题 7.2

字符频率 A:5, B:2, C:1, D:1，构造哈夫曼树，写出各字符编码和 WPL。

详解：

        9
      0/ \1
      A   4
     (5) 0/ \1
         B   2
        (2)0/ \1
           C   D
          (1) (1)

编码：A=0, B=10, C=110, D=111。 WPL = 5×1 + 2×2 + 1×3 + 1×3 = 5+4+3+3 = 15（= 内部节点和 2+4+9 = 15 ✓）。

7.8 图算法（DFS/BFS、MST、Dijkstra、拓扑）

7.8.1 题 8.1（DFS/BFS 序列）

无向图，邻接关系：1-{2,3}, 2-{1,4,5}, 3-{1,6}, 4-{2}, 5-{2,6}, 6-{3,5}。从 1 出发，按编号小优先，写出 DFS 和 BFS 序列。

详解：

7.8.2 题 8.2（Kruskal）

无向带权图，边：(1,2)=1, (1,3)=3, (2,3)=2, (2,4)=5, (3,4)=4。用 Kruskal 求 MST 及总权。

详解：边升序：(1,2)1, (2,3)2, (1,3)3, (3,4)4, (2,4)5。

7.8.3 题 8.3（Dijkstra 填表）

有向带权图，源点 1：1→2=4, 1→3=2, 3→2=1, 3→4=5, 2→4=3, 4→5=2, 2→5=7。求 1 到各点最短距离。

详解：

轮 确定点 d2 d3 d4 d5
初始 1(=0) 4 2 ∞ ∞
1 3(=2) 3(经3:2+1) ✓ 7(2+5) ∞
2 2(=3) ✓ ✓ 6(经2:3+3<7) 10(3+7)
3 4(=6) ✓ ✓ ✓ 8(经4:6+2<10)
4 5(=8) ✓ ✓ ✓ ✓

最短距离：1→2=3，1→3=2，1→4=6，1→5=8。

7.8.4 题 8.4（拓扑排序）

有向图：A→B, A→C, B→D, C→D, D→E。写出所有可能的拓扑序列。

详解：入度 A:0 B:1 C:1 D:2 E:1。

7.9 二分查找判定树 + ASL

7.9.1 题 9.1

有序表长 n=10，画二分判定树，求成功 ASL。

详解：下标 1~10，mid=⌊(low+high)/2⌋。

层数统计：第1层 1 个(5)，第2层 2 个(2,8)，第3层 4 个(1,3,6,9)，第4层 3 个(4,7,10)。 成功 ASL = (1×1 + 2×2 + 3×4 + 4×3)/10 = (1+4+12+12)/10 = 29/10 = 2.9。

7.9.2 题 9.2

n=7 的二分判定树成功 ASL。

详解：[1,7]mid=4；左[1,3]mid=2（1,3为孩子）；右[5,7]mid=6（5,7为孩子）。 层数：第1层 1 个(4)，第2层 2 个(2,6)，第3层 4 个(1,3,5,7)。 ASL = (1×1+2×2+3×4)/7 = (1+4+12)/7 = 17/7 ≈ 2.43。（n=7 是满判定树，很整齐）

7.10 哈希表 ASL（两种冲突处理）

7.10.1 题 10.1（线性探测）

关键字 {7, 8, 30, 11, 18, 9, 14}，表长 m=11，H(k)=k%11，线性探测。画表，求成功 ASL。

详解：算地址 k%11：7→7, 8→8, 30→8, 11→0, 18→7, 9→9, 14→3。 依次放：

k 起始 落位过程 比较次数
7 7 7空，放 1
8 8 8空，放 1
30 8 8占→9空，放 2
11 0 0空，放 1
18 7 7占→8占→9占→10空，放 4
9 9 9占→10占→0占→1空，放 4
14 3 3空，放 1

成功 ASL = (1+1+2+1+4+4+1)/7 = 14/7 = 2。

7.10.2 题 10.2（拉链法）

同样的 {7,8,30,11,18,9,14}，H=k%11，拉链法（尾插）。求成功 ASL 和不成功 ASL。

详解：按地址归类（k%11）：

成功 ASL = (1 + 1 + (1+2) + (1+2) + 1)/7 = 9/7 ≈ 1.29。 不成功 ASL（对地址 0~10 共 11 个，每个 = 该链长度）：地址0长1、3长1、7长2、8长2、9长1，其余 6 个长 0。 不成功 ASL = (1+1+2+2+1)/11 = 7/11 ≈ 0.64。

对比题 10.1 的线性探测（成功 ASL=2），拉链法明显更优（1.29），因为没有堆积。

7.11 排序过程模拟

统一用待排序列 49 38 65 97 76 13 27（除特别说明）。

7.11.1 题 11.1（直接插入，写每趟）

详解（[ ]为有序区）：

[49] 38 65 97 76 13 27
[38 49] 65 97 76 13 27
[38 49 65] 97 76 13 27
[38 49 65 97] 76 13 27
[38 49 65 76 97] 13 27
[13 38 49 65 76 97] 27
[13 27 38 49 65 76 97]

7.11.2 题 11.2（冒泡，写每趟，大数往后冒）

详解：

初始:  49 38 65 97 76 13 27
第1趟: 38 49 65 76 13 27 |97
第2趟: 38 49 65 13 27 |76 97
第3趟: 38 49 13 27 |65 76 97
第4趟: 38 13 27 |49 65 76 97
第5趟: 13 27 |38 49 65 76 97
第6趟: 13 |27 ...（无交换，结束）

7.11.3 题 11.3（快速排序，写第一趟 partition，基准=首元素 49）

详解：pivot=49，low/high 双指针填坑：

49 38 65 97 76 13 27   low=0,high=6
右找<49: 27 → 填左: 27 38 65 97 76 13 _
左找>49: 65 → 填右: 27 38 _ 97 76 13 65
右找<49: 13 → 填左: 27 38 13 97 76 _ 65
左找>49: 97 → 填右: 27 38 13 _ 76 97 65
指针相遇,基准归位: 27 38 13 [49] 76 97 65

第一趟结果：27 38 13 49 76 97 65（49 左边都 <49，右边都 >49）。

7.11.4 题 11.4（希尔排序，增量 5,3,1）

对 49 38 65 97 76 13 27 49* 55 04（10 个数，49* 是第二个49）做希尔，写出每个增量后的序列。

详解：

7.11.5 题 11.5（堆排序，建大顶堆）

对 49 38 65 97 76 13 27 建大顶堆，写出建堆后的数组。

详解：完全二叉树，从最后非叶 i=2（下标，值65）开始下沉（下标从0：左孩2i+1）：

7.11.6 题 11.6（归并，写每趟）

详解（自底向上，相邻段两两合并）：

初始(7个,看成7个长1的有序段): [49][38][65][97][76][13][27]
一趟(长2): [38 49][65 97][13 76][27]
二趟(长4): [38 49 65 97][13 27 76]
三趟(长8): [13 27 38 49 65 76 97]

7.12 动态规划（0-1 背包）

7.12.1 题 12.1

物品（重,值）：A(2,3) B(3,4) C(4,5) D(5,6)，背包容量 W=8。填 dp 表求最大价值，并指出选了哪些物品。

详解：dp[i][j] = 前 i 个物品、容量 j 的最大价值。转移：j≥wᵢ 时 dp[i][j]=max(dp[i−1][j], dp[i−1][j−wᵢ]+vᵢ)，否则 dp[i][j]=dp[i−1][j]。

i\j 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
A(2,3) 0 0 3 3 3 3 3 3 3
B(3,4) 0 0 3 4 4 7 7 7 7
C(4,5) 0 0 3 4 5 7 8 9 9
D(5,6) 0 0 3 4 5 7 8 9 10

最大价值 dp[4][8] = 10。 回溯选了谁：dp[4][8]=10 ≠ dp[3][8]=9，说明选了 D（值6），剩容量 8−5=3 看 dp[3][3]=4；dp[3][3]=4=dp[2][3]，说明没选 C；dp[2][3]=4≠dp[1][3]=3，选了 B（值4），剩 3−3=0；dp[1][0]=0 结束。 所以选 B + D，重 3+5=8，值 4+6=10 ✓。

7.13 过关自检

把下面每类都能独立做对至少 2 题，这部分考试就稳了：

错题别只改答案——回到对应讲义小节重读原理，想通「为什么」，下次才不会再错。

以下是一页式「考前必背速查表」——把上面练熟之后，考前最后一遍快速扫过即可。

这一页是纯结论的浓缩，原理见三段讲义。能把这页默写出来，基本盘就稳了。

7.14 复杂度

从快到慢（背死）

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

怎么数：单层循环 O(n)；双层嵌套 O(n²)；循环变量翻倍/折半 O(log n)；分两半递归再合并 O(n log n)。 顺序查找：最好 O(1)、最坏 O(n)、平均 (n+1)/2。 递归空间：算递归栈深度。

7.15 线性结构

顺序表：随机访问 O(1)；插入平均移动 n/2、删除平均 (n−1)/2，均 O(n)。 链表：按位查找 O(n)；已知位置增删 O(1)。插入「先接后断」：s->next=p->next; p->next=s;。删除记得 free。 头指针/头结点/首元结点：头结点不存数据、让首位置不用特判。

循环队列三公式（牺牲一个单元）：

判空: front == rear
判满: (rear+1) % MAXSIZE == front
个数: (rear - front + MAXSIZE) % MAXSIZE

顺序栈：top=-1 空，top=MAXSIZE-1 满；入栈先 ++top 再放。 栈→递归/表达式求值；队列→BFS/层序。

后缀表达式求值：数字入栈，运算符弹两个算完压回（先弹的是右操作数）。

7.16 串 · KMP

朴素匹配 O(n×m)；KMP O(n+m)，失配时 i 不回退、j = next[j]。 next[j] = P[0..j−1] 的最长相等前后缀长度（next[0]=−1）。 （各教材定义有差异，以课本为准，本质不变）

7.17 二叉树性质（必背）

  1. 第 i 层最多 2^(i−1) 个节点。
  2. 高度 k 最多 2^k − 1 个节点（满二叉树）。
  3. n₀ = n₂ + 1（叶子 = 度2节点 + 1）★高频。
  4. n 个节点完全二叉树高度 = ⌊log₂n⌋ + 1。
  5. 完全二叉树编号 i：左孩子 2i、右孩子 2i+1、双亲 ⌊i/2⌋。

二叉链表：n 个节点有 n+1 个空指针（→线索二叉树）。

遍历：前序=根左右、中序=左根右、后序=左右根、层序用队列。 还原：前序+中序 ✓、后序+中序 ✓、前序+后序 ✗（必须有中序）。 BST 中序 = 升序序列★。 求高度：max(左,右)+1；节点数：左+右+1。

7.18 树表 · 平衡

BST：左<根<右；查找/插入/删除平均 O(log n)，最坏退化成链 O(n)。 BST 删除三情况：①叶子直接删 ②一个孩子顶上 ③两个孩子用中序后继(右子树最小)/前驱(左子树最大)替换。

AVL：平衡因子(左高−右高)∈{−1,0,+1}。四种旋转：

LL → 右旋(单)        RR → 左旋(单)
LR → 先左旋再右旋(双)  RL → 先右旋再左旋(双)

口诀：单旋儿子上位、双旋孙子上位。最小例子：1,2,3→RR；3,2,1→LL；1,3,2→RL；3,1,2→LR。

哈夫曼：每次合并最小两个；WPL = 全部内部节点权值之和（速算）；左0右1得编码；前缀码保证解码无歧义。

堆：完全二叉树，大顶堆根最大；数组存(2i+1/2i+2/⌊(i-1)/2⌋)；建堆 O(n)，插入/删除 O(log n)。

并查集：Find 找根、Union 合并；路径压缩+按秩≈O(1)；用于判连通、Kruskal 判环。

B/B+ 树：多路平衡、矮胖减少磁盘 IO；B+ 数据全在叶子且叶子成链（数据库索引）。

7.19 图

存储：邻接矩阵 O(n²)、稠密图、判相连 O(1)、无向对称；邻接表 O(n+e)、稀疏图、遍历邻居快。 遍历：DFS 栈/递归、BFS 队列；都要 visited[] 防环；邻接表 O(n+e)、矩阵 O(n²)。BFS 求无权图最短路。 MST：Prim 加点(稠密 O(n²))、Kruskal 加边(稀疏 O(e log e)，并查集判环)；总权唯一、树可能不唯一。 最短路：

拓扑排序(AOV)：反复输出入度0的点、删出边；输出数<总数→有环；结果不唯一。 关键路径(AOE)：最长路 = 最短工期；e==l 的活动是关键活动(不能拖)。

7.20 查找

二分：前提有序+顺序存储；O(log n)；判定树高 ⌊log₂n⌋+1；成功 ASL = Σ(层数)/n。 分块：块间有序块内无序；最佳块 √n、ASL O(√n)。 哈希：H(k)=k%p(p 取≤表长最大质数)；不比较直接算地址平均 O(1)。

7.21 排序总表（背死）

算法 最好 平均 最坏 空间 稳定
直接插入 O(n) O(n²) O(n²) O(1) ✓
折半插入 O(n) O(n²) O(n²) O(1) ✓
希尔 — O(n^1.3) O(n²) O(1) ✗
冒泡 O(n) O(n²) O(n²) O(1) ✓
快速 O(nlogn) O(nlogn) O(n²) O(logn) ✗
简单选择 O(n²) O(n²) O(n²) O(1) ✗
堆排 O(nlogn) O(nlogn) O(nlogn) O(1) ✗
归并 O(nlogn) O(nlogn) O(nlogn) O(n) ✓
基数 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) ✓

口诀：不稳定的「快选堆希」；平均 nlogn 的「快堆归」；最坏退化 O(n²) 只有快排；空间例外：快排 O(logn)、归并 O(n)。 一趟特征：冒泡→最大归位末尾；快排→基准归位左小右大；选择→最小到最前；堆→建堆/堆顶换末尾。

外部排序：基于归并；k 路归并减少趟数(趟数=⌈log_k 段数⌉)→减 IO；败者树加速选最小；最佳归并树用哈夫曼思想。

7.22 算法设计策略

策略 核心 关键 例子
分治 分→治→合 子问题独立 归并/快排/二分/快速幂
贪心 每步局部最优 需贪心选择性质 哈夫曼/Prim/Kruskal/Dijkstra/分数背包
动态规划 存重叠子问题解 重叠+最优子结构 0-1背包/LCS/斐波那契/Floyd
回溯 DFS+剪枝+撤销 解空间树穷举 N皇后/全排列/迷宫
分支限界 BFS/优先级+界限 求最优解 0-1背包最优/TSP

辨析：分治vs DP=子问题独立vs重叠；分数背包用贪心、0-1背包用 DP；回溯 DFS 求所有解、分支限界 BFS 求最优解。 DP 四步：定义状态→转移方程→边界→计算顺序。 0-1 背包转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-wᵢ]+vᵢ)。

7.23 全课一句话灵魂

没有最好的结构，只有最合适的。每个设计都是在「时间 vs 空间」「访问快 vs 增删快」之间做权衡。 每学一个结构就问：它牺牲了什么、换来了什么？