王道考研:2013年数据结构联考复习指导

依托王道的平台与口碑，“王道考研系列”已然成为计算机考研辅导书中的口碑品牌，这一系列书由王道论坛组织名校高分选手编写，不仅参考了同类优秀图书，更是融入了论坛众多高分考生的智慧、以及论坛交流的精华。“书本+在线”的学习方式是本书最大特色，一方面它可以使同学们能及时解决复习中的遇到的各种疑问，另一方面它也能更好的促进王道论坛对本书进行改进和优化。
在过去的2年，有众多考生通过王道考研辅导书实现了自己的名校梦，也正是靠着成功学长的口碑相传，才有了王道论坛和王道考研辅导书今天的口碑。当然辅导书只是工具，成功只能靠自己，让自己更加强大。但我相信，有王道论坛以及王道考研辅导书的支撑，一定会让同学们的考研之路变得更加轻松和高效！

本书严格按照最新计算机考研大纲的数据结构部分，对大纲所涉及的知识点进行集中梳理，力求内容精炼、重点突出、深入浅出。本书精选了名校历年考研真题，并给出详细的解题思路，力求达到讲练结合、灵活掌握、举一反三的功效。创新的“书本+在线”的学习方式，网上答疑，通过本书可大大提高考生的复习效果，达到事半功倍的复习效率。
本书可作为考生参加计算机专业研究生入学考试的备考复习用书，也可作为计算机专业的学生学习数据结构课程的辅导用书。

王道论坛（www.cskaoyan.com）由清华、北大、浙大、上交、哈工大、中科院等名校计算机研究生共同创办，致力于给报考计算机专业研究生的考生提供帮助和指导。王道论坛是唯一一家专注于名校计算机考研的论坛。 “王道考研系列”由王道论坛组织清华、哈工大、浙大、上海交大等名校的初试状元级选手共同编写，融入了论坛众多名校高分选手的智慧，以及论坛交流精华。

 第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  答案与解析...................................................................（8）?
      第2章  线性表...............................................................................（10）?
2.1  线性表的定义和基本操作..................................................................（10）?
          2.1.1  线性表的定义...............................................................（10）?
          2.1.2  线性表的基本操作.......................................................（11）?
          2.1.3  本节试题精选...............................................................（11）?
          2.1.4  答案与解析...................................................................（11）?
2.2  线性表的顺序表示.............................................................................（12）?
          2.2.1  顺序表的定义.............................................................（12）?
          2.2.2  顺序表上基本操作的实现.........................................（13）?
          2.2.3  本节试题精选.............................................................（15）?
          2.2.4  答案与解析..................................................................（17）?
2.3  线性表的链式表示............................................................................（24）?
          2.3.1  单链表的定义.............................................................（24）?
          2.3.2  单链表上基本操作的实现.........................................（25）?
          2.3.3  双链表........................................................................（29）?
          2.3.4  循环链表....................................................................（30）?
          2.3.5  静态链表...................................................................（31）?
          2.3.6  顺序表和链表的比较................................................（32）?
          2.3.7  本节试题精选...........................................................（33）?
          2.3.8  答案与解析..............................................................（37）?
      第3章  栈和队列.....................................................................（54）?
3.1  栈....................................................................................................（54）?
          3.1.1  栈的基本概念...........................................................（54）?
          3.1.2  栈的顺序存储结构..................................................（55）?
          3.1.3  栈的链式存储结构..................................................（57）?
          3.1.4  本节试题精选...........................................................（58）?
          3.1.5  答案与解析..............................................................（60）?
3.2  队列.................................................................................................（67）?
          3.2.1  队列的基本概念........................................................（67）?
          3.2.2  队列的顺序存储结构..................................................（68）?
          3.2.3  队列的链式存储结构...................................................（70）?
          3.2.4  双端队列....................................................................................（72）?
          3.2.5  本节试题精选............................................................................（73）?
          3.2.6  答案与解析................................................................................（75）?
