王道论坛-2022年数据结构考研复习指导

图书标准信息

• 作者 王道论坛 著
• 出版社 电子工业出版社
• 出版时间 2020-12
• ISBN 9787121402180
• 定价 69.80元

【内容简介】

本书是计算机专业研究生入学考试“数据结构”课程的复习用书，内容包括绪论、线性表、栈和队列、串、树与二叉树、图、查找、排序等。全书严格按照**计算机考研大纲的数据结构部分，对大纲所涉及的知识点进行集中梳理，力求内容精炼、重点突出、深入浅出。本书精选各名校的历年考研真题，并给出详细的解题思路，力求实现讲练结合、灵活掌握、举一反三的功效。通过“书本＋在线”的学习方式和网上答疑方式，读者在使用本书时遇到的任何疑难点，都可以在王道论坛发帖与道友互动。

【作者简介】

王道论坛，一家专注于计算机考研的网站与培训机构，业务包括计算机组成原理、数据结构、计算机网络和操作系统，以及C等语言的培训工作，用户规模较大。

【目录】

目    录
第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  算法效率的度量5
1．2．3  本节试题精选6
1．2．4  答案与解析8
归纳总结10
思维拓展11
第2章  线性表12
2．1  线性表的定义和基本操作12
2．1．1  线性表的定义12
2．1．2  线性表的基本操作13
2．1．3  本节试题精选13
2．1．4  答案与解析13
2．2  线性表的顺序表示14
2．2．1  顺序表的定义14
2．2．2  顺序表上基本操作的实现15
2．2．3  本节试题精选17
2．2．4  答案与解析19
2．3  线性表的链式表示28
2．3．1  单链表的定义28
2．3．2  单链表上基本操作的实现28
2．3．3  双链表32
2．3．4  循环链表33
2．3．5  静态链表34
2．3．6  顺序表和链表的比较35
2．3．7  本节试题精选36
2．3．8  答案与解析41
归纳总结60
思维拓展60
第3章  栈和队列61
3．1  栈61
3．1．1  栈的基本概念61
3．1．2  栈的顺序存储结构62
3．1．3  栈的链式存储结构64
3．1．4  本节试题精选64
3．1．5  答案与解析67
3．2  队列73
3．2．1  队列的基本概念73
3．2．2  队列的顺序存储结构74
3．2．3  队列的链式存储结构76
3．2．4  双端队列77
3．2．5  本节试题精选79
3．2．6  答案与解析81
3．3  栈和队列的应用86
3．3．1  栈在括号匹配中的应用86
3．3．2  栈在表达式求值中的应用87
3．3．3  栈在递归中的应用88
3．3．4  队列在层次遍历中的应用89
3．3．5  队列在计算机系统中的应用89
3．3．6  本节试题精选90
3．3．7  答案与解析92
3．4  特殊矩阵的压缩存储97
3．4．1  数组的定义97
3．4．2  数组的存储结构97
3．4．3  矩阵的压缩存储98
3．4．4  稀疏矩阵100
3．4．5  本节试题精选100
3．4．6  答案与解析101
归纳总结103
思维拓展103
第4章  串104
4．1  串的定义和实现104
4．1．1  串的定义104
4．1．2  串的存储结构105
4．1．3  串的基本操作106
4．2  串的模式匹配106
4．2．1  简单的模式匹配算法106
4．2．2  改进的模式匹配算法DDKMP算法107
4．2．3  KMP算法的进一步优化112
4．2．4  本节试题精选112
4．2．5  答案与解析113
归纳总结117
思维拓展118
第5章  树与二叉树119
5．1  树的基本概念119
5．1．1  树的定义119
5．1．2  基本术语120
5．1．3  树的性质121
5．1．4  本节试题精选121
5．1．5  答案与解析122
5．2  二叉树的概念123
5．2．1  二叉树的定义及其主要特性123
5．2．2  二叉树的存储结构125
5．2．3  本节试题精选126
5．2．4  答案与解析128
5．3  二叉树的遍历和线索二叉树132
5．3．1  二叉树的遍历132
5．3．2  线索二叉树136
5．3．3  本节试题精选139
5．3．4  答案与解析144
5．4  树、森林161
5．4．1  树的存储结构161
5．4．2  树、森林与二叉树的转换163
5．4．3  树和森林的遍历164
*5．4．4  树的应用DD并查集165
5．4．5  本节试题精选166
5．4．6  答案与解析168
5．5  树与二叉树的应用174
5．5．1  二叉排序树（BST）174
5．5．2  平衡二叉树177
5．5．3  哈夫曼树和哈夫曼编码180
5．5．4  本节试题精选182
5．5．5  答案与解析186
归纳总结197
思维拓展198
第6章  图199
6．1  图的基本概念199
6．1．1  图的定义199
6．1．2  本节试题精选202
6．1．3  答案与解析204
6．2  图的存储及基本操作206
6．2．1  邻接矩阵法206
6．2．2  邻接表法207
6．2．3  十字链表209
6．2．4  邻接多重表209
6．2．5  图的基本操作210
6．2．6  本节试题精选211
6．2．7  答案与解析213
6．3  图的遍历216
6．3．1  广度优先搜索216
6．3．2  深度优先搜索218
6．3．3  图的遍历与图的连通性219
6．3．4  本节试题精选220
6．3．5  答案与解析222
6．4  图的应用227
6．4．1  最小生成树227
6．4．2  最短路径229
6．4．3  有向无环图描述表达式232
6．4．4  拓扑排序233
6．4．5  关键路径234
6．4．6  本节试题精选236
6．4．7  答案与解析244
归纳总结256
思维拓展257
第7章  查找258
7．1  查找的基本概念258
7．2  顺序查找和折半查找259
7．2．1  顺序查找259
7．2．2  折半查找261
7．2．3  分块查找262
7．2．4  本节试题精选263
7．2．5  答案与解析266
7．3  B树和B+树271
7．3．1  B树及其基本操作271
7．3．2  B+树的基本概念274
7．3．3  本节试题精选275
7．3．4  答案与解析277
7．4  散列表282
7．4．1  散列表的基本概念282
7．4．2  散列函数的构造方法282
7．4．3  处理冲突的方法283
7．4．4  散列查找及性能分析284
7．4．5  本节试题精选285
7．4．6  答案与解析288
归纳总结293
思维拓展293
第8章  排序294
8．1  排序的基本概念295
8．1．1  排序的定义295
8．1．2  本节试题精选295
8．1．3  答案与解析296
8．2  插入排序296
8．2．1  直接插入排序296
8．2．2  折半插入排序298
8．2．3  希尔排序298
8．2．4  本节试题精选299
8．2．5  答案与解析301
8．3  交换排序303
8．3．1  冒泡排序303
8．3．2  快速排序304
8．3．3  本节试题精选306
8．3．4  答案与解析308
8．4  选择排序314
8．4．1  简单选择排序314
8．4．2  堆排序315
8．4．3  本节试题精选317
8．4．4  答案与解析319
8．5  归并排序和基数排序323
8．5．1  归并排序323
8．5．2  基数排序324
8．5．3  本节试题精选326
8．5．4  答案与解析327
8．6  各种内部排序算法的比较及应用329
8．6．1  内部排序算法的比较329
8．6．2  内部排序算法的应用330
8．6．3  本节试题精选331
8．6．4  答案与解析332
8．7  外部排序336
8．7．1  外部排序的基本概念336
8．7．2  外部排序的方法336
8．7．3  多路平衡归并与败者树337
8．7．4  置换-选择排序（生成初始归并段）338
8．7．5  最佳归并树339
8．7．6  本节试题精选340
8．7．7  答案与解析341
归纳总结344
思维拓展345
参考文献346