数据结构习题精析与考研辅导

前言

第1章引论1

1.1数据结构课程的地位和考试要求1

1.1.1数据结构课程的地位1

1.1.2考试要求1

1.1.3考查的知识点1

1.2数据结构和算法的预备知识3

1.2.1数据结构的主要概念3

1.2.2算法及算法分析4

1.2.3选择填空题解析6

1.2.4综合应用题选讲8

1.3使用C/C++的几个规则11

1.3.1算法结构11

1.3.2函数参数11

1.3.3条件运算11

1.3.4动态存储分配12

1.3.5标准输入/输出12

1.3.6指针12

第2章线性表13

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

2.1.1知识点复习13

2.1.2关键问题点拨13

2.1.3选择填空题解析14

2.2线性表的存储表示14

2.2.1知识点复习14

2.2.2关键问题点拨17

2.2.3选择填空题解析17

2.2.4综合应用题选讲18

2.3线性表的插入和删除运算19

2.3.1知识点复习19

2.3.2关键问题点拨21

2.3.3选择填空题解析21

2.3.4综合应用题选讲24

2.4线性表的应用33

第3章栈、队列和多维数组39

3.1栈和队列的基本概念39

3.1.1知识点复习39

3.1.2关键问题点拨40

3.1.3选择填空题解析40

3.1.4综合应用题选讲42

3.2栈的存储结构44

3.2.1知识点复习44

3.2.2关键问题点拨45

3.2.3选择填空题解析46

3.2.4综合应用题选讲47

3.3队列的存储结构49

3.3.1知识点复习49

3.3.2关键问题点拨51

3.3.3选择填空题解析52

3.3.4综合应用题选讲53

3.4栈和队列的应用58

3.4.1知识点复习58

3.4.2关键问题点拨60

3.4.3选择填空题解析61

3.4.4综合应用题选讲61

3.5数组与特殊矩阵的压缩存储72

3.5.1知识点复习72

3.5.2关键问题点拨75

3.5.3选择填空题解析77

3.5.4综合应用题选讲78

第4章树与二叉树87

4.1树的基本概念87

4.1.1知识点复习87

4.1.2关键问题点拨88

4.1.3选择填空题解析88

4.1.4综合应用题选讲88

4.2二叉树的定义和特性88

4.2.1知识点复习88

4.2.2关键问题点拨90

4.2.3选择填空题解析90

4.2.4综合应用题选讲91

4.3二叉树的存储和遍历93

4.3.1知识点复习93

4.3.2关键问题点拨95

4.3.3选择填空题解析96

4.3.4综合应用题选讲101

4.4线索二叉树110

4.4.1知识点复习110

4.4.2关键问题点拨112

4.4.3选择填空题解析112

4.4.4综合应用题选讲113

4.5树与森林118

4.5.1知识点复习118

4.5.2关键问题点拨123

4.5.3选择填空题解析124

4.5.4综合应用题选讲125

4.6二叉排序树131

4.6.1知识点复习131

4.6.2关键问题点拨134

4.6.3选择填空题解析135

4.6.4综合应用题选讲136

4.7平衡二叉树144

4.7.1知识点复习144

4.7.2关键问题点拨147

4.7.3选择填空题解析148

4.7.4综合应用题选讲149

4.8Huffman树与Huffman编码151

4.8.1知识点复习151

4.8.2关键问题点拨153

4.8.3选择填空题解析153

4.8.4综合应用题选讲155

4.9堆157

4.9.1知识点复习157

4.9.2关键问题点拨160

4.9.3选择填空题解析161

4.9.4综合应用题选讲162

第5章图164

5.1图的基本概念164

5.1.1知识点复习164

5.1.2关键问题点拨165

5.1.3选择填空题解析165

5.1.4综合应用题选讲166

5.2图的存储及基本操作168

5.2.1知识点复习168

5.2.2关键问题点拨170

5.2.3选择填空题解析171

5.2.4综合应用题选讲173

5.3图的遍历177

5.3.1知识点复习177

5.3.2关键问题点拨179

5.3.3选择填空题解析180

5.3.4综合应用题选讲182

5.4最小（代价）生成树189

5.4.1知识点复习190

5.4.2关键问题点拨192

5.4.3选择填空题解析193

5.4.4综合应用题选讲195

5.5最短路径200

5.5.1知识点复习200

5.5.2关键问题点拨202

5.5.3选择填空题解析202

5.5.4综合应用题选讲204

5.6拓扑排序211

5.6.1知识点复习211

5.6.2关键问题点拨212

5.6.3选择填空题解析213

5.6.4综合应用题选讲214

5.7关键路径217

5.7.1知识点复习217

5.7.2关键问题点拨218

5.7.3选择填空题解析218

5.7.4综合应用题选讲219

第6章查找222

6.1查找的基本概念222

6.1.1知识点复习222

6.1.2关键问题点拨222

