1
数据结构复习重点
申超波
第一章 绪论
这章没有大题，但也有几个小的考点，如下：
(1) 数据结构的几种类型，基本概念；
(2) 数据结构类型和抽象数据类型要理解；
(3) 算法的五个要素及特点；
(4) 评价算法的标准，时间复杂度(每年必考，必须知道评价给定的一段程序的时间复杂度)和空间复杂度(这个无所谓)。
第二，三章 线性表和栈以及队列
这两章应该合在一起，因为栈和队列本身就是特殊的线性表。
复习要点：
（1） 熟悉线性表的概念和特点(理解就行)
（2） 线性表的两种存储结构，即顺序表和链表，能够清楚理解这两种结构的不同之
处，比较优劣。
（3） 能够用伪码写出线性表的创建，插入，删除，合并（非常重要）。
（4） 知道栈的特性，即先进后出，要理解这个特性以及它应用的领域，还要重点掌
握三个操作，出栈(即删除)操作代码及注意判空，进栈(即插入)操作代码及注意判满，求栈当前长度代码。
（5） 知道队列的特性，即先进先出，要理解这个特性以及它应用的领域，还要重点
掌握三个操作，出队列(即删除)操作代码及注意判空，进队列(即插入)操作代码及注意判满，求当前队列长度代码。
第四章 串，数组，广义表
复习要点：
（1） 串：熟悉常见对串操作方法；理解模式匹配算法；理解KMP算法原理，要求
会求模式串的next，以及nextval.
（2） 数组：理解数组的原理及特点，重点掌握矩阵与数组存储之间彼此对应的运算。
（3） 广义表：会求表头，表尾，及深度，可以会可以学会广义表的两种画图表示。
第五章 树和二叉树
全书最最最最重点的一章，考点最多，大题几乎最可能出在这章，所以对这章内容无论如何要吃透。
复习要点：
(1) 二叉树的定义和性质，性质最重要就三点就是要知道边和结点之间的关系，以及度数为0和度数为2的结点关系，已知道结点总数求树的深度或相反。
(2) 遍历二叉树，掌握三种方式的递归代码伪代码，掌握至少一种非递归遍历(书上有) ，掌握二叉树的层次遍历。
(3) 掌握三种线索二叉树构造，理解中序线索二叉树的代码实现过程。
(4) 理解森林的几种存储方式，以及森林与二叉树转换，还有三种遍历的对应关系。
(5) 掌握构造最优哈夫曼树的方法，学会计算及带权路径长度。
第六章 图
这章比较难，但考得不是很深。
复习要点：
(1) 图的定义和性质。
(2) 图的两种常用存储：邻接矩阵和邻接表。
(3) 掌握图的深度优选遍历和广度优先遍历，要求能写出伪代码。
(3) 了解无向图和有向图，连通分量，强连通分量及生成树概念。
(4) 最小生成树的两种算法，要求会写prim算法伪代码 。
(5) 要求会拓扑排序和找关键路径，不要求代码。
(6) 掌握Dijstra算法，熟读代码，可能出代码填空。
这章是仅次与树那章的重点，考点非常多，可以出大题。
复习要点：
(1) 顺序表，有序表，索引表的查找，学会计算这三种查找的代价。
(2) 掌握二叉排序树，平衡二叉树以及B树的构建包括添加，和删除一个结果，不要求代码，还要尤其注意它们的性质。
(3) 掌握哈希表的构造方法，处理冲突的方法，哈希链表的构造方法，及两种哈希表查找失败和成功的代价。
(4) 比较各种排序的特点，包括时间复杂度，空间复杂度，是否稳定等。
(5) 掌握直插，快排，简单排序，堆排的伪代码实现。
第十一章 外排
这章要求很简单，知道外排的三种方式，并会构建最大败子树