本教材是根据《全国硕士研究生入学考试计算机专业基础综合考试大纲》编写的学习数据结构的辅导教材。全书共分8章。第1章是介绍数据结构的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。第2～7章对应考试大纲的6个方面，包括线性表，栈、队列和数组，树与二叉树，图，查找，排序。每个方面又细分为若干知识点，每个知识点按照“知识点复习―关键问题点拨―选择填空题解析―综合应用题选讲”等4个步骤层层深入，有针对性地讲解和分析。在紧紧把握考试大纲的前提下，尽可能深入细节、扩展知识面、联想相关数据结构。第8章对历年联考的真题做了精确解析，细化了考试大纲各个知识点的要求，并提供了学习指导和应试指南。
针对《全国硕士研究生入学考试计算机专业基础综合考试大纲》，按照“知识点复习—关键问题点拨—选择填空题解析—综合应用题选讲”的安排复习每一个知识点。特别是，“关键问题点拨”部分还介绍了许多教科书中没有强调但不可忽视的细节。
作者将多年的“数据结构”课程教学经验、辅导本科生准备考试的经验包含在本书中，为读者学好“数据结构”课程和考前准备提供了有效建议。
对历年考研真题进行了深入剖析，特别是对容易失分之处进行了特别提示，有利于考生避免失误。
书中还附有模拟试卷，帮助读者巩固基础知识，进行考前演练。
根据教育部办公厅教学厅（2008）11号文件要求，从2009年起，全国硕士研究生统一入学考试计算机学科专业基础综合考试全国联考，考试科目包括数据结构、计算机组成原理、操作系统和计算机网络。要求考生比较系统地理解相关科目的基本概念、基本原理和方法，能够运用所掌握的基本原理和方法分析、设计和解决相关的理论问题和实际问题。
数据结构科目占45分，从考研大纲可以看到，考核的主要知识点涵盖线性表，栈、队列与多维数组，树与二叉树，图，查找和排序等6个方面。从考试出题的点和面分析，基本覆盖了这6个方面。然而，与其他考试科目比较，数据结构是最不好把握，试题灵活性最强，最容易在细节上失分的科目。因此，如何提高数据结构学习的效果，全面掌握数据结构的相关知识点并能合理运用，是应考的关键。
许多学习数据结构课程的学生和正在复习数据结构课程的考生最感困惑的问题是如何抓住复习的重点，如何把握考核的范围。按道理讲，根据考试大纲复习不就可以了吗？遗憾的是，考试大纲只给出了一个大概的范围，到底考到何种深度和广度，考试大纲并未指明。例如，“栈和队列的应用”是一个必考的知识点，凡是在解决问题时涉及栈或队列的都算栈和队列的应用，其范围很难界定。所以在计算机学科专业基础综合考试中，数据结构是最难复习的课程。许多学生都希望通过选择一本权威的参考书来解决所有问题，殊不知任何一本优秀的参考书都有其优点和缺点。有的参考书覆盖范围广但不深，有的参考书对某些问题阐述比较清楚但覆盖面不够，有的因为出书较早不能反映学科的发展，有的因为著作者的教学经验不足不能深入挖掘由知识点拓展出来的知识，有的甚至想当然地划分重点而没有了解学生的感受和需要。从几次联考阅卷来看，我确实为某些考生感到可惜，他们看了不少书，也做了不少题，然而某些题还是得不了高分。
本书作者从1978年便开始学习数据结构。从1983年开始，曾为清华附中和北京四中的中学生开课。1987年从日本回国后走上大学数据结构课程的讲堂。1992年开始与严蔚敏老师合作为清华大学计算机系本科生开课，1996～2008年承担清华大学考研数据结构和程序设计课程的命题和批改任务。针对不同层次的学生，使用过严蔚敏、刘美纶、许卓群、张乃孝以及本人自己编写的数据结构教材，积累了较多的教学经验。特别是通过与清华大学本科生的互动，与清华大学夜大学大专生的互动，与高教自考培训学生的互动，与北京广播电视大学学生的互动，与清航考研培训网站学生的互动，作者对数据结构的许多知识点有较深层次的理解，愿意通过本书，将这些经验与广大读者或考生共享。
本书共分8章，第1章分3部分，首先较为概括地介绍数据结构课程的地位和主要考点，这是一个引子；然后介绍数据结构相关的基本概念和算法设计、分析、评价的简要知识和方法；最后简单介绍C语言中涉及算法编写的相关知识。这一章虽然不是考研大纲所要求的，但有助于后续章节相关数据结构和算法设计的理解。
第2~7章涵盖考研大纲的6个方面。每一个知识点都按照“知识点复习―关键问题点拨―选择填空题解析―综合应用题选讲”来复习，通过例题深入分析讲解，以期达到举一反三的目的。在“知识点复习”部分简单概括了相关知识点的主要内容和要点说明，部分算法给出了算法思路和源代码。在“关键问题点拨”部分介绍了许多教科书上没有讲到的但不可忽视的细节辨析，这些都是通过与学生互动而得到的。在“选择填空题解析”部分对相关知识点涉及的数据结构定义、特点、性质，存储实现，算法分析等进行考查，并详细解释和分析可能混淆的概念。在“综合应用题选讲”部分中有证明题、问答题和算法设计题。根据知识点的可能出题频率，这类题在各个知识点中分配的数量有所不同，在某些知识点中题的数量较多，在有的知识点中题的数量较少，多数题都给出了求解思路和求解过程。
第8章也由3部分组成。首先对历年联考的真题做了精确解析，并总结了阅卷中发现的学生易犯的错误，对于算法设计题特别提示了应如何对其阅读和理解。接下来详细列出考研大纲各知识点的细化要求，最后导出考研的复习方法和应试指南，可供读者参考。
本书是作者本着作为一名教师，为考生“解惑”而编写的。它不但适合考研的学生使用，对在校学生学习数据结构课程也很有帮助。书中精选了各个大学和研究院的历年考研试题中的部分真题，也参考了部分国内外相关数据结构教材，还参考了网上的一些资料。由于时间有限，书中难免存在疏漏之处，恳请广大读者批评指正。
作者联系方式：yinrk@tsinghua.edu.cn。
计算机\数据结构
前言
第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