3.3  栈和队列的应用................................................................................................（79）?
          3.3.1  栈在括号匹配中的应用..............................................................（79）?
          3.3.2  栈在表达式求值中的应用...........................................................（79）?
          3.3.3  栈在递归中的应用........................................................................（80）?
          3.3.4  队列在层次遍历中的应用...........................................................（81）?
          3.3.5  队列在计算机系统中的应用.........................................................（82）?
          3.3.6  本节试题精选..................................................................................（83）?
          3.3.7  答案与解析.....................................................................................（84）?
3.4  特殊矩阵的压缩存储............................................................................................（88）?
          3.4.1  数组的定义....................................................................................（88）?
          3.4.2  数组的存储结构..............................................................................（89）?
          3.4.3  矩阵的压缩存储..............................................................................（89）?
          3.4.4  稀疏矩阵...........................................................................................（92）?
          3.4.5  本节试题精选....................................................................................（92）?
          3.4.6  答案与解析........................................................................................（93）?
      第4章  树与二叉树...........................................................................................（94）?
4.1  树的基本概念..........................................................................................................（95）?
          4.1.1  树的定义............................................................................................（95）?
          4.1.2  基本术语...........................................................................................（95）?
          4.1.3  树的性质..........................................................................................（96）?
          4.1.4  本节试题精选...................................................................................（96）?
          4.1.5  答案与解析........................................................................................（97）?
4.2  二叉树的概念.........................................................................................................（98）?
          4.2.1  二叉树的定义及其主要特性...........................................................（98）?
          4.2.2  二叉树的存储结构.........................................................................（100）?
          4.2.3  本节试题精选................................................................................（102）?
          4.2.4  答案与解析...................................................................................（103）?
4.3  二叉树的遍历和线索二叉树................................................................................（107）?
          4.3.1  二叉树的遍历....................................................................................（107）?
          4.3.2  线索二叉树..........................................................................................（110）?
          4.3.3  本节试题精选.......................................................................................（113）
          4.3.4  答案与解析.........................................................................................（116）?
4.4  树、 森林..................................................................................................................（133）?
          4.4.1  树的存储结构......................................................................................（133）?
          4.4.2  树、 森林与二叉树的转换.............................................................（135）?
          4.4.3  树和森林的遍历.................................................................................（136）
          4.4.4  树的应用——并查集.......................................................................（136）?
          4.4.5  本节试题精选...................................................................................（138）?
          4.4.6  答案与解析......................................................................................（140）?
4.5  树与二叉树的应用..................................................................................................（144）?
          4.5.1  二叉排序树.......................................................................................（144）?
          4.5.2  平衡二叉树.................................................................................（148）?
          4.5.3  哈夫曼（Huffman）树和哈夫曼编码........................................（151）?
          4.5.4  本节试题精选...............................................................................（153）?
          4.5.5  答案与解析...................................................................................（156）?
      第5章  图........................................................................................................（164）?
5.1  图的基本概念.......................................................................................................（164）?
          5.1.1  图的定义.......................................................................................（164）?
          5.1.2  本节试题精选................................................................................（168）?
          5.1.3  答案与解析.....................................................................................（169）?
5.2  图的存储及基本操作............................................................................................（171）?
          5.2.1  邻接矩阵法....................................................................................（171）?
          5.2.2  邻接表法.......................................................................................（173）?
          5.2.3  图的基本操作.................................................................................（174）?
          5.2.4  本节试题精选................................................................................（175）?
          5.2.5  答案与解析....................................................................................（177）?
5.3  图的遍历.............................................................................................................（180）?
          5.3.1  广度优先搜索（Breadth First Search， BFS）.........................（180）?
          5.3.2  深度优先搜索（Depth First Search， DFS）..........................（182）?
          5.3.3  图的遍历与图的连通性..............................................................（183）?
          5.3.4  本节试题精选.............................................................................（184）?
          5.3.5  答案与解析................................................................................（186）?
