附录：考前复盘笔记

这一章是我考前最后一晚自己手写的复盘笔记，口吻随意、密度很高——先把八章知识点按章快速过一遍，再记下刷题时反复踩的易错点，然后是几段「不能调库时得默写出来」的算法模板，最后一套带答案的模拟题自测。和前面正文的系统讲解相比，这里更像「考前临门一脚」的速记。

9.1 知识点回顾（按章速过）

9.1.1 数据结构基础知识

malloc是手动在堆上申请分配内存，存活时间是全局的，直到在其他地方free。 注意malloc直接返回指针。

逻辑结构：集合，线性，树形，图状 存储结构：顺序（数组），链式（链表指针），索引（目录），散列（哈希表）

时间复杂度 O(n) 空间复杂度，如果原地就是O(1)，额外开了一个一样大的则是O(n)

9.1.2 线性表

一对一线性结构，(a₁, a₂, ..., aₙ)

顺序表（线性表的顺序实现），即为数组：

• 查找的时间复杂度是O(1)
• 移动，删除的时间复杂度是O(n)

单链表（线性表的链式实现），即为链表：

• 查找的时间复杂度是O(n)
• 移动，删除的时间复杂度是O(1)，注意删除还需要free节点

循环链表：把单链表最后一个节点的 next 由 NULL 改为指向头结点，整条链就首尾相连成一个环。

双链表：存两个指针（next和piror），前后都可以走

9.1.3 栈与队列

栈：后进先出，一般用数组实现，核心是push, pop, top这三个操作 应用：括号匹配 前后缀表达式和中缀表达式的转换（画二叉树，用前中后序遍历） 后缀表达式求值（用一个栈）：从左到右扫描——遇到操作数就入栈；遇到运算符，就弹出栈顶两个操作数做运算，结果再压回栈。扫描结束栈里剩的唯一一个数就是答案。

队列：先进先出，数组实现则需要“循环队列”，防止假溢出，链表实现则不需要。

9.1.4 串和数组

串，就是字符串，如何匹配字符串是一个核心问题 KMP算法

稀疏矩阵：

• 三元组：每个非零元素记成一个三元组 (行, 列, 值)，把所有非零元素的三元组存进一个数组
• 十字链表：用链表把每行、每列的非零元素分别串起来

9.1.5 树与二叉树

看到树，就想到递归

节点的度：有几个孩子

完全二叉树：不需要满，但中间不能有空缺

叶子节点数 n₀ = 度为 2 的节点数 n₂ + 1，即 n₀ = n₂ + 1

二叉树怎么存储？完全二叉树可以用数组，一般二叉树用二叉链表（也就是一堆节点用指针连接）

二叉树怎么遍历？

• DFS：前中后序（递归），注意前/后+中可以还原，前+后不可以
• BFS：逐层遍历（队列）

线索二叉树：对于很稀疏的二叉树，把空着的指针废物利用，左指针为空就指向该节点的中序前驱，如果右指针为空，就指向中序后继。再加两个ltag和rtag区分（0说明是真实的孩子，1说明是线索），方便遍历。

二叉搜索树/二叉排序树（BST）：左子树 < 根 < 右子树 查找就是二分查找了，插入也类似， 删除麻烦点：

• 没有孩子：直接删
• 有一个孩子，顶替上来
• 有两个孩子：用中序前继/后继（左右子树）

平衡二叉树（AVL）： 防止BST退化，在BST基础上进行的约束 AVL最小高度N(h)？ N(h) = N(h-1) + N(h-2) + 1 （左子树高 h-1、右子树高 h-2，再加根自己） 边界：N(0) = 0（空树）, N(1) = 1, N(2) = 2 AVL失衡处理办法：

1. 从插入点往上，找到第一个失衡的节点A
2. 匹配四种类型做响应操作
   • LL：右旋，A的左孩子上位，LR挂到A左边
   • RR：左旋，A的右孩子上位，RL接到A右边
   • LR：先对L左旋，再对A右旋（让LR上位，L还是L，A变成R）
   • RL：先对R右旋，再对A左旋（让RL上位，R还是R，A变成L） 响应本质是让AVL不管怎么插入，始终在满足BST基础下平衡

