2021管理类联考·老吕数学要点精编（第6版）

图书标准信息

• 作者 吕建刚 著
• 出版社 北京理工大学出版社
• 出版时间 2020-01
• ISBN 9787568249874
• 定价 89.80元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸

【内容简介】

本书是"数据结构”考研课程的复习指导书，全书严格按照*新计算机统考大纲的数据结构部分，对大纲所涉及的知识点进行集中梳理，力求内容精炼、重点突出。本书精选名校历年考研真题，并给出详细的解题思路。图书采用"书本＋在线”的学习方式和网上答疑方式，方便读者互动。

【作者简介】

王道论坛专注于计算机专业学生考研和就业的社区，由国内名校计算机研究生共同创办，致力于给报考计算机专业硕士研究生的学生提供帮助和指导。主要作者赵霖，本科毕业于中南大学，研究生毕业于哈尔滨工业大学，现为王道论坛主要负责人，曾出版图书多种。王道论坛http://www.cskaoyan.com/，专营计算机考研与培训。

【目录】

目    录
第1章  绪论1
1．1  数据结构的基本概念1
1．1．1  基本概念和术语1
1．1．2  数据结构三要素2
1．1．3  本节试题精选3
1．1．4  答案与解析4
1．2  算法和算法评价5
1．2．1  算法的基本概念5
1．2．2  算法效率的度量6
1．2．3  本节试题精选7
1．2．4  答案与解析9
归纳总结11
思维拓展12
第2章  线性表13
2．1  线性表的定义和基本操作13
2．1．1  线性表的定义13
2．1．2  线性表的基本操作14
2．1．3  本节试题精选14
2．1．4  答案与解析14
2．2  线性表的顺序表示15
2．2．1  顺序表的定义15
2．2．2  顺序表上基本操作的实现16
2．2．3  本节试题精选17
2．2．4  答案与解析21
2．3  线性表的链式表示29
2．3．1  单链表的定义29
2．3．2  单链表上基本操作的实现29
2．3．3  双链表33
2．3．4  循环链表34
2．3．5  静态链表35
2．3．6  顺序表和链表的比较36
2．3．7  本节试题精选37
2．3．8  答案与解析44
归纳总结63
思维拓展63
第3章  栈和队列64
3．1  栈64
3．1．1  栈的基本概念64
3．1．2  栈的顺序存储结构65
3．1．3  栈的链式存储结构67
3．1．4  本节试题精选67
3．1．5  答案与解析71
3．2  队列77
3．2．1  队列的基本概念77
3．2．2  队列的顺序存储结构78
3．2．3  队列的链式存储结构80
3．2．4  双端队列81
3．2．5  本节试题精选83
3．2．6  答案与解析86
3．3  栈和队列的应用91
3．3．1  栈在括号匹配中的应用91
3．3．2  栈在表达式求值中的应用92
3．3．3  栈在递归中的应用92
3．3．4  队列在层次遍历中的应用93
3．3．5  队列在计算机系统中的应用94
3．3．6  本节试题精选94
3．3．7  答案与解析97
3．4  特殊矩阵的压缩存储102
3．4．1  数组的定义102
3．4．2  数组的存储结构102
3．4．3  矩阵的压缩存储103
3．4．4  稀疏矩阵105
3．4．5  本节试题精选105
3．4．6  答案与解析106
归纳总结108
思维拓展108
第4章  串109
4．1  串的定义和实现109
4．1．1  串的定义109
4．1．2  串的存储结构110
4．1．3  串的基本操作111
4．2  串的模式匹配111
4．2．1  简单的模式匹配算法111
4．2．2  改进的模式匹配算法――KMP算法112
4．2．3  KMP算法的进一步优化117
4．2．4  本节试题精选118
4．2．5  答案与解析119
归纳总结123
思维拓展123
第5章  树与二叉树124
5．1  树的基本概念124
5．1．1  树的定义124
5．1．2  基本术语125
5．1．3  树的性质126
5．1．4  本节试题精选126
5．1．5  答案与解析127
5．2  二叉树的概念128
5．2．1  二叉树的定义及其主要特性128
5．2．2  二叉树的存储结构130
5．2．3  本节试题精选131
5．2．4  答案与解析134
5．3  二叉树的遍历和线索二叉树138
5．3．1  二叉树的遍历138
5．3．2  线索二叉树142
5．3．3  本节试题精选145
5．3．4  答案与解析152
5．4  树、森林170
5．4．1  树的存储结构170
5．4．2  树、森林与二叉树的转换171
5．4．3  树和森林的遍历172
5．4．4  树的应用――并查集173
5．4．5  本节试题精选174
5．4．6  答案与解析177
5．5  树与二叉树的应用182
5．5．1  二叉排序树（BST）182
5．5．2  平衡二叉树186
5．5．3  哈夫曼树和哈夫曼编码189
5．5．4  本节试题精选191
5．5．5  答案与解析196
归纳总结206
思维拓展207
第6章  图208
6．1  图的基本概念208
6．1．1  图的定义208
6．1．2  本节试题精选211
6．1．3  答案与解析214
6．2  图的存储及基本操作216
6．2．1  邻接矩阵法216
6．2．2  邻接表法217
6．2．3  十字链表218
6．2．4  邻接多重表219
6．2．5  图的基本操作220
6．2．6  本节试题精选220
6．2．7  答案与解析223
6．3  图的遍历226
6．3．1  广度优先搜索226
6．3．2  深度优先搜索228
6．3．3  图的遍历与图的连通性229
6．3．4  本节试题精选230
6．3．5  答案与解析233
6．4  图的应用238
6．4．1  最小生成树238
6．4．2  最短路径240
6．4．3  有向无环图描述表达式243
6．4．4  拓扑排序244
6．4．5  关键路径245
6．4．6  本节试题精选247
6．4．7  答案与解析256
归纳总结268
思维拓展269
第7章  查找270
7．1  查找的基本概念270
7．2  顺序查找和折半查找271
7．2．1  顺序查找271
7．2．2  折半查找273
7．2．3  分块查找274
7．2．4  本节试题精选275
7．2．5  答案与解析279
7．3  B树和B+树284
7．3．1  B树及其基本操作284
7．3．2  B+树的基本概念287
7．3．3  本节试题精选288
7．3．4  答案与解析291
7．4  散列表295
7．4．1  散列表的基本概念295
7．4．2  散列函数的构造方法295
7．4．3  处理冲突的方法296
7．4．4  散列查找及性能分析297
7．4．5  本节试题精选298
7．4．6  答案与解析302
归纳总结307
思维拓展307
第8章  排序308
8．1  排序的基本概念308
8．1．1  排序的定义308
8．1．2  本节试题精选309
8．1．3  答案与解析310
8．2  插入排序310
8．2．1  直接插入排序310
8．2．2  折半插入排序312
8．2．3  希尔排序312
8．2．4  本节试题精选313
8．2．5  答案与解析316
8．3  交换排序318
8．3．1  冒泡排序318
8．3．2  快速排序319
8．3．3  本节试题精选321
8．3．4  答案与解析324
8．4  选择排序330
8．4．1  简单选择排序330
8．4．2  堆排序330
8．4．3  本节试题精选333
8．4．4  答案与解析335
8．5  归并排序和基数排序339
8．5．1  归并排序339
8．5．2  基数排序340
8．5．3  本节试题精选342
8．5．4  答案与解析344
8．6  各种内部排序算法的比较及应用346
8．6．1  内部排序算法的比较346
8．6．2  内部排序算法的应用347
8．6．3  本节试题精选348
8．6．4  答案与解析350
8．7  外部排序353
8．7．1  外部排序的基本概念353
8．7．2  外部排序的方法353
8．7．3  多路平衡归并与败者树354
8．7．4  置换-选择排序（生成初始归并段）355
8．7．5  最佳归并树356
8．7．6  本节试题精选357
8．7．7  答案与解析359
归纳总结361
思维拓展362
参考文献363