数据结构科目的主编，资深考研培训师

本书针对近几年全国计算机学科专业综合考试大纲的“数据结构”部分进行了深入解读，以一种独创的方式对考试大纲中的知识点进行了讲解，即从考生的视角剖析知识难点；以通俗易懂的语言取代晦涩难懂的专业术语；以成功考生的亲身经历指引复习方向；以风趣幽默的笔触缓解考研压力。考生对书中的知识点讲解有任何疑问都可与作者进行在线互动，解决复习中的疑难点，提高复习效率。
根据计算机专业研究生入学考试形势的变化，书中对大量非统考知识点进行了讲解，使本书所包含的知识点除覆盖统考大纲的内容外，还包括了各自主命题高校所要求的知识点。
本书可作为计算机专业研究生入学考试的复习指导用书（包括统考和非统考），也可作为全国各大高校计算机专业或非计算机专业的学生学习“数据结构”课程的辅导用书。
（编辑邮箱：jinacmp@163.com）

目 录
序
前言
第1章 绪论1
本章概略1
1.1 针对考研数据结构的代码书写规范以及C与C++语言基础1
1.1.1 考研综合应用题中算法设计部分的代码书写规范1
1.1.2 考研中的C与C++语言基础3
1.2 算法的时间复杂度与空间复杂度分析基础12
1.2.1 考研中的算法时间复杂度分析12
1.2.2 例题选讲12
1.2.3 考研中的算法空间复杂度分析14
1.3 数据结构和算法的基本概念14
1.3.1 数据结构的基本概念14
1.3.2 算法的基本概念15
习题16
习题答案17
第2章 线性表20
大纲要求20
考点与要点分析20
核心考点20
基础要点20
知识点讲解20
2.1 线性表的基本概念与实现20
2.2 线性表的结构体定义和基本操作24
2.2.1 线性表的结构体定义24
2.2.2 顺序表的操作26
2.2.3 单链表的操作28
2.2.4 双链表的操作33
2.2.5 循环链表的操作35
2.2.6 逆置问题（408科目重要考点）35
▲真题仿造36
真题仿造答案与解析37
习题+真题精选38
习题答案+真题精选答案42
第3章 栈和队列60
大纲要求60
考点与要点分析60
核心考点60
基础要点60
知识点讲解60
3.1 栈和队列的基本概念60
3.1.1 栈的基本概念60
3.1.2 队列的基本概念61
3.2 栈和队列的存储结构、算法与应用61
3.2.1 本章所涉及的结构体定义61
3.2.2 顺序栈62
3.2.3 链栈64
3.2.4 栈的应用65
3.2.5 顺序队69
3.2.6 链队71
3.2.7 共享栈和双端队列72
3.2.8 队列的配置问题74
3.3 抽象数据类型75
▲真题仿造77
真题仿造答案与解析77
习题+真题精选80
习题答案+真题精选答案85
第4章 串98
知识点讲解98
4.1 串数据类型的定义98
4.1.1 串的定义98
4.1.2 串的存储结构98
4.1.3 串的基本操作99
4.2 串的模式匹配算法102
4.2.1 简单模式匹配算法102
4.2.2 KMP算法103
4.2.3 KMP算法的改进107
习题109
习题答案110
第5章 数组、矩阵与广义表120
知识点讲解120
5.1 数组120
5.2 矩阵的压缩存储121
5.2.1 矩阵121
5.2.2 特殊矩阵和稀疏矩阵122
5.3 广义表128
习题129
习题答案130
第6章 树与二叉树139
大纲要求139
考点与要点分析139
核心考点139
基础要点139
知识点讲解139
6.1 树的基本概念139
6.1.1 树的定义139
6.1.2 树的基本术语140
6.1.3 树的存储结构140
6.2 二叉树141
6.2.1 二叉树的定义141
6.2.2 二叉树的主要性质142
6.2.3 二叉树的存储结构144
6.2.4 二叉树的遍历算法145
6.2.5 二叉树遍历算法的改进153
6.3 树和森林与二叉树的互相转换162
6.3.1 树转换为二叉树162
6.3.2 二叉树转换为树163
6.3.3 森林转换为二叉树164
6.3.4 二叉树转换为森林164
6.3.5 树和森林的遍历164
6.4 树与二叉树的应用166
6.4.1 二叉排序树与平衡二叉树166
6.4.2 赫夫曼树和赫夫曼编码166
6.4.3 并查集及其应用（2022统考大纲新增内容）169
▲真题仿造169
真题仿造答案与解析169
习题+真题精选170
习题答案+真题精选答案176
第7章 图191
大纲要求191
考点与要点分析191
核心考点191
基础要点191
知识点讲解191
7.1 图的基本概念191
7.2 图的存储结构192
7.2.1 邻接矩阵193
7.2.2 邻接表194
7.2.3 邻接多重表195
7.3 图的遍历算法操作196
7.3.1 深度优先搜索遍历196
7.3.2 广度优先搜索遍历197
7.3.3 例题选讲198
7.4 最小（代价）生成树201
7.4.1 普里姆算法和克鲁斯卡尔算法（含2022统考大纲新增内容并查集的讲解）201
7.4.2 例题选讲205
7.5 最短路径206
7.5.1 迪杰斯特拉算法206
7.5.2 弗洛伊德算法212
7.6 拓扑排序215
7.6.1 AOV网215
7.6.2 拓扑排序核心算法215
7.6.3 例题选讲217
7.7 关键路径218
7.7.1 AOE网218
7.7.2 关键路径核心算法218
▲真题仿造221
真题仿造答案与解析221
习题+真题精选223
习题答案+真题精选答案229
第8章 排序243
大纲要求243
考点与要点分析243
核心考点243
基础要点243
知识点讲解244
8.1 排序的基本概念244
8.1.1 排序244
8.1.2 稳定性244
8.1.3 排序算法的分类244
8.2 插入类排序245
8.2.1 直接插入排序245
8.2.2 折半插入排序246
8.2.3 希尔排序247
8.3 交换类排序249
8.3.1 起泡排序249
8.3.2 快速排序250
8.4 选择类排序252
8.4.1 简单选择排序252
8.4.2 堆排序253
8.5 二路归并排序256
8.6 基数排序257
8.7 外部排序261
8.7.1 概念与流程261
8.7.2 置换-选择排序262
8.7.3 最佳归并树263
8.7.4 败者树263
8.7.5 时间与空间复杂度相关问题266
8.8 排序知识点小结266
▲真题仿造267
真题仿造答案与解析268
习题+真题精选269
习题答案+真题精选答案274
第9章 查找285
大纲要求285
考点与要点分析285
核心考点285
基础要点285
知识点讲解285
9.1 查找的基本概念、顺序查找法、折半查找法285
9.1.1 查找的基本概念285
9.1.2 顺序查找法286
9.1.3 折半查找法287
9.1.4 分块查找289
9.2 树形查找 290
9.2.1 二叉排序树290
9.2.2 平衡二叉