数据结构复习提纲

根据课程重点整理，涵盖各章节核心考点与示例

第1章绪论 / 时间复杂度

考点

while循环的时间复杂度分析，特别是基本语义变量与循环变量有关联的情况

示例问题

问题：分析以下代码的时间复杂度

int i = 1;
while (i <= n) {
    i = i * 2;
}

答案：O(log₂n)。循环变量 i 以指数增长，执行次数为 log₂n。

问题：分析以下嵌套循环的时间复杂度

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        // 操作
    }
}

答案：O(n²)。内层循环次数为 1+2+3+...+n = n(n+1)/2。

第2章线性表

2.1 顺序表

考点

插入元素时移动元素个数：分最好情况、最坏情况、平均情况
顺序表支持随机存取（O(1)时间访问任意位置）

示例问题

问题：在长度为 n 的顺序表中插入一个元素，分别求最好、最坏、平均情况下需要移动的元素个数。

答案： | 情况 | 插入位置 | 移动元素个数 | |------|---------|------------| | 最好 | 表尾（第 n+1 位） | 0 | | 最坏 | 表头（第 1 位） | n | | 平均 | 等概率随机插入 | n/2 |

平均情况推导：等概率插入 n+1 个位置，移动次数分别为 n, n-1, ..., 1, 0 $$ASL = \frac{1}{n+1} \sum_{i=0}^{n} i = \frac{n(n+1)/2}{n+1} = \frac{n}{2}$$

2.2 链表（重点）

考点

链表原地逆置：不借助额外空间，将链表元素翻转（空间复杂度 O(1)）

示例问题

问题：给定一个带头结点的单链表，编写算法在不使用额外数据空间的情况下将其逆置。

答案：

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 原地逆置单链表
void Reverse(LinkList &L) {
    LNode *p = L->next;    // p指向第一个数据节点
    L->next = NULL;        // 头结点指向空，作为新链表的尾

    while (p != NULL) {
        LNode *q = p;      // q保存当前节点
        p = p->next;       // p后移
        q->next = L->next; // 头插法：q插入到头结点之后
        L->next = q;
    }
}

解析：使用三个指针（p遍历原链表，q保存当前节点，L->next指向新链表头），逐个将节点头插到新链表中，实现逆置。空间复杂度 O(1)，时间复杂度 O(n)。

第3章栈和队列

3.1 栈

考点

给定入栈序列，判断可能的出栈次序
栈的本质是操作受限的线性表（先进后出 FILO）

示例问题

问题：入栈序列为 1, 2, 3，判断以下出栈序列是否可能： - (1) 3, 2, 1 - (2) 2, 3, 1 - (3) 3, 1, 2

答案： - (1) 可能。1入→2入→3入→3出→2出→1出 - (2) 可能。1入→2入→2出→3入→3出→1出 - (3) 不可能。3先出说明1,2,3都已入栈，此时栈顶是2，1在栈底，1不可能在2之前出栈。

3.2 队列

考点

循环队列的长度计算：区分长度（元素个数）与容量
循环队列的队空和队满条件
队列也是受限线性表（先进先出 FIFO）

示例问题

问题：循环队列用数组实现，队头指针 front，队尾指针 rear，数组容量为 MaxSize。如何计算队列长度？队空和队满的条件是什么？

答案：

// 牺牲一个单元区分队空和队满
队列长度 = (rear - front + MaxSize) % MaxSize;

// 队空条件：front == rear
// 队满条件：(rear + 1) % MaxSize == front

解析：循环队列通过取模运算实现"循环"，长度计算需考虑 rear 可能在 front 之前的情况。牺牲一个存储单元是为了区分队空和队满两种状态。

第4章串

4.1 数组

考点

数组元素地址计算：给定行列数、元素大小、按行/列优先存储方式
二维数组的地址计算

示例问题

问题：二维数组 A[0..9][0..9]，每个元素占 4 个存储单元，按行优先存储，基地址为 1000。求 A[2][5] 的地址。

答案： $$LOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times L$$ $$LOC(A[2][5]) = 1000 + (2 \times 10 + 5) \times 4 = 1000 + 25 \times 4 = 1100$$

4.2 模式匹配

考点

