数据结构（DS）

一、知识框架

数据结构主要研究数据的逻辑结构、存储结构以及在这些结构上定义的运算。408 中通常包括线性表、栈和队列、串、树、图、查找与排序。

二、算法复杂度

设基本操作执行次数为输入规模 n 的函数 T(n)：

• 时间复杂度关注 T(n) 的数量级，忽略低阶项和常数系数。
• 空间复杂度关注算法运行时额外使用的空间。
• 常见数量级：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。
• 递归算法的空间复杂度通常需要考虑递归调用栈。

三、栈与后缀表达式

我的记录

1

//后缀表达式，运算符等级相同时，从左到右的顺序

补充：中缀表达式转后缀表达式

1. 遇到操作数，直接输出。
2. 遇到左括号，将其压入运算符栈。
3. 遇到右括号，持续弹出并输出运算符，直到遇到左括号；左右括号都不输出。
4. 对通常的左结合运算符，当栈顶运算符优先级大于或等于当前运算符时，先弹出栈顶运算符。
5. 扫描结束后，将栈中剩余运算符依次弹出。

后缀表达式求值时，从左向右扫描：操作数入栈；遇到二元运算符时，先弹出的数是右操作数，后弹出的数是左操作数。

+、-、*、/ 通常是左结合；若题目引入幂运算等右结合运算符，同优先级时的出栈规则需要单独处理。

四、快速排序

4.1 我的代码

我的记录（原样保留）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//枚举法，快排法。
/// @brief 升序快排
/// @param A 
/// @param L 
/// @param R 
void Qsort(int A[],int L, int R)
{
    if(L>=R)
    return;
    int i = L,j = R;
    int pivot = A[L];
    while(L<R)
    {
        while(i<j && A[j] >= pivot)
        j--;
        while(i<j && A[i] <= pivot)
        i++;
        if(i<j)
        swap(A[i],A[j]);
    }
    swap(A[L],A[i]);
    Qsort(A,L,i-1);
    Qsort(A,i+1,R);
}

4.2 算法思想

快速排序使用分治思想：选择一个枢轴 pivot，通过一趟划分让枢轴左侧元素不大于它、右侧元素不小于它，再递归排序左右两个子序列。

4.3 参考实现

下面是单独补充的可编译参考实现，不替换上面的个人代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

static void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void QuickSort(int A[], int L, int R)
{
    if (L >= R)
        return;

    int i = L;
    int j = R;
    int pivot = A[L];

    while (i < j)
    {
        while (i < j && A[j] >= pivot)
            --j;
        while (i < j && A[i] <= pivot)
            ++i;

        if (i < j)
            Swap(&A[i], &A[j]);
    }

    Swap(&A[L], &A[i]);
    QuickSort(A, L, i - 1);
    QuickSort(A, i + 1, R);
}

原代码旁注（不修改原代码）

• C 语言不能在同一翻译单元中重复定义四个签名完全相同的 Qsort。
• 外层划分循环通常应判断 i < j；如果写 L < R 且循环中不修改 L、R，可能无法退出。
• 第二个版本中的右指针使用了 j++，方向需要检查。
• C 标准库没有通用的 swap(A[i], A[j])，需要自行定义函数或宏。
• 使用严格的 <、> 时，如果两端都遇到等于枢轴的元素，需要保证指针仍能移动，否则可能死循环。

五、查找与排序速查

折半查找

• 仅适用于有序的顺序表。
• 判定树是一棵平衡二叉树，查找长度不超过 ⌊log₂n⌋+1。
• 链表不支持高效随机访问，因此不适合直接使用折半查找。

散列查找

装填因子 α = 表中记录数 / 散列表长度。装填因子越大，发生冲突的概率通常越高。常见冲突处理方法包括开放定址法和拉链法。

六、线性表

补充内容：线性表是具有相同数据类型的有限序列。除首尾元素外，每个元素有唯一直接前驱和直接后继。

6.1 顺序表

顺序表用连续存储单元依次存放元素，支持随机访问。已知下标访问为 O(1)；在第 i 个位置插入或删除需要移动后续元素，平均为 O(n)。

• 静态分配：数组容量固定，空间用尽后无法继续扩展。
• 动态分配：通过重新申请更大空间并复制元素扩容，但逻辑结构仍是顺序表。
• 按值查找：无序表为 O(n)；有序表可用折半查找达到 O(log n)。
• 优点：存储密度高、随机访问快、Cache 局部性好。
• 缺点：插删移动元素，连续大空间不易分配。

6.2 链表