哈夫曼树：编码最短的构造 注意每次是从所有里面选两个拼接，包括已有的树，不要一条路走到底。 编码即左0右1, WPL是编码完之后的总位数 注意哈夫曼树不一定唯一（相等权值）但WPL一定唯一且最小

堆：一种特殊的完全二叉树，满足节点和孩子之间的大小关系。 移动删除都是“上浮和下沉”

树转二叉树：左孩子右兄弟

9.1.6 图

怎么存储图？邻接矩阵/邻接表 邻接矩阵的第i行第j列是 i -> j 无向图的邻接矩阵对称 邻接多重表：无向图用，只存一次

怎么遍历图？DFS，BFS。

生成树：用最少的边联通所有顶点的方式，在带权图里面，权值最小的生成树就是最小生成树（MST） 两种算法：

• Prim：把顶点分成「已在树里的」和「还没进树的」，在所有「一端在树里、一端在树外」的边中，选权值最小的那条，拉入树内，适合稠密图。
• Kruskal：把所有边按权值从小到大排序，然后从最小的边开始一条条考察：如果加入这条边不会形成环，就加入；会成环就跳过，直到选够 n−1 条边为止，适合稀疏图。

最短路径：

• Dijkstra：从一个节点出发，每次确定当前所能触及的最短的路径，加入visited数组中，继续迭代下一次（不能有负权边），堆优化是缩短了“找到最小路径”的方式，原先是遍历，现在用堆优化就快很多。
• Floyd：用邻接矩阵 A[i][j] 存当前 i 到 j 的最短距离。然后枚举每一个顶点 k 作为「中转站」，看「i 经过 k 到 j」是不是比「i 直接到 j」更短，更短就更新。三重循环，外层是中转点 k，内层是所有点对 (i, j)。

拓扑排序：Kahn算法和DFS，注意结果一般不唯一

9.1.7 查找表

ASL，平均查找长度

顺序查找：最慢，O(n) 二分查找：必须有序，O(log n) 分块查找：最佳分块是O(√n) 树表查找：BST一般O(log n)，可能退化O(n)，AVL始终O(log n) 哈希表：空间换时间，O(1)

9.1.8 排序

稳定性：若两个元素关键字相等，排序后它们的相对前后位置不变，就叫稳定；若可能被交换顺序，就不稳定。

直接插入排序：O(n²) 折半插入排序：O(n²)，比较次数变成O(n log n) 希尔排序：gap，最后再插入排序，平均O(n^1.3)，第一个突破O(n²)的排序 冒泡排序：O(n²) 快速排序：递归，取基准，双指针，平均 O(n log n)，但最坏 O(n²)（当数列基本有序、基准每次都取到最小/最大值时退化）。空间 O(log n)（递归栈）。 选择排序：O(n²) 堆排序：建堆 O(n)，之后 n−1 次下沉每次 O(log n)，整体 O(n log n)，且最好/平均/最坏都是 O(n log n)（性能稳定，无退化） 归并排序：递归，对半分到极致，之后逐渐合并，分 log n 层、每层合并共 O(n)，最好/平均/最坏都是 O(n log n)

9.2 刷题小结（易错点速记）

后缀表达式（前中后序遍历）

稀疏矩阵存储（三元组表，十字链表）

三元组表并不创新，只是用三个东西记位置，适合压缩，但查找的适合还是需要遍历，插入删除都不方便，牵一发而动全身。 

十字链表就只需要改指针，方便很多，本质就是用链表而不是矩阵的形式存储，这样可以“跳过”太多空位置，一次性直接指向下一个有信息的元素，当然还是有行和列的概念。 

注意先序/前序 的“前”是指 根

二叉树里面节点的“度”指的是孩子数

哈希冲突里面的处理方法：

• 开放定址法的线性探测：冲突了直接往后走

• 开放定址法的二次探测：冲突了用平方左右跳

• 链地址法：每个位置挂一个链表，冲突了就往后挂

任意一颗二叉树，用前序/中序/后序遍历并不改变叶子节点的相对次序关系

归并排序不管数列情况，基本上都是O(n·logn)

关键字序列：折半查找时比较过的元素，按顺序列出来就行