KMP算法相对于BF算法的主要优势

示例问题

问题：KMP算法相对于BF（暴力）算法的主要优势是什么？

答案： 1. 主串指针不回溯：BF算法匹配失败时主串指针回溯，KMP利用已匹配信息避免回溯 2. 时间复杂度 O(m+n)：BF为 O(m×n)，KMP为线性时间 3. 通过next数组：预处理模式串，利用最长公共前后缀信息跳过不必要的比较

4.3 广义表

考点

广义表的深度：计算括号嵌套层数

示例问题

问题：求广义表 A = (a, (b, c), ((d, e), f)) 的深度。

答案：深度为 3。

解析：深度 = 括号的最大嵌套层数。 - 第1层：A 本身 - 第2层：(b, c) 和 ((d, e), f) - 第3层：(d, e)

第5章树和二叉树

5.1 完全二叉树性质

考点

完全二叉树叶子节点数：给定 n 个节点，会算叶子节点数
二叉树性质：度为1的节点要么为0，要么为1
满二叉树 vs 完全二叉树：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树

示例问题

问题1：一棵完全二叉树有 100 个节点，求叶子节点数。

答案： - 设 n₀ 为叶子节点数，n₁ 为度为1的节点数，n₂ 为度为2的节点数 - 节点总数：n = n₀ + n₁ + n₂ = 100 - 分支数：n - 1 = n₁ + 2n₂（总分支数 = 总节点数 - 1） - 联立得：n₀ = n₂ + 1 - 完全二叉树中 n₁ 只能是 0 或 1 - 代入：100 = n₀ + n₁ + (n₀ - 1) = 2n₀ + n₁ - 1 - 若 n₁ = 0：2n₀ = 101（不成立，n₀ 不是整数） - 若 n₁ = 1：2n₀ = 100，n₀ = 50

叶子节点数为 50

问题2：完全二叉树中度为1的节点个数有什么规律？

答案： - 完全二叉树中度为1的节点个数只能是 0 或 1 - 原因：完全二叉树只在最底层从右往左连续缺少若干节点 - 若节点总数 n 为偶数：度为1的节点数为 1 - 若节点总数 n 为奇数：度为1的节点数为 0

5.2 遍历序列恢复二叉树

考点

由先序+中序或后序+中序恢复二叉树

示例问题

问题：先序序列为 ABDECF，中序序列为 DBEACF，画出该二叉树。

答案：

步骤： 1. 先序第一个元素 A 是根节点 2. 在中序中找到 A，左边 DBE 是左子树，右边 CF 是右子树 3. 左子树先序为 BDE，中序为 DBE → B 是根，D 在左，E 在右 4. 右子树先序为 CF，中序为 CF → C 是根，F 在右

5.3 线索二叉树

考点

根据遍历序列画先序线索二叉树

示例问题

问题：画出上述二叉树的先序线索二叉树。

答案：

先序遍历序列：A → B → D → E → C → F

线索化规则： - 若左孩子为空，则左指针指向其先序前驱 - 若右孩子为空，则右指针指向其先序后继

线索： - D 的左线索为空（先序第一个），右线索指向 E - E 的左线索为空，右线索指向 C - F 的左线索为空，右线索为空（先序最后一个）

5.4 树、森林与二叉树的转换

考点

树 ↔ 二叉树 ↔ 森林的相互转换（孩子兄弟表示法）

示例问题

问题：将以下森林转换为二叉树。

森林： - 树1：A(B(E,F), C, D) - 树2：G(H, I)

答案：

步骤： 1. 每棵树先转为二叉树（左孩子右兄弟） 2. 树1转二叉树：A 为根，B 为左孩子，C 为 B 的右兄弟，D 为 C 的右兄弟；E、F 为 B 的左孩子和右兄弟 3. 树2转二叉树：G 为根，H 为左孩子，I 为 H 的右兄弟 4. 森林转二叉树：将树2的根 G 作为树1根 A 的右孩子

        A
       / 
      B — C — D
     / 
    E — F

    (G 作为 A 的右孩子)

第6章图

6.1 握手定理

考点

给定边数和顶点度范围，求顶点数

示例问题