链表不支持随机访问，定位第 i 个结点通常为 O(n)。若已知待删结点的前驱，则单链表删除为 O(1)；仅给出待删结点时，尾结点是特殊情况。头结点不存放有效数据，作用是统一空表和非空表的边界操作；头指针指向链表第一个结点或头结点。

常考操作：头插法建立的链表与输入顺序相反；尾插法保持输入顺序；寻找倒数第 k 个结点可用快慢指针；判断环及寻找环入口可用 Floyd 算法；合并有序链表可用双指针。

七、栈、队列、数组与串

7.1 栈与队列

栈是只允许在一端插入和删除的线性表，遵循后进先出；队列在队尾插入、队头删除，遵循先进先出。栈常用于递归、括号匹配、表达式求值和 DFS；队列常用于层次遍历、BFS、缓冲和资源调度。

循环队列设数组长度为 MaxSize，常用“牺牲一个单元”的判定：

1
2
3

队空：front == rear
队满：(rear + 1) % MaxSize == front
队列长度：(rear - front + MaxSize) % MaxSize

若另设元素个数 size 或标志位，则可以使用全部数组单元。双端队列允许两端插入删除；输入受限或输出受限双端队列会限制可产生的序列。

7.2 多维数组与特殊矩阵

二维数组按行优先时，A[i][j] 前面有 i × 列数 + j 个元素（下标从 0 开始）；按列优先则为 j × 行数 + i。地址还应乘每个元素所占字节数。

• 对称矩阵：只存上三角或下三角，共 n(n+1)/2 个元素。
• 三角矩阵：除三角区域外元素为同一常量，可压缩存储。
• 三对角矩阵：非零元素满足 |i-j|≤1，共约 3n-2 个。
• 稀疏矩阵：可使用三元组 (行, 列, 值) 或十字链表。

7.3 串与 KMP

朴素模式匹配最坏时间复杂度为 O(nm)。KMP 在失配时利用模式串自身前后缀信息移动模式串，主串指针不回退，匹配复杂度为 O(n+m)。

next 数组的具体数值受教材定义和下标起点影响，但本质都是：失配后把模式串回退到“已匹配部分的最长相等真前缀与真后缀”对应位置。nextval 在当前字符与回退后字符相同时继续回退，以减少无效比较。做题必须先确认题目采用的 next[0]、next[1] 定义。

八、树与二叉树

8.1 基本性质

树中结点数等于所有结点度数之和加 1。度为 m 的树与 m 叉树不同：前者至少有一个结点度为 m，后者每个结点至多有 m 个孩子。

二叉树常用性质：

1
2
3
4

第 i 层至多有 2^(i-1) 个结点（根为第 1 层）
高度为 h 的二叉树至多有 2^h - 1 个结点
非空二叉树中 n0 = n2 + 1
含 n 个结点的完全二叉树高度为 floor(log2 n) + 1

完全二叉树顺序编号从 1 开始时：结点 i 的双亲为 floor(i/2)；左孩子为 2i；右孩子为 2i+1，存在性需与 n 比较。

8.2 存储与遍历

顺序存储适合完全二叉树；链式存储的二叉链表含左右孩子指针。含 n 个结点的二叉链表共有 n+1 个空指针域。

仅由先序和后序通常不能唯一确定二叉树；“先序+中序”或“后序+中序”在结点值互异时可唯一确定。递归遍历时间为 O(n)，辅助空间最坏为树高 O(h)。

8.3 线索二叉树

利用空指针域保存遍历序列中的前驱和后继，并用标志位区分孩子指针与线索。中序线索树中，若结点无右孩子，其右线索指向中序后继；若有右孩子，其中序后继是右子树最左结点。线索化仍需要按相应次序遍历。

8.4 树、森林与二叉树转换

“左孩子—右兄弟”表示法：结点左指针指向第一个孩子，右指针指向下一个兄弟。森林转二叉树后，各棵树的根通过右指针相连。对应遍历关系：树的先根遍历对应二叉树先序；树的后根遍历对应二叉树中序；森林的先序和中序也分别对应转换后二叉树的先序和中序。

8.5 Huffman 树

带权路径长度 WPL = Σ(w_i × l_i)。每次选取权值最小的两棵树合并可得到 Huffman 树，其 WPL 最小。若初始有 n 个叶结点，最终树有 n-1 个度为 2 的结点，总结点数为 2n-1。Huffman 编码是前缀编码，任一码字都不是另一码字的前缀，但编码形态不唯一，WPL 相同。

8.6 BST、AVL 与红黑树