哈夫曼树要记得不是直接走到底，而是每次取最小的两个叠加。

ASL是平均查找长度，分母的n是指一共要找多少个元素。

哈希表：

• 直接计算就能找到：1次

• 直接计算发现不是：按照具体探测方式定位，用几次找到算几次

邻接表的形式是一系列链表，但其实是并列的，如0——2——1——4，其实指的是0分别指向2,1,4，他们是并列而非前后关系，用链表只是为了存储方便。

拓扑序列：每次弹出入度为0的节点，如果结束发现并没有遍历所有节点，说明有环。

拓扑序列通常不唯一。

拓扑排序是一种针对有向图的线性排序方式，核心是该排序严格符合所有有向边的先后顺序。主要有两种实现方式：

BFS（Kahn算法）：初始情况下找到一个入度为0的节点，压入栈，消除所有它发出的边，之后弹出并打印，弹出后下一步把所有入度为0的节点都压入，按照顺序（邻接矩阵行顺序）依次弹出并打印，同样，每次弹出一个节点后消除所有它发出的边，有入度为0就压入，之后继续栈内下一个，直到结束。

DFS：对每个节点做DFS，在递归返回时把节点压入栈（即所有后继都处理完才入栈），全部完成后把栈逆序输出，就是拓扑序。若DFS中遇到正在访问的节点说明有环。

顺序存储方式（数组）不止可以用来存线性结构，完全二叉树也可以

9.3 考前突击：手写算法模板（不能调 STL 时手写）

9.3.1 栈（数组实现）

typedef struct {
    int data[MAXSIZE];
    int top;          // 栈顶下标，初始 -1
} Stack;

void init(Stack *s){ s->top = -1; }
int isEmpty(Stack *s){ return s->top == -1; }
int isFull(Stack *s){ return s->top == MAXSIZE - 1; }
int push(Stack *s, int x){
    if(isFull(s)) return 0;
    s->data[++s->top] = x; return 1;
}
int pop(Stack *s, int *x){
    if(isEmpty(s)) return 0;
    *x = s->data[s->top--]; return 1;
}

9.3.2 循环队列（数组实现，牺牲一个单元判满）

typedef struct {
    int data[MAXSIZE];
    int front, rear;  // 初始都为 0
} Queue;

void init(Queue *q){ q->front = q->rear = 0; }
int isEmpty(Queue *q){ return q->front == q->rear; }
int isFull(Queue *q){ return (q->rear + 1) % MAXSIZE == q->front; }
int enqueue(Queue *q, int x){          // 入队
    if(isFull(q)) return 0;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE; return 1;
}
int dequeue(Queue *q, int *x){         // 出队
    if(isEmpty(q)) return 0;
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE; return 1;
}
// 队列长度 = (rear - front + MAXSIZE) % MAXSIZE

9.3.3 快速排序（partition + 递归）

int partition(int a[], int low, int high){
    int pivot = a[low];                // 取基准
    while(low < high){
        while(low < high && a[high] >= pivot) high--;
        a[low] = a[high];
        while(low < high && a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low] = pivot;                    // 基准归位
    return low;
}
void quickSort(int a[], int low, int high){
    if(low < high){
        int p = partition(a, low, high);
        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }
}

9.3.4 归并排序（merge 两个有序段）

void merge(int a[], int tmp[], int l, int mid, int r){
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];  // <= 保证稳定
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r)   tmp[k++] = a[j++];
    for(k = l; k <= r; k++) a[k] = tmp[k];
}
void mergeSort(int a[], int tmp[], int l, int r){
    if(l < r){
        int mid = (l + r) / 2;
        mergeSort(a, tmp, l, mid);
        mergeSort(a, tmp, mid + 1, r);
        merge(a, tmp, l, mid, r);
    }
}

9.3.5 Dijkstra（伪代码，单源最短路，不能有负权边）

dist[s] = 0, 其余 dist[] = ∞
visited[] = false
重复 n 次：
    在所有 visited=false 的点中，选 dist 最小的 u
    visited[u] = true
    对 u 的每个邻居 v：           // 松弛
        if !visited[v] && dist[u] + w(u,v) < dist[v]:
            dist[v] = dist[u] + w(u,v)