问题：无向图有 18 条边，度为4的顶点有2个，度为3的顶点有4个，度为5的顶点有1个，其余顶点度为1或2。求总顶点数。

答案： - 握手定理：所有顶点度数之和 = 2 × 边数 = 36 - 已知顶点度数和：4×2 + 3×4 + 5×1 = 8 + 12 + 5 = 25 - 剩余度数：36 - 25 = 11 - 设度为1的顶点有 x 个，度为2的顶点有 y 个 - 方程：x + 2y = 11，且 x + y = 剩余顶点数 - 可能解：y=5, x=1（顶点数6）或 y=4, x=3（顶点数7）等 - 需根据题目其他条件确定唯一解

6.2 图的遍历

考点

会写 DFS 和 BFS 遍历序列
实现区别：DFS用栈/递归，BFS用队列

示例问题

问题：给定下图，从顶点 A 出发写出 DFS 和 BFS 序列。

    A — B — C
    |   |   |
    D — E — F

答案： - DFS（深度优先）：A → B → C → F → E → D（假设邻接表按字母序） - BFS（广度优先）：A → B → D → C → E → F

实现区别： | | DFS | BFS | |--|-----|-----| | 数据结构 | 栈（递归隐式栈） | 队列 | | 访问顺序 | 深入到底再回溯 | 逐层扩展 | | 应用 | 连通分量、拓扑排序 | 最短路径（无权图） |

6.3 最小生成树

考点

Prim算法和Kruskal算法的构造过程

示例问题

问题：用 Prim 算法求以下图的最小生成树。

    A —2— B —3— C
    |4    |1    |5
    D —6— E —2— F

答案：

Prim算法步骤（从A开始）： 1. 选 A，邻接边：(A,B,2), (A,D,4)，选最小 (A,B,2) 2. 集合 {A,B}，邻接边：(A,D,4), (B,E,1), (B,C,3)，选最小 (B,E,1) 3. 集合 {A,B,E}，邻接边：(A,D,4), (B,C,3), (E,D,6), (E,F,2)，选最小 (E,F,2) 4. 集合 {A,B,E,F}，邻接边：(A,D,4), (B,C,3), (E,D,6)，选最小 (B,C,3) 5. 集合 {A,B,E,F,C}，邻接边：(A,D,4), (E,D,6)，选最小 (A,D,4)

最小生成树总权值：2 + 1 + 2 + 3 + 4 = 12

6.4 拓扑排序

考点

适用于有向无环图（DAG）
有环图无法进行拓扑排序
拓扑排序应用：项目管理（AOV网）

示例问题

问题：判断以下有向图能否进行拓扑排序。

    A → B → C
    ↑       ↓
    └———————D

答案： - 存在环：A → B → C → D → A - 不能进行拓扑排序 - 原因：环中每个顶点都有前驱，找不到入度为0的顶点作为起点

6.5 邻接矩阵

考点

无向图的邻接矩阵是对称的
根据邻接矩阵画图
根据边集和顶点集写出邻接矩阵

示例问题

问题：无向图的邻接矩阵有什么特点？

答案： - 对称矩阵：A[i][j] = A[j][i] - 对角线元素为0（无自环） - 第 i 行（或第 i 列）非零元素个数 = 顶点 i 的度

第7章查找

7.1 哈希表（重点）

考点

用除留余数法构造哈希表
三种冲突解决方法：线性探测法、二次探测法、链地址法
线性探测法的缺点：聚集现象
二次探测法解决冲突时产生的问题
哈希表三层结构：下标、关键字位置、查找比较次数
平均查找长度（ASL）计算
哈希表长度与地址空间的关系

示例问题

问题1：关键字序列 {7, 8, 30, 11, 18, 9, 14}，哈希函数 H(key) = key mod 7，用线性探测法解决冲突，构造哈希表并计算 ASL。

答案：

下标	0	1	2	3	4	5	6
关键字	7	14	9	8	18	30	11
比较次数	1	7	2	1	2	1	1

计算过程： - H(7) = 0，下标0空，放入，比较 1 次 - H(14) = 0，冲突→1,2,3,4,5,6空，放入，比较 7 次 - H(30) = 2，下标2空，放入，比较 1 次 - H(11) = 4，下标4空，放入，比较 1 次 - H(18) = 4，冲突→5空，放入，比较 2 次 - H(9) = 2，冲突→3空，放入，比较 2 次 - H(8) = 1，下标1空，放入，比较 1 次

