第1章 数据结构绪论1

1.1 数据结构的概念及分类1

1.1.1 知识点复习1

1.1.2 疑难点辨析2

1.1.3 选择题解析3

1.1.4 应用题选讲5

1.2 算法和算法设计5

1.2.1 知识点复习5

1.2.2 疑难点辨析7

1.2.3 选择题解析8

1.2.4 应用题选讲8

1.3 算法分析11

1.3.1 知识点复习11

1.3.2 疑难点辨析12

1.3.3 选择题解析13

1.3.4 应用题选讲15

第2章 线性表19

2.1 线性表19

2.1.1 知识点复习19

2.1.2 疑难点辨析20

2.1.3 选择题解析20

2.1.4 应用题选讲20

2.2 顺序表21

2.2.1 知识点复习21

2.2.2 疑难点辨析23

2.2.3 选择题解析24

2.2.4 应用题选讲25

2.3 单链表30

2.3.1 知识点复习30

2.3.2 疑难点辨析33

2.3.3 选择题解析33

2.3.4 应用题选讲36

2.4 线性链表的其他变形42

2.4.1 知识点复习42

2.4.2 疑难点辨析44

2.4.3 选择题解析45

2.4.4 应用题选讲47

2.5 线性表的应用50

2.5.1 知识点复习50

2.5.2 疑难点辨析53

2.5.3 选择题解析53

2.5.4 应用题选讲54

第3章 栈和队列65

3.1 栈65

3.1.1 知识点复习65

3.1.2 疑难点辨析68

3.1.3 选择题解析69

3.1.4 应用题选讲71

3.2 队列76

3.2.1 知识点复习76

3.2.2 疑难点辨析79

3.2.3 选择题解析80

3.2.4 应用题选讲82

3.3 栈的应用85

3.3.1 知识点复习85

3.3.2 疑难点辨析86

3.3.3 选择题解析87

3.3.4 应用题选讲89

3.4 队列的应用95

3.4.1 知识点复习95

3.4.2 疑难点辨析96

3.4.3 选择题解析96

3.4.4 应用题选讲97

3.5 在算法设计中使用递归97

3.5.1 知识点复习97

3.5.2 疑难点辨析98

3.5.3 选择题解析99

3.5.4 应用题选讲101

3.6 双端队列108

3.6.1 知识点复习108

3.6.2 疑难点辨析109

3.6.3 选择题解析109

3.6.4 应用题选讲110

第4章 多维数组、字符串与广义表114

4.1 数组114

4.1.1 知识点复习114

4.1.2 疑难点辨析116

4.1.3 选择题解析116

4.1.4 应用题选讲117

4.2 特殊矩阵的压缩存储126

4.2.1 知识点复习126

4.2.2 疑难点辨析127

4.2.3 选择题解析128

4.2.4 应用题选讲129

4.3 稀疏矩阵134

4.3.1 知识点复习134

4.3.2 疑难点辨析135

4.3.3 选择题解析136

4.3.4 应用题选讲136

4.4 字符串140

4.4.1 知识点复习140

4.4.2 疑难点辨析143

4.4.3 选择题解析145

4.4.4 应用题选讲146

4.5 广义表155

4.5.1 知识点复习155

4.5.2 疑难点辨析156

4.5.3 选择题解析157

4.5.4 应用题选讲159

第5章 树与二叉树163

5.1 树的基本概念163

5.1.1 知识点复习163

5.1.2 疑难点辨析164

5.1.3 选择题解析164

5.1.4 应用题选讲165

5.2 二叉树的定义和特性165

5.2.1 知识点复习165

5.2.2 疑难点辨析166

5.2.3 选择题解析167

5.2.4 应用题选讲169

5.3 二叉树的存储171

5.3.1 知识点复习171

5.3.2 疑难点辨析172

5.3.3 选择题解析172

5.3.4 应用题选讲173

5.4 二叉树的遍历173

5.4.1 知识点复习173

5.4.2 疑难点辨析175

5.4.3 选择题解析179

5.4.4 应用题选讲184

5.5 线索二叉树195

5.5.1 知识点复习195

5.5.2 疑难点辨析197

5.5.3 选择题解析198

5.5.4 应用题选讲199

5.6 树与森林205

5.6.1 知识点复习205

5.6.2 疑难点辨析209

5.6.3 选择题解析212

5.6.4 应用题选讲213

第6章 树与二叉树的应用222

6.1 二叉查找树222

6.1.1 知识点复习222

6.1.2 疑难点辨析225

6.1.3 选择题解析226

6.1.4 应用题选讲228

6.2 AVL树237

6.2.1 知识点复习237

6.2.2 疑难点辨析242

6.2.3 选择题解析244

6.2.4 应用题选讲245

6.3 Huffman树与Huffman编码249

6.3.1 知识点复习 249

