2023年数据结构考研复习指导

图书标准信息

• 作者 王道论坛
• 出版社 电子工业出版社
• 出版时间 2021-12
• 版次 1
• ISBN 9787121424366
• 定价 75.00元
• 装帧 其他
• 开本 其他
• 纸张 胶版纸
• 页数 388页
• 字数 0.62千字

【内容简介】

本书是计算机专业研究生入学考试“数据结构”课程的复习用书，内容包括绪论，线性表，栈、队列和数组，串，树与二叉树，图、查找，排序等。全书严格按照计算机考研大纲的数据结构部分，对大纲所涉及的知识点进行集中梳理，力求内容精炼、重点突出、深入浅出。本书精选各名校的历年考研真题，并给出详细的解题思路，力求实现讲练结合、灵活掌握、举一反三的功效。本书可作为考生参加计算机专业研究生入学考试的复习用书，也可作为计算机专业学生学习数据结构课程的辅导用书。

【作者简介】

王道论坛，一家专注于计算机考研的网站与培训机构，业务包括计算机组成原理、数据结构、计算机网络和操作系统，以及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  单链表的定义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  答案与解析42

归纳总结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  答案与解析70

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  栈在递归中的应用93

3.3.4  队列在层次遍历中的应用94

3.3.5  队列在计算机系统中的应用94

3.3.6  本节试题精选95

3.3.7  答案与解析96

3.4  数组和特殊矩阵102

3.4.1  数组的定义102

3.4.2  数组的存储结构103

3.4.3  特殊矩阵的压缩存储103

3.4.4  稀疏矩阵105

3.4.5  本节试题精选106

3.4.6  答案与解析107

归纳总结108

思维拓展109

第4章  串110

*4.1  串的定义和实现110

4.1.1  串的定义110

4.1.2  串的存储结构111

4.1.3  串的基本操作112

4.2  串的模式匹配112

4.2.1  简单的模式匹配算法112

4.2.2  串的模式匹配算法——KMP算法113

4.2.3  KMP算法的进一步优化118

4.2.4  本节试题精选118

4.2.5  答案与解析119

归纳总结123

思维拓展124

第5章  树与二叉树125

5.1  树的基本概念125

5.1.1  树的定义125

5.1.2  基本术语126

5.1.3  树的性质127

5.1.4  本节试题精选127

5.1.5  答案与解析128

5.2  二叉树的概念129

5.2.1  二叉树的定义及其主要特性129

5.2.2  二叉树的存储结构131

5.2.3  本节试题精选132

5.2.4  答案与解析134

5.3  二叉树的遍历和线索二叉树139

5.3.1  二叉树的遍历139

5.3.2  线索二叉树143

5.3.3  本节试题精选146

5.3.4  答案与解析151

5.4  树、森林169

5.4.1  树的存储结构169

5.4.2  树、森林与二叉树的转换171

5.4.3  树和森林的遍历172

5.4.4  本节试题精选173

5.4.5  答案与解析175

5.5  树与二叉树的应用181

5.5.1  哈夫曼树和哈夫曼编码181

5.5.2  并查集183

5.5.3  本节试题精选184

5.5.4  答案与解析186

归纳总结190

思维拓展191

第6章  图192

6.1  图的基本概念192

6.1.1  图的定义192

6.1.2  本节试题精选195

6.1.3  答案与解析197

6.2  图的存储及基本操作199

6.2.1  邻接矩阵法199

6.2.2  邻接表法201

6.2.3  十字链表202

6.2.4  邻接多重表203

6.2.5  图的基本操作203

6.2.6  本节试题精选204

6.2.7  答案与解析207

6.3  图的遍历211

6.3.1  广度优先搜索211

6.3.2  深度优先搜索213

6.3.3  图的遍历与图的连通性214

6.3.4  本节试题精选214

6.3.5  答案与解析217

6.4  图的应用222

6.4.1  小生成树222

6.4.2  短路径225

6.4.3  有向无环图描述表达式228

6.4.4  拓扑排序228

6.4.5  关键路径230

6.4.6  本节试题精选232

6.4.7  答案与解析240

归纳总结254

思维拓展255

第7章  查找256

7.1  查找的基本概念256

7.2  顺序查找和折半查找257

7.2.1  顺序查找257

7.2.2  折半查找259

7.2.3  分块查找260

7.2.4  本节试题精选261

7.2.5  答案与解析264

7.3  树型查找270

7.3.1  二叉排序树（BST）270

7.3.2  平衡二叉树273

7.3.3  红黑树277

7.3.4  本节试题精选282

7.3.5  答案与解析286

7.4  B树和B+树295

7.4.1  B树及其基本操作296

7.4.2  B+树的基本概念299

7.4.3  本节试题精选300

7.4.4  答案与解析302

7.5  散列表307

7.5.1  散列表的基本概念307

7.5.2  散列函数的构造方法307

7.5.3  处理冲突的方法308

7.5.4  散列查找及性能分析309

7.5.5  本节试题精选310

7.5.6  答案与解析313

归纳总结318

思维拓展319

第8章  排序320

8.1  排序的基本概念321

8.1.1  排序的定义321

8.1.2  本节试题精选321

8.1.3  答案与解析322

8.2  插入排序322

8.2.1  直接插入排序322

8.2.2  折半插入排序324

8.2.3  希尔排序324

8.2.4  本节试题精选326

8.2.5  答案与解析327

8.3  交换排序330

8.3.1  冒泡排序330

8.3.2  快速排序331

8.3.3  本节试题精选333

8.3.4  答案与解析335

8.4  选择排序341

8.4.1  简单选择排序341

8.4.2  堆排序342

8.4.3  本节试题精选344

8.4.4  答案与解析346

8.5  归并排序和基数排序350

8.5.1  归并排序350

8.5.2  基数排序352

8.5.3  本节试题精选353

8.5.4  答案与解析355

8.6  各种内部排序算法的比较及应用357

8.6.1  内部排序算法的比较357

8.6.2  内部排序算法的应用358

8.6.3  本节试题精选359

8.6.4  答案与解析361

8.7  外部排序365

8.7.1  外部排序的基本概念365

8.7.2  外部排序的方法365

8.7.3  多路平衡归并与败者树366

8.7.4  置换-选择排序（生成初始归并段）367

8.7.5  归并树368

8.7.6  本节试题精选369

8.7.7  答案与解析370

归纳总结373

思维拓展374

参考文献375