二叉排序树（BST）满足左子树关键字小于根、右子树关键字大于根（重复关键字规则依题设）。中序遍历递增。查找、插入、删除平均可达 O(log n)，退化时为 O(n)。删除有两个孩子的结点时，可用中序前驱或后继替换。

AVL 树任一结点左右子树高度差绝对值不超过 1。插入后从插入点向上找第一个失衡结点，按 LL、RR、LR、RL 旋转；查找和更新均为 O(log n)。

红黑树满足根和空叶为黑、红结点孩子为黑、从任一结点到其叶结点的路径包含相同数目的黑结点，因此最长路径不超过最短路径的 2 倍，操作为 O(log n)。408 更重视性质、插入调整思想及其与 AVL 的对比。

8.7 B 树与 B+ 树

m 阶 B 树中每个结点至多 m 棵子树、至多 m-1 个关键字；除根外非叶结点至少有 ceil(m/2) 棵子树。所有叶结点在同一层。关键字及其记录可分布在各层结点，查找可能在非叶结点成功。

B+ 树中非叶结点只保存索引，记录集中在叶结点；叶结点按关键字有序链接，适合范围查询。内部结点中的关键字可能在叶结点重复出现。关于最少关键字数应按题目给出的 B+ 树定义计算。

九、图

9.1 基本概念与存储

无向图所有顶点度数之和为 2|E|；有向图入度之和等于出度之和，均为 |E|。连通图、强连通图、连通分量、强连通分量要区分。极大连通子图是连通分量；极小连通子图常指保持连通所需边数最少的生成树。

无向图邻接矩阵对称；邻接表中每条无向边通常出现两次。图的遍历序列通常不唯一，取决于邻接点存储次序。

9.2 BFS 与 DFS

BFS 使用队列，可求无权图单源最短路径；邻接表时间为 O(V+E)，邻接矩阵为 O(V²)。DFS 使用递归或栈，适合求连通性、拓扑相关问题；复杂度同样取决于存储结构。遍历非连通图需要对每个未访问顶点重新启动遍历，形成 BFS/DFS 森林。

9.3 最小生成树

最小生成树适用于连通无向带权图，含 V-1 条边且无环。边权互异时 MST 唯一；边权有重复时也可能唯一。

• Prim：从一个顶点集合出发，每次加入连接集合内外的最小边；朴素实现适合稠密图。
• Kruskal：按边权递增选择不构成环的边，常用并查集判环；适合稀疏图。

割性质：跨越某个割的唯一最轻边一定属于 MST。MST 保证总权值最小，但不保证任意两点路径最短。

9.4 最短路径

408 核心通常是 Dijkstra 与 Floyd。Dijkstra 一旦确定顶点最短距离便不再修改；Floyd 递推为 D^(k)[i][j] = min(D^(k-1)[i][j], D^(k-1)[i][k]+D^(k-1)[k][j])。

9.5 DAG、拓扑排序与关键路径

有向无环图可进行拓扑排序。每次选择入度为 0 的顶点输出并删除其出边；若不能输出全部顶点，则图中有环。一个 DAG 可有多个拓扑序；拓扑序唯一不等价于图的传递约简唯一等其他结论。

AOE 网中顶点表示事件、边表示活动。源点到汇点的最长路径长度是工程最短完成时间。活动 a_i=<v_j,v_k>：

1
2
3

最早开始 e(i) = ve(j)
最迟开始 l(i) = vl(k) - weight(j,k)
时间余量 d(i) = l(i) - e(i)

余量为 0 的活动是关键活动。关键路径可能不唯一；缩短某一条关键活动不一定缩短总工期，因为还可能存在其他关键路径。

十、查找

10.1 线性与折半查找

顺序查找适合顺序表和链表，可设置哨兵减少边界判断。折半查找要求有序且支持随机访问，判定树是二叉排序树，查找长度不超过 floor(log2 n)+1。折半查找不适合链表。

分块查找把索引表有序、块内元素可无序组织；先查索引再在块内顺序查找，兼顾动态性与效率。

10.2 散列表

装填因子 α = 表中记录数 / 散列表长度，决定冲突概率和平均查找长度的重要程度通常高于记录总数。常见散列函数有直接定址、除留余数、数字分析、平方取中。

冲突处理：

• 开放定址：线性探测、平方探测、双散列；删除通常使用删除标记，不能直接置空。
• 拉链法：同义词存入链表，装填因子可超过 1。

线性探测易产生一次聚集；平方探测可缓解一次聚集，但探测到所有位置需满足相应表长条件。查找失败时也要沿相同探测序列直到遇到真正空单元或遍历完规定范围。