5.4  图的应用............................................................................................................（191）?
          5.4.1  最小生成树（Minimum Spanning Tree， MST）..................（191）?
          5.4.2  最短路径...................................................................................（194）?
          5.4.3  拓扑排序....................................................................................（197）?
          5.4.4  关键路径..................................................................................（199）?
          5.4.5  本节试题精选.............................................................................（200）?
          5.4.6  答案与解析................................................................................（204）?
      第6章  查  找............................................................................................（214）?
6.1  查找的基本概念..............................................................................................（214）?
6.2  顺序查找和折半查找........................................................................................（215）?
          6.2.1  顺序查找....................................................................................（215）?
          6.2.2  折半查找....................................................................................（217）?
          6.2.3  分块查找.................................................................................（219）?
          6.2.4  本节试题精选..........................................................................（220）?
          6.2.5  答案与解析...............................................................................（222）?
6.3  B树和B+树....................................................................................................（227）?
          6.3.1  B树及其基本操作.................................................................（227）?
          6.3.2  B+树基本概念........................................................................（230）?
          6.3.3  本节试题精选.........................................................................（231）?
          6.3.4  答案与解析............................................................................（232）?
6.4  散列(Hash)表..............................................................................................（236）?
          6.4.1  散列表的基本概念..............................................................（236）?
          6.4.2  散列函数的构造方法...........................................................（236）?
          6.4.3  处理冲突的方法...........................................................（237）?
          6.4.4  散列查找及性能分析....................................................（238）?
          6.4.5  本节试题精选.............................................................（239）?
          6.4.6  答案与解析..................................................................（242）?
      第7章  排  序............................................................................（248）?
7.1  排序的基本概念..............................................................................（249）?
          7.1.1  排序的定义..............................................................（249）?
          7.1.2  本节试题精选..........................................................（249）?
          7.1.3  答案与解析............................................................（250）?
7.2  插入排序......................................................................................（250）?
          7.2.1  直接插入排序.......................................................（250）?
          7.2.2  折半插入排序.......................................................（251）?
          7.2.3  希尔排序..............................................................（252）?
          7.2.4  本节试题精选.......................................................（253）?
          7.2.5  答案与解析...........................................................（255）?
7.3  交换排序....................................................................................（256）?
          7.3.1  冒泡排序.............................................................（256）?
          7.3.2  快速排序.............................................................（257）?
          7.3.3  本节试题精选.....................................................（259）?
          7.3.4  答案与解析........................................................（261）?
7.4  选择排序..................................................................................（266）?
          7.4.1  简单选择排序...................................................（266）?
          7.4.2  堆排序................................................................（267）?
          7.4.3  本节试题精选...................................................（270）?
          7.4.4  本节试题精选.....................................................（271）?
7.5  归并排序和基数排序...............................................................（275）?
          7.5.1  归并排序...........................................................（275）?
          7.5.2  基数排序...........................................................（277）?
          7.5.3  本节试题精选....................................................（277）?
          7.5.4  答案与解析.........................................................（278）?
7.6  各种内部排序算法的比较及应用.............................................（279）?
          7.6.1  内部排序算法的比较..........................................（279）?
          7.6.2  内部排序算法的应用..........................................（280）?
          7.6.3  本节试题精选.......................................................（281）?
          7.6.4  答案与解析.........................................................（282）?
7.7  外部排序....................................................................................（284）?
          7.7.1  外部排序的基本概念..........................................（285）?
          7.7.2  外部排序的方法...................................................（285）?
          7.7.3  多路平衡归并与败者树........................................（286）?
          7.7.4  置换-选择排序（生成初始归并段）...................（288）?
          7.7.5  最佳归并树............................................................（289）?
          7.7.6  本节试题精选.........................................................（290）?
          7.7.7  答案与解析...........................................................（291）?
      参考文献...................................................................................（294）?