本书是计算机专业研究生入学考试“数据结构”课程的复习用书，内容包括绪论、线性表、栈和队列、树与二叉树、图、查找、排序等。全书严格按照最新计算机统考大纲的数据结构部分，对大纲所涉及的知识点进行集中梳理，力求内容精炼、重点突出、深入浅出。本书精选各名校的历年考研真题，并给出详细的解题思路，力求实现讲练结合、灵活掌握、举一反三的功效。通过本书“书本＋在线”的学习方式和网上答疑方式，读者在使用本书时遇到的任何疑难点，都可以在王道论坛发帖与道友互动。本书可作为考生参加计算机专业研究生入学考试的备考复习用书，也可作为计算机专业的学生学习数据结构课程的辅导用书。

前 言 2011年，由王道论坛（www.cskaoyan.com）组织名校状元级选手，编写了4本单科辅导书。单科书是基于王道之前作品的二代作品，不论是编排方式还是内容质量，都较前一版本的王道书有了较大的提升。这套书也参考了同类优秀的教材和辅导书，更是结合了高分选手们自己的复习经验。无论是对考点的讲解，还是对习题的选择和解析，都结合了他们对专业课复习的独特见解。2019年，我们继续推出“王道考研系列”单科书，一共4本： ? 《2020年数据结构考研复习指导》 ? 《2020年计算机组成原理考研复习指导》 ? 《2020年操作系统考研复习指导》 ? 《2020年计算机网络考研复习指导》 每一版，我们不仅会修正之前发现的全部错误，而且还会对考点讲解做出尽可能的优化，也重新审视论坛的交流帖，针对大家提出的疑问和建议对本书做出针对性的优化；此外还重新筛选了部分习题，尤其是对习题的解析做出了更好的改进。 后期在冲刺阶段，王道还将出版2本冲刺用书： ? 《2020年计算机专业基础综合考试历年真题及思路分析》 ? 《2020年计算机专业基础综合考试最后8套模拟题》 当然，深入掌握专业课内容没有捷径，考生也不应抱有任何侥幸心理，扎扎实实打好基础、踏踏实实做题巩固，最后灵活致用才是高分的保障。我们只希望这套书能够指导大家复习考研，但学习还是得靠自己，高分不是建立在任何空中楼阁之上的。对于一个想继续在计算机专业领域深造的考生来说，认真学习和扎实掌握这4门计算机专业中最基础的专业课，是最基本的前提。 “王道考研系列”是计算机专业考生口碑相传的辅导书，自出版以来在同类书中的销量始终遥遥领先。有这么多学长的成功经验，我相信只要考生合理地利用好本书，并采用合理的复习方法，就一定会收获属于自己的那份回报。 读者在复习时遇到的疑问，可以通过读者QQ群（346165686）交流。从2019版起，我们就陆续制作了配套辅导及习题讲解视频，2020版将免费为读者提供所有选择题的讲解视频，读者可扫相应二维码观看。此外，请读者关注王道论坛微信公众号（wangdaoluntan），里面会及时推送勘误及配套视频的相关情况。 “不打广告、不发证书、不包就业，专注于培养有梦想、有能力的高级码农”王道程序员训练营是王道团队举办的线下程序员魔鬼式训练。打下扎实的编程和算法基本功，培养程序员式的学习能力和学习方法，期待有梦想有追求的你加入！ 予人玫瑰，手有余香，王道论坛伴你一路同行！ 风华漫舞 致 读 者 ——王道单科使用方法的道友建议 我是“二战考生”，2012年第一次考研成绩333分（专业代码408，成绩81分），痛定思痛后决心再战。潜心复习了半年后终于以392分（专业代码408，成绩124分）考入上海交通大学计算机系，这半年里我的专业课成绩提高了43分，成了提分主力。从未达录取线到考出比较满意的成绩；从蒙头乱撞到有了自己明确的复习思路，我想这也是为什么风华哥从诸多高分选手中选我给大家介绍经验的一个原因吧。 整个专业课的复习是围绕王道材料展开的，从一遍、两遍、三遍看单科书的积累提升，到做8套模拟题时的强化巩固，再到看思路分析时的醍醐灌顶。王道书能两次押中原题固然有运气成分，但这也从侧面说明他们的编写思路和选题方向与真题很接近。 下面说说我的具体复习过程。 每天划给专业课的时间是3～4小时。第一遍细看课本，看完一章做一章单科书（红笔标注错题），这一遍共持续2个月。第二遍主攻单科书（红笔标注重难点），辅看课本。第二遍看单科书和课本的速度快了很多，但感觉收获更多，常有温故知新的感觉，理解更深刻（风华注，建议这时再速看第三遍，特别针对错题和重难点。模拟题做完后再跳看第四遍）。 以上是打基础阶段，注意单科书和课本我仔细精读了两遍，弄懂每个知识点和习题。大概11月上旬开始做模拟题和思路分析，期间遇到不熟悉的地方不断回头查阅单科书和课本。8套模拟题的考点覆盖得很全面，所以大家做题时如果忘记了某个知识点，千万不要慌张，赶紧回去看这个知识盲点，最后的模拟就是查漏补缺。模拟题一定要严格按考试时间去做（14:00—17:00），注意应试技巧，做完试题后再回头研究错题。算法题的最优解法不太好想，如果实在没思路，建议直接“暴力”解决，结果正确也能有10分，总比苦拼出15分来而将后面比较好拿分的题耽误了好（这是我第一年的切身教训）。最后剩了几天看标注的错题，第三遍跳看单科书，考前一夜浏览完网络，踏实地睡着了…… 考完专业课，走出考场终于长舒一口气，考试情况也胸中有数。回想这半年的复习，耐住了寂寞和诱惑，雨雪风霜从未间断地跑去自习，考研这人生一站终归没有辜负我的用心良苦。佛教徒说世间万物生来平等，都要落入春华秋实的代谢中去，辩证唯物主义认为事物作为过程存在，凡是存在的终归要结束，你不去为活得多姿多彩拼搏，真到了和青春说再见时你是否会可惜虚枉了青春？风华哥说过我们都是有梦想的青年，我们正在逆袭，你呢？ 感谢风华大哥的信任，给我这个机会分享专业课复习经验给大家，作为一个铁杆道友在王道受益匪浅，也借此机会回报王道论坛。祝大家金榜题名！ ccg1990@SJTU