十一、内部排序

11.1 核心概念

稳定性指关键字相等元素排序后相对次序不变，与算法正确性无关。内部排序数据全部在内存；外部排序因数据量大需在内外存之间交换。

折半插入只减少关键字比较次数，元素移动次数仍是 O(n²)。简单选择排序比较次数与初始序列无关。冒泡和快速排序属于交换排序。

11.2 堆排序与归并排序

大根堆满足双亲不小于孩子，可用于升序堆排序：建立大根堆，反复把堆顶与末尾交换并向下调整。建堆可从最后一个非叶结点开始，整体为 O(n)；每次调整为 O(log n)。

2 路归并把相邻有序段合并。趟数为 ceil(log2 n)，每趟时间 O(n)。归并排序适合链表和外部排序；数组实现通常需要 O(n) 辅助空间。

十二、外部排序

外部排序主要代价是磁盘 I/O。基本过程：生成若干初始归并段，再进行多路归并。减少归并趟数可显著减少读写次数。

1

归并趟数约为 ceil(log_k r)

其中 r 为初始归并段数，k 为归并路数。增加归并路数会增加内部选择最小记录的比较，可用败者树把选择代价降为 O(log k)。置换—选择排序可生成平均长度约为内存工作区两倍的初始归并段；最佳归并树用 Huffman 思想安排长度不等的归并段，必要时补充长度为 0 的虚段。

十二-A、补充专题：压缩存储、并查集与排序

12-A.1 特殊矩阵下标换算

设每个元素占 w 字节，压缩数组首地址为 LOC。求出一维下标 k 后，元素地址为 LOC + k × w。

• 对称矩阵按下三角逐行存储：
  • 若 i ≥ j，k = i(i+1)/2 + j；
  • 若 i < j，利用 A[i][j] = A[j][i]，故 k = j(j+1)/2 + i。
• 下三角矩阵：三角区内 k = i(i+1)/2 + j；三角区外的相同常量可单独放在 k = n(n+1)/2。
• 上三角矩阵按行存储：第 i 行之前已有 i(2n-i+1)/2 个元素，因此 k = i(2n-i+1)/2 + (j-i)，适用于 i ≤ j。
• 三对角矩阵按行存储：仅保存 |i-j|≤1 的元素，一维下标为 k = 2i + j，总元素数为 3n-2。

12-A.2 并查集

并查集维护若干互不相交集合，核心操作是 Find 和 Union，常用于 Kruskal 判环、连通分量和等价类问题。

1
2
3
4
5
6
7
8
9
10
11
12
13

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);   // 路径压缩
    return parent[x];
}

void unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;                  // 按大小合并
    size[ra] += size[rb];
}

只做普通合并时树可能退化为链。路径压缩与按秩/按大小合并同时使用后，m 次操作的总复杂度为 O(m α(n))，其中 α(n) 为反 Ackermann 函数，在实际规模下可视为近似常数。

12-A.3 计数排序

计数排序适用于关键字为较小整数区间 [min,max] 的情况。令 r=max-min+1：先统计每个值出现次数；若要求稳定排序，再求前缀和并从右向左扫描原数组，把元素放入输出数组。

• 时间复杂度：O(n+r)；
• 空间复杂度：O(n+r)（稳定输出版本）；
• 稳定性：按前缀和定位且逆序扫描时稳定；
• 局限：关键字范围远大于数据规模时空间浪费严重，它不是基于比较的排序。

12-A.4 置换—选择与最佳归并树

置换—选择排序维护内存工作区：每次输出当前可用记录中的最小者；新读入记录若不小于刚输出的关键字，可继续进入当前归并段，否则被冻结到下一段。初始归并段长度不固定，随机数据下平均约为工作区容量的两倍，但这不是绝对保证。

长度不等的归并段应按 Huffman 思想构造最佳归并树，使带权路径长度最小。进行 k 路归并时，为形成严格的 k 叉树，虚段数量为：

1

u = ((k - 1) - (r - 1) mod (k - 1)) mod (k - 1)

把 u 个长度为 0 的虚段与真实归并段一起构树。虚段必须作为最小权值参与，不能随意补在树的高层。

十三、应试导航与考点分级

13.1 算法题统一模板

1. 明确逻辑结构、存储结构、输入和输出。
2. 写出核心不变量，例如“p 之前均已处理”。
3. 单独检查空结构、单结点、首尾结点、重复关键字和越界。
4. 给出时间复杂度与额外空间复杂度，不能只写大致结论。
5. 用最小样例、一般样例和边界样例各验证一次。