ASL（成功） = (1+7+1+1+2+2+1) / 7 = 15/7 ≈ 2.14

线性探测法缺点：产生"聚集"现象，如 14 需要探测多次才能找到空位。

问题2：哈希表地址空间为 0~8，哈希表长度是多少？

答案：9（0~8 共 9 个地址单元）

解析：哈希表长度 m = 9，哈希函数 H(key) = key mod m 中的 m 就是表长。表长与解决冲突时的增量计算直接相关。

问题3：二次探测法解决冲突时会产生什么问题？

答案： - 二次探测法：Hᵢ = (H(key) + dᵢ) mod m，其中 dᵢ = 1², -1², 2², -2², ... - 优点：可以缓解聚集现象（避免线性探测的连续堆积） - 缺点：可能产生二次聚集（二次堆积），且不一定能探测到所有空位

7.2 二叉排序树（BST）

考点

给定序列建立二叉排序树
计算查找成功时的平均查找长度

示例问题

问题：给定关键字序列 {50, 30, 70, 20, 40, 60, 80}，建立二叉排序树并计算查找成功时的 ASL。

答案：

        50
       /  \
     30    70
    / \   / \
  20  40 60  80

查找过程： | 关键字 | 所在层 | 比较次数 | |--------|--------|---------| | 50 | 1 | 1 | | 30 | 2 | 2 | | 70 | 2 | 2 | | 20 | 3 | 3 | | 40 | 3 | 3 | | 60 | 3 | 3 | | 80 | 3 | 3 |

ASL（成功） = (1×1 + 2×2 + 4×3) / 7 = 17/7 ≈ 2.43

解析：查找时先与根比较，小则走左子树，大则走右子树，递归进行。

7.3 折半查找

考点

对有序顺序表进行二分查找
查找失败时最多比较次数

示例问题

问题：在有序表 {5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92} 中查找 20，最多比较几次？画出判定树。

答案：

判定树：

            56(5)
           /     \
        19(2)    80(8)
       /    \    /    \
    13(1)  37(4) 64(7)  88(10)
   /       /       \      /   \
  5(0)   21(3)    75(6)  92(11)

查找 20： 1. 与 56 比较，20 < 56，进入左子树 2. 与 19 比较，20 > 19，进入右子树 3. 与 37 比较，20 < 37，进入左子树 4. 与 21 比较，20 < 21，应到左子树但为空

查找失败，比较 4 次

最多比较次数 = 树高 = ⌈log₂(n+1)⌉ = ⌈log₂12⌉ = 4

第8章排序

8.1 快速排序

考点

快速排序过程
快速排序在数据基本有序时效率最差

示例问题

问题：对序列 {49, 38, 65, 97, 76, 13, 27, 49} 进行快速排序，写出第一趟结果。

答案：

选第一个元素 49 为枢轴：

初始：49, 38, 65, 97, 76, 13, 27, 49

过程（双向扫描）： 1. 从右向左找 < 49 的：27，与 49 交换位置 → 27, 38, 65, 97, 76, 13, 49, 49 2. 从左向右找 > 49 的：65，与 49 交换 → 27, 38, 49, 97, 76, 13, 65, 49 3. 从右向左找 < 49 的：13，交换 → 27, 38, 13, 97, 76, 49, 65, 49 4. 从左向右找 > 49 的：97，交换 → 27, 38, 13, 49, 76, 97, 65, 49 5. 从右向左找 < 49 的：无（左右指针相遇）

第一趟结果：27, 38, 13, 49, 76, 97, 65, 49 （49 已归位，左边都小于49，右边都大于等于49）

问题：快速排序在什么情况下效率最差？为什么？

答案： - 数据基本有序时效率最差 - 原因：每次选择的枢轴都是当前子序列的最大/最小值，导致划分极不平衡 - 时间复杂度退化为 O(n²) - 改进：随机选择枢轴或三数取中法

8.2 堆排序

考点

建堆过程（大根堆/小根堆）
堆排序是增序还是降序？

示例问题