第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 答案与解析/9 归纳总结/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 线性表的链式表示/27 2.3.1 单链表的定义/27 2.3.2 单链表上基本操作的实现/28 2.3.3 双链表/31 2.3.4 循环链表/33 2.3.5 静态链表/33 2.3.6 顺序表和链表的比较/34 2.3.7 本节试题精选/35 2.3.8 答案与解析/41 归纳总结/58 思维拓展/58 第3章 栈和队列/59 3.1 栈/59 3.1.1 栈的基本概念/59 3.1.2 栈的顺序存储结构/60 3.1.3 栈的链式存储结构/62 3.1.4 本节试题精选/62 3.1.5 答案与解析/66 3.2 队列/73 3.2.1 队列的基本概念/73 3.2.2 队列的顺序存储结构/73 3.2.3 队列的链式存储结构/75 3.2.4 双端队列/77 3.2.5 本节试题精选/78 3.2.6 答案与解析/81 3.3 栈和队列的应用/85 3.3.1 栈在括号匹配中的应用/85 3.3.2 栈在表达式求值中的应用/85 3.3.3 栈在递归中的应用/86 3.3.4 队列在层次遍历中的应用/87 3.3.5 队列在计算机系统中的应用/88 3.3.6 本节试题精选/88 3.3.7 答案与解析/90 3.4 特殊矩阵的压缩存储/96 3.4.1 数组的定义/96 3.4.2 数组的存储结构/96 3.4.3 矩阵的压缩存储/97 3.4.4 稀疏矩阵/99 3.4.5 本节试题精选/99 3.4.6 答案与解析/100 归纳总结/102 思维拓展/102 第4章 树与二叉树/103 4.1 树的基本概念/103 4.1.1 树的定义/103 4.1.2 基本术语/104 4.1.3 树的性质/105 4.1.4 本节试题精选/105 4.1.5 答案与解析/106 4.2 二叉树的概念/107 4.2.1 二叉树的定义及其 主要特性/107 4.2.2 二叉树的存储结构/109 4.2.3 本节试题精选/110 4.2.4 答案与解析/113 4.3 二叉树的遍历和线索二叉树/117 4.3.1 二叉树的遍历/117 4.3.2 线索二叉树/120 4.3.3 本节试题精选/122 4.3.4 答案与解析/128 4.4 树、森林/145 4.4.1 树的存储结构/145 4.4.2 树、森林与二叉树的转换/147 4.4.3 树和森林的遍历/148 4.4.4 树的应用—并查集/148 4.4.5 本节试题精选/150 4.4.6 答案与解析/152 4.5 树与二叉树的应用/157 4.5.1 二叉排序树/157 4.5.2 平衡二叉树/160 4.5.3 哈夫曼树和哈夫曼编码/162 4.5.4 本节试题精选/164 4.5.5 答案与解析/169 归纳总结/179 思维拓展/180 第5章 图/181 5.1 图的基本概念/181 5.1.1 图的定义/181 5.1.2 本节试题精选/184 5.1.3 答案与解析/187 5.2 图的存储及基本操作/189 5.2.1 邻接矩阵法/189 5.2.2 邻接表法/190 5.2.3 十字链表/192 5.2.4 邻接多重表/192 5.2.5 图的基本操作/193 5.2.6 本节试题精选/194 5.2.7 答案与解析/196 5.3 图的遍历/199 5.3.1 广度优先搜索/200 5.3.2 深度优先搜索/201 5.3.3 图的遍历与图的连通性/203 5.3.4 本节试题精选/203 5.3.5 答案与解析/206 5.4 图的应用/211 5.4.1 最小生成树/211 5.4.2 最短路径/213 5.4.3 拓扑排序/216 5.4.4 关键路径/217 5.4.5 本节试题精选/219 5.4.6 答案与解析/226 归纳总结/237 思维拓展/238 第6章 查找/239 6.1 查找的基本概念/239 6.2 顺序查找和折半查找/240 6.2.1 顺序查找/240 6.2.2 折半查找/242 6.2.3 分块查找/243 6.2.4 本节试题精选/244 6.2.5 答案与解析/248 6.3 B树和B+树/253 6.3.1 B树及其基本操作/253 6.3.2 B+树的基本概念/256 6.3.3 本节试题精选/257 6.3.4 答案与解析/259 6.4 散列表/263 6.4.1 散列表的基本概念/263 6.4.2 散列函数的构造方法/264 6.4.3 处理冲突的方法/265 6.4.4 散列查找及性能分析/266 6.4.5 本节试题精选/266 6.4.6 答案与解析/269 6.5 串/274 6.5.1 串的定义/274 6.5.2 串的存储结构/275 6.5.3 串的基本操作/276 6.5.4 串的模式匹配/276 6.5.5 改进的模式匹配算法——KMP算法/277 6.5.6 本节试题精选/280 6.5.7 答案与解析/281 归纳总结/289 思维拓展/289 第7章 排序/290 7.1 排序的基本概念/291 7.1.1 排序的定义/291 7.1.2 本节试题精选/291 7.1.3 答案与解析/292 7.2 插入排序/292 7.2.1 直接插入排序/292 7.2.2 折半插入排序/293 7.2.3 希尔排序/294 7.2.4 本节试题精选/295 7.2.5 答案与解析/297 7.3 交换排序/299 7.3.1 冒泡排序/299 7.3.2 快速排序/300 7.3.3 本节试题精选/301 7.3.4 答案与解析/304 7.4 选择排序/309 7.4.1 简单选择排序/309 7.4.2 堆排序/310 7.4.3 本节试题精选/312 7.4.4 答案与解析/315 7.5 归并排序和基数排序/318 7.5.1 归并排序/318 7.5.2 基数排序/319 7.5.3 本节试题精选/320 7.5.4 答案与解析/322 7.6 各种内部排序算法的比较及应用/324 7.6.1 内部排序算法的比较/324 7.6.2 内部排序算法的应用/325 7.6.3 本节试题精选/326 7.6.4 答案与解析/327 7.7 外部排序/330 7.7.1 外部排序的基本概念/330 7.7.2 外部排序的方法/330 7.7.3 多路平衡归并与败者树/331 7.7.4 置换-选择排序（生成初始归并段）/332 7.7.5 最佳归并树/333 7.7.6 本节试题精选/334 7.7.7 答案与解析/336 归纳总结/338 思维拓展/339 参考文献/340