天勤计算机考研高分笔记系列 2021版数据结构高分笔记 第9版

408大纲起草者殷人昆力推

配套线上课，作者率辉亲自授课

关注辉解读公众号领取更新补丁

书内扫码得习题讲解视频，多次命中原题

活跃的千人互动答疑群

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

前言
第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 习题答案 真题精选答案 43 第3 章栈和队列 56 大纲要求 56 考点与要点分析 56 核心考点 56 基础要点 56 知识点讲解 56

2021 版数据结构高分笔记

3.1 栈和队列的基本概念 56
3.1.1 栈的基本概念 56
3.1.2 队列的基本概念 57
3.2 栈和队列的存储结构、算法与应用 57
3.2.1 本章所涉及的结构体定义 57
3.2.2 顺序栈 58
3.2.3 链栈 60
3.2.4 栈的应用 61
3.2.5 顺序队 65
3.2.6 链队 67
3.2.7 共享栈和双端队列 69
3.2.8 队列的配置问题 70
3.3 抽象数据类型 71
▲真题仿造 73 真题仿造答案与解析 73 习题 真题精选 76 习题答案 真题精选答案 81 第4 章串 93 知识点讲解 93
4.1 串数据类型的定义 93
4.1.1 串的定义 93
4.1.2 串的存储结构 93
4.1.3 串的基本操作 94
4.2 串的模式匹配算法 97
4.2.1 简单模式匹配算法 97
4.2.2 KMP 算法 98
4.2.3 KMP 算法的改进 102 习题 104 习题答案 105 第5 章数组、矩阵与广义表 115 知识点讲解 115
5.1 数组 115
5.2 矩阵的压缩存储 116
5.2.1 矩阵 116
5.2.2 特殊矩阵和稀疏矩阵 117
5.3 广义表 123 习题 124 习题答案 125 第6 章树与二叉树 134 大纲要求 134 考点与要点分析 134 核心考点 134 基础要点 134 知识点讲解 134

目 录
6.1 树的基本概念 134
6.1.1 树的定义 134
6.1.2 树的基本术语 134
6.1.3 树的存储结构 135
6.2 二叉树 136
6.2.1 二叉树的定义 136
6.2.2 二叉树的主要性质 137
6.2.3 二叉树的存储结构 139
6.2.4 二叉树的遍历算法 139
6.2.5 二叉树遍历算法的改进 148
6.3 树和森林与二叉树的互相转换 157
6.3.1 树转换为二叉树 157
6.3.2 二叉树转换为树 158
6.3.3 森林转换为二叉树 158
6.3.4 二叉树转换为森林 159
6.3.5 树和森林的遍历 159
6.4 树与二叉树的应用 160
6.4.1 二叉排序树与平衡二叉树 160
6.4.2 赫夫曼树和赫夫曼编码 161
▲真题仿造 164
真题仿造答案与解析 164
习题 真题精选 165
习题答案 真题精选答案 170
第7 章图 185
大纲要求 185
考点与要点分析 185
核心考点 185
基础要点 185
知识点讲解 185
7.1 图的基本概念 185
7.2 图的存储结构 186
7.2.1 邻接矩阵 187
7.2.2 邻接表 188
7.2.3 邻接多重表 189
7.3 图的遍历算法操作 190
7.3.1 深度优先搜索遍历 190
7.3.2 广度优先搜索遍历 191
7.3.3 例题选讲 192
7.4 最小（代价）生成树 195
7.4.1 普里姆算法和克鲁斯卡尔算法 195
7.4.2 例题选讲 199
7.5 最短路径 200
7.5.1 迪杰斯特拉算法 200
7.5.2 弗洛伊德算法 206

2021 版数据结构高分笔记

7.6 拓扑排序 209
7.6.1 AOV 网 209
7.6.2 拓扑排序核心算法 209
7.6.3 例题选讲 211
7.7 关键路径 212
7.7.1 AOE 网 212
7.7.2 关键路径核心算法 212
▲真题仿造 215
真题仿造答案与解析 215
习题 真题精选 217
习题答案 真题精选答案 223
第8 章排序 236
大纲要求 236
考点与要点分析 236
核心考点 236
基础要点 236
知识点讲解 237
8.1 排序的基本概念 237
8.1.1 排序 237
8.1.2 稳定性 237
8.1.3 排序算法的分类 237
8.2 插入类排序 238
8.2.1 直接插入排序 238
8.2.2 折半插入排序 239
8.2.3 希尔排序 240
8.3 交换类排序 242
8.3.1 起泡排序 242
8.3.2 快速排序 243
8.4 选择类排序 245
8.4.1 简单选择排序 245
8.4.2 堆排序 246
8.5 二路归并排序 249
8.6 基数排序 250
8.7 外部排序 254
8.7.1 概念与流程 254
8.7.2 置换-选择排序 255
8.7.3 最佳归并树 256
8.7.4 败者树 257
8.7.5 时间与空间复杂度相关问题 259
8.8 排序知识点小结 260
▲真题仿造 261
真题仿造答案与解析 261
习题 真题精选 262
习题答案 真题精选答案 267
第9 章查找 277
大纲要求 277
考点与要点分析 277
核心考点 277
基础要点 277
知识点讲解 277
9.1 查找的基本概念、顺序查找法、折半查找法 277
9.1.1 查找的基本概念 277
9.1.2 顺序查找法 278
9.1.3 折半查找法 279
9.1.4 分块查找 281
9.2 二叉排序树与平衡二叉树 282
9.2.1 二叉排序树 282
9.2.2 平衡二叉树 285
9.3 B-树的基本概念及其基本操作、B 树的基本概念 288
9.3.1 B-树（B 树）的基本概念 288
9.3.2 B-树的基本操作 290
9.3.3 B 树的基本概念 294
9.4 散列表 295
9.4.1 散列表的概念 295
9.4.2 散列表的建立方法以及冲突解决方法 295
9.4.3 散列表的性能分析 299
▲真题仿造 300
真题仿造答案与解析 300
习题 真题精选 301
习题答案 真题精选答案 306
第10 章考研中某些算法的分治法释 319
参考文献 322