// 堆优化：用小根堆代替"线性扫描找最小 u"，O((V+E)logV)

9.3.6 哈希表要点（ASL 计算）

• 装填因子 α = 表中元素数 / 表长，α 越大冲突越多。
• ASL_成功 = 找到每个已存在元素的比较次数之和 / 元素个数。
• ASL_失败 = 对每个哈希地址，从该位置探测到第一个空位的比较次数之和 / 哈希地址数(模数)。
• 线性探测：(h+i) % m；二次探测：(h ± i²) % m；链地址法：挂链表，ASL_失败按链长算。

9.4 模拟练习题（含答案）

9.4.1 选择 / 填空（复杂度 + 概念）

1. 一棵完全二叉树有 1000 个节点，叶子节点有多少个？

答案：n₀=n₂+1，n=n₀+n₁+n₂。完全二叉树 n₁=0或1。n=1000偶数→n₁=1。1000=n₀+1+(n₀−1)→n₀=500。

2. 含 n 个单元的循环队列，最多能存多少元素？

答案：牺牲一个单元判满，MAXSIZE−1。

3. 最坏情况时间复杂度为 O(n log n) 的排序：A.快排 B.堆排序 C.冒泡 D.直接插入

答案：B 堆排序（快排最坏 O(n²)；归并也满足但不在选项）。

4. 哈希表装填因子 α 越大会怎样？

答案：空间利用率高，但冲突概率大、ASL 变长。

5. 邻接表存 n 顶点 e 边的无向图，边结点总数？

答案：2e（每条边存两次）；有向图为 e。

9.4.2 简答

6. 快排为何不稳定，归并为何稳定？

答案：快排：partition 时基准与远处元素交换，相等元素相对位置可能颠倒→不稳定。归并：merge 时 a[i]<=a[j] 取左段，相等优先取前段→稳定。

7. Prim 与 Kruskal 各适合什么图？

答案：Prim 按顶点扩展，复杂度与顶点相关，适合稠密图；Kruskal 按边排序，与边数相关，适合稀疏图。

9.4.3 写中间结果

8. [49,38,65,97,76,13,27] 快排第一趟（基准取首元素49）结果？

答案：基准49归位，左<49右>49：[27,38,13,49,76,97,65]。

9. 关键字 {19,14,23,1,68,20,84,27,55,11,10,79}，m=13，H(k)=k%13，线性探测。

答案：逐个填：19→6；14→1；23→10；1→1冲突→2；68→3；20→7；84→6冲突→8；27→1,2,3冲突→4；55→3冲突→9；11→11；10→10冲突→11冲突→12；79→1起冲突一路探测到空位（下标0）。 ASL_成功 = 各元素比较次数之和 / 12（考场把表画出来逐个数比较次数）。

10. 先序 ABDECFG，中序 DBEAFCG，求后序。

答案：根A；左子树(先序DBE/中序DBE)，右子树(先序CFG/中序FCG)。B左D右E，C左F右G。 后序：DEBFGCA。

9.4.4 算法实现（写代码）

11. 用栈判断 ()[]{} 括号匹配。

答案（代码）：

int match(char *s){
    Stack st; init(&st); int x;
    for(int i=0; s[i]; i++){
        char c = s[i];
        if(c=='('||c=='['||c=='{') push(&st, c);
        else{
            if(pop(&st,&x)==0) return 0;           // 栈空，右括号多
            if((c==')'&&x!='(')||(c==']'&&x!='[')||(c=='}'&&x!='{'))
                return 0;
        }
    }
    return isEmpty(&st);                            // 栈空才匹配
}

12. 后缀表达式求值步骤。

答案：从左扫描：操作数入栈；遇运算符弹出两个（先弹的是右操作数）运算后压回；扫描完栈顶即答案。

9.4.5 算法设计（思路型，写不出代码就写文字得步骤分）

13. 判断无向图是否连通。

答案：从任一顶点 DFS/BFS，统计访问到的顶点数；== n 则连通，否则不连通。

14. 求二叉树高度。

答案（代码）：

int height(Node *t){
    if(!t) return 0;
    int l = height(t->left), r = height(t->right);
    return (l > r ? l : r) + 1;
}

看到树就想递归。