6.2顺序查找法223

6.2.1知识点复习223

6.2.2关键问题点拨225

6.2.3选择填空题解析226

6.2.4综合应用题选讲227

6.3折半查找法230

6.3.1知识点复习230

6.3.2关键问题点拨231

6.3.3选择填空题解析231

6.3.4综合应用题选讲233

6.4B树与B+树237

6.4.1知识点复习237

6.4.2关键问题点拨243

6.4.3选择填空题解析244

6.4.4综合应用题选讲247

6.5散列表及其查找252

6.5.1知识点复习252

6.5.2关键问题点拨257

6.5.3选择填空题解析259

6.5.4综合应用题选讲261

第7章排序269

7.1排序的基本概念269

7.1.1知识点复习269

7.1.2关键问题点拨269

7.2四种简单的排序方法270

7.2.1知识点复习270

7.2.2关键问题点拨272

7.2.3选择填空题解析274

7.2.4综合应用题选讲276

7.3希尔排序281

7.3.1知识点复习281

7.3.2关键问题点拨282

7.3.3选择填空题解析283

7.3.4综合应用题选讲283

7.4快速排序285

7.4.1知识点复习285

7.4.2关键问题点拨286

7.4.3选择填空题解析287

7.4.4综合应用题选讲288

7.5堆排序294

7.5.1知识点复习294

7.5.2关键问题点拨295

7.5.3选择填空题解析296

7.5.4综合应用题选讲297

7.6二路归并排序299

7.6.1知识点复习299

7.6.2关键问题点拨301

7.6.3选择填空题解析302

7.6.4综合应用题选讲303

7.7基数排序307

7.7.1知识点复习307

7.7.2关键问题点拨310

7.7.3选择填空题解析310

7.7.4综合应用题选讲310

7.8各种内排序方法的比较和选择311

7.8.1知识点复习311

7.8.2关键问题点拨312

7.8.3选择填空题解析313

7.8.4综合应用题选讲314

第8章试题分析与备考指南319

8.1全国硕士研究生入学考试真题分析319

8.1.12009年联考试题数据结构部分319

8.1.22010年联考试题数据结构部分325

8.2考试复习建议331

8.2.1试题难度分析331

8.2.2风险和机遇332

8.2.3主要知识点的难度级别和重点级别332

8.2.4复习建议342

8.2.5考试指导343

8.2.6结束语345

模拟试题及参考答案346

参考文献356

　　本书共分8章，第1章分3部分，首先较为概括地介绍数据结构课程的地位和主要考点，这是一个引子；然后介绍数据结构相关的基本概念和算法设计、分析、评价的简要知识和方法；最后简单介绍C语言中涉及算法编写的相关知识。第2～7章涵盖考研大纲的6个方面。每一个知识点都按照“知识点复习一关键问题点拨一选择填空题解析一综合应用题选讲”来复习，通过例题深入分析讲解，以期达到举一反三的目的。在“知识点复习”部分简单概括了相关知识点的主要内容和要点说明，部分算法给出了算法思路和源代码。第8章也由3部分组成。首先对历年联考的真题做了精确解析，并总结了阅卷中发现的学生易犯的错误，对于算法设计题特别提示了应如何对其阅读和理解。接下来详细列出考研大纲各知识点的细化要求，最后导出考研的复习方法和应试指南，可供读者参考。　　本书是根据《全国硕士研究生入学统一考试计算机学科专业基础综合考试大纲》编写的学习数据结构的辅导教材。全书共分8章。第1章介绍数据结构课程的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。第2～7章对应考试大纲的6个方面，包括线性表，栈、队列和多维数组，树与二叉树，图，查找，排序，分别进行详解。每个方面细分为若干知识点，每个知识点按照“知识点复习一关键问题点拨一选择填空题解析一综合应用题选讲”等4个步骤层层深入，有针对性地讲解和分析。在紧紧把握考试大纲的前提下，尽可能深入细节、扩展知识面、联想相关数据结构。第8章对历年联考的真题做了精确解析，细化了考试大纲各个知识点的要求，并提供了学习指导和应试指南。　　本书融入作者30多年数据结构教学的经验，考虑了不同层次学生学习的需要，精选了630个例题，覆盖了相关知识点的方方面面，既可以作为大学计算机专业学习数据结构课程的辅助教材，也可以作为计算机专业考研的辅导教材。【作者简介】　　殷人昆，清华大学计算机系教授。1970年清华大学计算数学专业毕业，1980年获清华大学计算机系工学硕士学位，1985年赴日本东京理科大学做访问学者，研究方向为软件工程过程的质量管理和软件产品的质量评价。主要讲授大学本科“数据结构”、“软件工程”和研究生“软件工程”、“软件项目管理”，其中，本科“数据结构”和工程硕士“软件工程”是清华大学精品课程，此外还主持了教育部-微软精品课程“数据结构”的建设。