高分笔记系列书籍简介

高分笔记系列书籍包括《数据结构高分笔记》《组成原理高分笔记》《操作系统高分笔记》《计算机网络高分笔记》等，是一套针对计算机考研的辅导书。它们在2010 年夏天诞生于一群考生之手，其写作风格突出表现为：以学生的视角剖析知识难点；以通俗易懂的语言取代晦涩难懂的专业术语；以成功考生的亲身经历指引复习方向；以风趣幽默的笔触缓解考研压力。相信高分笔记系列书籍带给考生的将是更高效、更明确、更轻松、更愉快的复习过程。
数据结构高分笔记简介

众所周知，在计算机统考的四门专业课中，最难拿高分的就是数据结构。但是这门课本身的难度并不是考生最大的障碍，真正的障碍在于考生不能独自把握复习方向和考试范围。也许有学生要问，我们不是有大纲吗？照着大纲去复习不就可以了吗？表面上看是这样的，但是当你真正开始复习的时候就会发现，其实大纲只给了考生一个大致范围，有很多地方是模糊的，这些模糊的地方可能就是你纠结的地方。比如大纲里对于栈和队列的考查中有这么一条：“栈和队列的应用。”这个知识点就说得很模糊，因为只要涉及栈和队列的地方，都是其应用的范畴，这时考生该怎么办呢？于是把所有的希望寄托于参考书，希望参考书能帮助他们理解大纲的意图。参考书分为两种：一是课本，二是与课本配套的辅导书。对于课本，考生用得最多的就是严蔚敏老师编写的“严版”《数据结构》。因为这本书的内容非常丰富，如果能把这本书中考试大纲要求的章节理解透彻，参加考研就没有任何问题，但是这个过程是漫长的，除非本科阶段就学得非常好。计算机统考后，专业课四门加上公共课三门，一共是七门，绝大多数考生复习的时间一般也就六个月，而数据结构的复习需要占用多少时间，这点大家都很清楚。要在这么短的时间内掌握“严版”《数据结构》中考纲要求的知识点，基本上是不可能的，这就需要一本辅导书来依照大纲从课本中总结出考纲要求的知识点，才能使得考生在短时间内达到研究生考试的要求。市面上的参考书有两种：一种是四合一的辅导书，另一种是分册的。比如网上流行的《1800 题》及其第2 版，此书中题目极多，并且有很多老式的考研题，有些算法设计题的答案是用Pascal 语言写的。这本书中的题目一般考生全做基本上是不可能的，挑着做又会把时间浪费在选题上。不可否认，这本书确实是一本非常好的题库，但是考生直接拿来用作考研辅导书却不太合适。在这种情况下，就需要有一本优质的完全针对新大纲的辅导书出现，这就是高分笔记产生的原因。
接下来详细介绍一下这本辅导书的写作过程，请看下图：

图中所涉及的书都是大家很熟悉的。当年这些书编者都买了，花了很大心思才从中找出在考研战场上真正有用的东西。比如《1800 题》，里边既有好题，又有废题，相信很多人都希望有人能从中去掉重复的题目，选出大纲要求的题目，并能把解答写得更通俗易懂些，而现在编者所做的工作就是从这1800 道题中选出大纲要求的题目，并且修正部分解答，使其更容易理解。其次是“严版”《数据结构》，此书写得很严谨，语言表述非常专业，但对于基础稍差的学生来说读起来十分费力，要很长时间才能适应这本书的写作风格。如果有一本辅导书能把那些复杂程序的执行过程、拗口的专业术语、令人头大的符号翻译成容易理解的语言，就可以节省考生很多时间，因此，编者所做的事情就是根据自己复习的经验，以及对这本书的理解，把其中考试不需要的内容删掉，把需要的内容改造成一般考生容易接受的形式。对于李春葆老师的《数据结构习题与解析》，也做了类似的处理，并且在这本书中穿插讲解了一些考试大纲中没有明文规定，但是很多算法题目中大量用到的算法设计思想，来帮助大家提高解算法设计题的能力，比如搜索（打印图中两结点之间的所有路径）、分治法（二分法排序、求树的深度等）等算法思想。因此，相信本书会给读者的考研复习带来很大的帮助。
另外，本书配有微信公众号（微信搜索「辉解读」即可找到公众号）来收集读者的反馈，这也是本书不断更新完善的重要途径，即根据考生最需要的内容来作为调整讲解的依据。
自2017 年起，本书作者开始以《高分笔记》系列书籍为教材，开课讲解计算机考研知识点、模拟题以及真题。课程可在前面介绍的微信公众号中找到。
本书特点：
（1）精心挑选出适合考研的习题，并配上通俗易懂的答案，供读者自测和练习。
（2）总结出考研必备知识点，并且帮读者把其中过于专业、过于严谨的表述翻译成通俗易懂的语言。

（3）针对近年数据结构大题的出题风格（比如算法设计题目中的三段式题目：①表述算法思想；②写出算法描述；③计算算法的时间和空间复杂度），设计了独特的真题仿造部分，让读者在复习的过程中逐渐适应不同类型的题目。