问题：堆排序如果要排增序，应该建大根堆还是小根堆？

答案： - 排增序 → 建大根堆 - 原因：每次将堆顶（最大值）与最后一个元素交换，最大值放到末尾，然后对前面元素重新调整堆 - 类似地，排降序 → 建小根堆

排序算法对比表

算法	最好时间	平均时间	最坏时间	空间复杂度	稳定性
直接插入排序	O(n)	O(n²)	O(n²)	O(1)	✅ 稳定
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	✅ 稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	❌ 不稳定
简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	❌ 不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	❌ 不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ 稳定

附加：哈夫曼树

考点

根据字符频率构造哈夫曼树
计算带权路径长度（WPL）
写出哈夫曼编码
由 n 个权值构成的哈夫曼树有多少个节点
根据哈夫曼编码计算报文长度

示例问题

问题1：字符集 {A, B, C, D}，频率分别为 {4, 7, 5, 2}，构造哈夫曼树并求 WPL 和编码。

答案：

构造过程： 1. 选最小两个：D(2), A(4) → 合并为 6 2. 选最小两个：C(5), B(7) → 合并为 12 3. 选最小两个：6, 12 → 合并为 18（根）

          18
         /  \
        6    12
       / \   / \
      D   A C   B
     (2) (4)(5) (7)

哈夫曼编码（左0右1）： | 字符 | 编码 | 路径长度 | |------|------|---------| | D | 00 | 2 | | A | 01 | 2 | | C | 10 | 2 | | B | 11 | 2 |

WPL = 2×2 + 4×2 + 5×2 + 7×2 = 36

或：WPL = 所有非叶子节点权值之和 = 6 + 12 + 18 = 36

特点：哈夫曼编码是前缀编码，任何编码都不是另一个编码的前缀，确保解码唯一。

问题2：由 n 个权值构成的哈夫曼树有多少个节点？

答案：2n - 1 个节点

推导： - n 个叶子节点（权值节点） - 每次合并产生一个新节点，共需 n-1 次合并 - 总节点数 = n + (n-1) = 2n - 1

问题3：根据上述哈夫曼编码，若报文为 "ABCD"，计算编码后的报文长度。

答案： - A: 01 (2位) - B: 11 (2位) - C: 10 (2位) - D: 00 (2位) - 报文 "ABCD" 编码：01 11 10 00 - 总长度 = 2+2+2+2 = 8 位

答题注意事项

排序题：不要只写一轮结果，要写出完整的排序过程，每轮都要展示
画图题：二叉树、线索二叉树、哈夫曼树、图等要画清楚
计算题：写出推导过程，不要只写结果
算法题：链表逆置等要写完整代码或清晰步骤

祝考试顺利！🎓

数据结构复习提纲

数据结构复习提纲

第1章 绪论 / 时间复杂度

考点

示例问题

第2章 线性表

2.1 顺序表

考点

示例问题

2.2 链表（重点）

考点

示例问题

第3章 栈和队列

3.1 栈

考点

示例问题

3.2 队列

考点

示例问题

第4章 串

4.1 数组

考点

示例问题

4.2 模式匹配

考点

示例问题

4.3 广义表

考点

示例问题

第5章 树和二叉树

5.1 完全二叉树性质

考点

示例问题

5.2 遍历序列恢复二叉树

考点

示例问题

5.3 线索二叉树

考点

示例问题

5.4 树、森林与二叉树的转换

考点

示例问题

第6章 图

6.1 握手定理

考点

示例问题

6.2 图的遍历

考点

示例问题

6.3 最小生成树

考点

示例问题

6.4 拓扑排序

考点

示例问题

6.5 邻接矩阵

考点

示例问题

第7章 查找

7.1 哈希表（重点）

考点

示例问题

7.2 二叉排序树（BST）

考点

示例问题

7.3 折半查找

考点

示例问题

第8章 排序

8.1 快速排序

考点

示例问题

8.2 堆排序

考点

示例问题

排序算法对比表

附加：哈夫曼树

考点

示例问题

答题注意事项

第1章绪论 / 时间复杂度

第2章线性表

第3章栈和队列

第4章串

第5章树和二叉树

第6章图

第7章查找

第8章排序