2025王道考研 数据结构考研复习指导

图书标准信息

• 作者 王道论坛
• 出版社 电子工业出版社
• 出版时间 2024-01
• 版次 1
• ISBN 9787121466595
• 定价 78.00元
• 装帧 其他
• 开本 其他
• 纸张 胶版纸
• 页数 420页
• 字数 739千字

【内容简介】

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

【作者简介】

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

【目录】

目   录

第1章  绪论1

1.1  数据结构的基本概念1

1.1.1  基本概念和术语1

1.1.2  数据结构三要素2

1.1.3  本节试题精选3

1.1.4  答案与解析4

1.2  算法和算法评价4

1.2.1  算法的基本概念4

1.2.2  算法效率的度量5

1.2.3  本节试题精选6

1.2.4  答案与解析8

归纳总结11

思维拓展11

第2章  线性表12

2.1  线性表的定义和基本操作12

2.1.1  线性表的定义12

2.1.2  线性表的基本操作13

2.1.3  本节试题精选13

2.1.4  答案与解析14

2.2  线性表的顺序表示14

2.2.1  顺序表的定义14

2.2.2  顺序表上基本操作的实现15

2.2.3  本节试题精选18

2.2.4  答案与解析20

2.3  线性表的链式表示30

2.3.1  单链表的定义30

2.3.2  单链表上基本操作的实现31

2.3.3  双链表35

2.3.4  循环链表37

2.3.5  静态链表37

2.3.6  顺序表和链表的比较38

2.3.7  本节试题精选39

2.3.8  答案与解析45

归纳总结62

思维拓展63

第3章  栈、队列和数组64

3.1  栈64

3.1.1  栈的基本概念64

3.1.2  栈的顺序存储结构65

3.1.3  栈的链式存储结构68

3.1.4  本节试题精选68

3.1.5  答案与解析71

3.2  队列78

3.2.1  队列的基本概念78

3.2.2  队列的顺序存储结构78

3.2.3  队列的链式存储结构81

3.2.4  双端队列82

3.2.5  本节试题精选84

3.2.6  答案与解析87

3.3  栈和队列的应用92

3.3.1  栈在括号匹配中的应用92

3.3.2  栈在表达式求值中的应用93

3.3.3  栈在递归中的应用95

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

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

3.3.6  本节试题精选97

3.3.7  答案与解析100

3.4  数组和特殊矩阵104

3.4.1  数组的定义104

3.4.2  数组的存储结构104

3.4.3  特殊矩阵的压缩存储105

3.4.4  稀疏矩阵107

3.4.5  本节试题精选108

3.4.6  答案与解析109

归纳总结111

思维拓展112

第4章  串113

*4.1  串的定义和实现113

4.1.1  串的定义113

4.1.2  串的存储结构114

4.1.3  串的基本操作115

4.2  串的模式匹配115

4.2.1  简单的模式匹配算法115

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

4.2.3  KMP算法的进一步优化121

4.2.4  本节试题精选122

4.2.5  答案与解析123

归纳总结127

思维拓展127

第5章  树与二叉树128

5.1  树的基本概念128

5.1.1  树的定义128

5.1.2  基本术语129

5.1.3  树的性质130

5.1.4  本节试题精选131

5.1.5  答案与解析131

5.2  二叉树的概念134

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

5.2.2  二叉树的存储结构136

5.2.3  本节试题精选137

5.2.4  答案与解析140

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

5.3.1  二叉树的遍历145

5.3.2  线索二叉树151

5.3.3  本节试题精选154

5.3.4  答案与解析160

5.4  树、森林179

5.4.1  树的存储结构179

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

5.4.3  树和森林的遍历182

5.4.4  本节试题精选183

5.4.5  答案与解析185

5.5  树与二叉树的应用191

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

5.5.2  并查集194

5.5.3  本节试题精选196

5.5.4  答案与解析198

归纳总结204

思维拓展204

第6章  图206

6.1　图的基本概念206

6.1.1　图的定义206

6.1.2　本节试题精选210

6.1.3　答案与解析211

6.2　图的存储及基本操作214

6.2.1　邻接矩阵法214

6.2.2　邻接表法215

6.2.3　十字链表217

6.2.4　邻接多重表217

6.2.5　图的基本操作218

6.2.6　本节试题精选219

6.2.7　答案与解析222

6.3　图的遍历227

6.3.1　广度优先搜索227

6.3.2　深度优先搜索230

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

6.3.4　本节试题精选231

6.3.5　答案与解析234

6.4　图的应用239

6.4.1　最小生成树239

6.4.2　最短路径242

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

6.4.4　拓扑排序246

6.4.5　关键路径248

6.4.6　本节试题精选251

6.4.7　答案与解析260

归纳总结275

思维拓展276

第7章  查找277

7.1  查找的基本概念277

7.2  顺序查找和折半查找278

7.2.1  顺序查找278

7.2.2  折半查找280

7.2.3  分块查找281

7.2.4  本节试题精选282

7.2.5  答案与解析285

7.3  树型查找291

7.3.1  二叉排序树（BST）291

7.3.2  平衡二叉树295

7.3.3  红黑树299

7.3.4  本节试题精选305

7.3.5  答案与解析309

7.4  B树和B+树319

7.4.1  B树及其基本操作319

7.4.2  B+树的基本概念322

7.4.3  本节试题精选323

7.4.4  答案与解析325

7.5  散列（Hash）表331

7.5.1  散列表的基本概念331

7.5.2  散列函数的构造方法331

7.5.3  处理冲突的方法332

7.5.4  散列查找及性能分析334

7.5.5  本节试题精选335

7.5.6  答案与解析338

归纳总结343

思维拓展344

第8章  排序345

8.1  排序的基本概念346

8.1.1  排序的定义346

8.1.2  本节试题精选346

8.1.3  答案与解析347

8.2  插入排序347

8.2.1  直接插入排序347

8.2.2  折半插入排序349

8.2.3  希尔排序349

8.2.4  本节试题精选351

8.2.5  答案与解析352

8.3  交换排序355

8.3.1  冒泡排序355

8.3.2  快速排序356

8.3.3  本节试题精选359

8.3.4  答案与解析361

8.4  选择排序366

8.4.1  简单选择排序366

8.4.2  堆排序366

8.4.3  本节试题精选369

8.4.4  答案与解析371

8.5  归并排序、基数排序和计数排序377

8.5.1  归并排序377

8.5.2  基数排序379

*8.5.3  计数排序380

8.5.4  本节试题精选382

8.5.5  答案与解析384

8.6  各种内部排序方法的比较及应用387

8.6.1  内部排序方法的比较387

8.6.2  内部排序方法的应用388

8.6.3  本节试题精选389

8.6.4  答案与解析391

8.7  外部排序394

8.7.1  外部排序的基本概念394

8.7.2  外部排序的方法394

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

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

8.7.5  最佳归并树397

8.7.6  本节试题精选399

8.7.7  答案与解析400

归纳总结404

思维拓展405

参考文献406