手写清单：单链表逆置、区间删除、合并有序表、倒数第 k 个结点、树高/结点数、平衡判断、最近公共祖先、BFS、DFS。

13.2 高频计算题模板

• Huffman/WPL：反复合并最小的两个权值；WPL=Σ(叶权值×路径长度)；只有叶结点计权。
• 折半查找：先按题设的中点取法画判定树，再分成功与失败分别计算 ASL。
• 散列表：依次插入，严格按冲突处理规则探测；成功与失败 ASL 的比较次数口径不同。
• 图算法：每一轮记录集合、候选边/距离、前驱，不能只写最终结果。
• 外部排序：先求初始归并段数 r，再求 ⌈log_k r⌉；使用最佳归并树时按 Huffman 思想并按需要补零权虚段。

13.3 快速排序勘误与可背版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

static void quick_sort(int A[], int left, int right) {
    if (left >= right) return;
    int i = left, j = right;
    int pivot = A[left];
    while (i < j) {
        while (i < j && A[j] >= pivot) --j;
        while (i < j && A[i] <= pivot) ++i;
        if (i < j) {
            int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
        }
    }
    A[left] = A[i];
    A[i] = pivot;
    quick_sort(A, left, i - 1);
    quick_sort(A, i + 1, right);
}

• 平均时间 O(n log n)，最坏时间 O(n²)；平均递归栈 O(log n)，最坏 O(n)。
• 快速排序通常不稳定。枢轴选择影响划分平衡程度，但不改变其不稳定性。

13.4 真题与错题登记

1
2
3
4
5
6
7

编号：DS-章节-序号
来源/年份/题号：
题型：选择 / 算法 / 综合
错误原因：概念 / 边界 / 模拟 / 复杂度 / 编码
正确步骤：
一句话结论：
复习日期：

十四、2009—2025 真题融合复习地图

本节把历年真题的典型命题方式融入对应知识点。下列“高频/中频”表示复习优先级，不冒充尚未逐题核验完成的精确次数；具体年份、题号和答案只在核对原卷与解析后登记。

14.1 线性表、栈、队列与数组

高频 线性表：顺序表下标换算、链表指针修改、插入删除复杂度、双链表与循环链表边界。

高频 栈与队列：入栈出栈序列、循环队列判空判满、共享栈、递归与栈、表达式求值。

真题化检查：

1. 循环队列必须先确认是否牺牲一个存储单元；
2. 链表算法写出空表、首结点、尾结点和只有一个结点的情况；
3. 后缀表达式从左向右扫描，遇到运算符时先弹出的通常是右操作数。

14.2 树、二叉树与森林

高频 遍历序列、线索二叉树、树/森林与二叉树转换、哈夫曼编码、二叉排序树、AVL 树。

统一解题链：结点关系 → 遍历规则 → 是否唯一确定 → 高度/路径长度 → 存储结构。哈夫曼编码只保证前缀无歧义和带权路径长度最小，不保证编码唯一。

14.3 图

高频 BFS/DFS、最小生成树、最短路径、拓扑排序、关键路径与存储结构。

• Dijkstra 要求边权非负；Floyd 可处理负边，但不能处理需要定义最短路的负环。
• Prim 更关注顶点到当前生成树的最小代价；Kruskal 按边权排序并用并查集判环。
• AOV 网拓扑序不唯一；AOE 网关键活动由最早、最迟发生时间共同确定。

14.4 查找与排序

高频 折半查找判定树、散列表、B/B+ 树、排序过程、稳定性与复杂度。

14.5 算法综合题作答模板

1
2
3
4
5

1. 说明核心思想与所用数据结构；
2. 写清输入、输出和边界条件；
3. 给出伪代码/C代码；
4. 证明或解释正确性；
5. 分析时间复杂度与空间复杂度。

14.6 经核验真题登记表

历年真题跳转

数据结构在统考卷中通常对应 第 1—11、41—42 题。以下链接可直接进入各年试卷的本科目区域：

• 2009 年数据结构真题

• 2010 年数据结构真题

• 2011 年数据结构真题

• 2012 年数据结构真题

• 2013 年数据结构真题

• 2014 年数据结构真题

• 2015 年数据结构真题

• 2016 年数据结构真题

• 2017 年数据结构真题

• 2018 年数据结构真题

• 2019 年数据结构真题

• 2020 年数据结构真题

• 2021 年数据结构真题

• 2022 年数据结构真题

• 2023 年数据结构真题

• 2024 年数据结构真题

• 2025 年数据结构真题

• 查看 408 历年真题总索引