6.3.2 疑难点辨析251

6.3.3 选择题解析252

6.3.4 应用题选讲253

6.4 堆258

6.4.1 知识点复习258

6.4.2 疑难点辨析260

6.4.3 选择题解析261

6.4.4 应用题选讲263

6.5 并查集267

6.5.1 知识点复习267

6.5.2 疑难点辨析269

6.5.3 选择题解析269

6.5.4 应用题选讲270

第7章 图273

7.1 图的基本概念273

7.1.1 知识点复习273

7.1.2 疑难点辨析274

7.1.3 选择题解析274

7.1.4 应用题选讲276

7.2 图的存储及基本操作278

7.2.1 知识点复习278

7.2.2 疑难点辨析280

7.2.3 选择题解析281

7.2.4 应用题选讲284

7.3 图的遍历289

7.3.1 知识点复习289

7.3.2 疑难点辨析291

7.3.3 选择题解析293

7.3.4 应用题选讲296

7.4 最小生成树305

7.4.1 知识点复习305

7.4.2 疑难点辨析306

7.4.3 选择题解析307

7.4.4 应用题选讲310

7.5 最短路径316

7.5.1 知识点复习316

7.5.2 疑难点辨析317

7.5.3 选择题解析318

7.5.4 应用题选讲320

7.6 拓扑排序和关键路径328

7.6.1 知识点复习328

7.6.2 疑难点辨析331

7.6.3 选择题解析332

7.6.4 应用题选讲335

第8章 查找341

8.1 查找的基本概念341

8.1.1 知识点复习341

8.1.2 疑难点辨析342

8.1.3 选择题解析342

8.1.4 应用题选讲343

8.2 顺序查找法344

8.2.1 知识点复习344

8.2.2 疑难点辨析346

8.2.3 选择题解析347

8.2.4 应用题选讲349

8.3 折半查找法352

8.3.1 知识点复习352

8.3.2 疑难点辨析354

8.3.3 选择题解析354

8.3.4 应用题选讲357

8.4 B树361

8.4.1 知识点复习361

8.4.2 疑难点辨析367

8.4.3 选择题解析368

8.4.4 应用题选讲371

8.5 散列表及其查找377

8.5.1 知识点复习377

8.5.2 疑难点辨析382

8.5.3 选择题解析385

8.5.4 应用题选讲388

第9章 排序396

9.1 排序的基本概念396

9.1.1 知识点复习396

9.1.2 疑难点辨析397

9.1.3 选择题解析398

9.1.4 应用题选讲398

9.2 插入排序399

9.2.1 知识点复习399

9.2.2 疑难点辨析401

9.2.3 选择题解析404

9.2.4 应用题选讲406

9.3 交换排序410

9.3.1 知识点复习410

9.3.2 疑难点辨析413

9.3.3 选择题解析414

9.3.4 应用题选讲416

9.4 选择排序427

9.4.1 知识点复习427

9.4.2 疑难点辨析432

9.4.3 选择题解析433

9.4.4 应用题选讲435

9.5 归并排序439

9.5.1 知识点复习439

9.5.2 疑难点辨析440

9.5.3 选择题解析442

9.5.4 应用题选讲442

9.6 基数排序448

9.6.1 知识点复习448

9.6.2 疑难点辨析451

9.6.3 选择题解析452

9.6.4 应用题选讲452

9.7 各种内部排序方法的比较和选择453

9.7.1 知识点复习453

9.7.2 疑难点辨析454

9.7.3 选择题解析455

9.7.4 应用题选讲457

第10章 外排序463

10.1 主存储器和外存储器463

10.1.1 知识点复习463

10.1.2 疑难点辨析464

10.1.3 选择题解析464

10.2 磁盘文件的外排序过程465

10.2.1 知识点复习465

10.2.2 疑难点辨析468

10.2.3 选择题解析470

10.2.4 应用题选讲471

10.3 m路平衡归并473

10.3.1 知识点复习473

10.3.2 疑难点辨析473

10.3.3 选择题解析474

10.3.4 应用题选讲475

10.4 初始归并段的生成479

10.4.1 知识点复习479

10.4.2 疑难点辨析480

10.4.3 选择题解析481

10.4.4 应用题选讲482

10.5 最佳归并树485

10.5.1 知识点复习485

10.5.2 疑难点辨析486

10.5.3 选择题解析486

10.5.4 应用题选讲487

10.6 并行操作的缓冲区处理488

10.6.1 知识点复习488

10.6.2 疑难点辨析489

10.6.3 选择题解析490

10.6.4 应用题选讲490

10.7 磁带归并排序491

10.7.1 知识点复习491

10.7.2 疑难点辨析491

10.7.3 选择题解析492

10.7.4 应用题选讲493

附录 全国硕士研究生入学考试“数据结构”真题分析494

参考书目515