第一部分 数据结构
【复习方法】
09年的统考大纲对数据结构的考查目标定位为理解数据结构的基本概念,掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现;掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析;能够选择合适的数据结构和方法进行问题求解。这个考查目标跟以往各个学校的考研大纲的考查目标并没有什么实质性的区别,这说明数据结构科目考查的指导思想并没有发生变化,同学们可以在不影响已有复习成果的基础上继续进行复习计划,只是在数据结构的考点有了些调整。
从考试大纲来看,所要求的知识在一般的大学数据结构教材中都已经包含,所以,选择哪本书并不是最重要的事情。建议对于数据结构的复习,可以选择清华大学出版社的《数据结构(第二版)》(严蔚敏主编)。这本书有多种语言的版本,建议选择C语言的版本,在复习的过程中,还可以配以相应的习题集进行练习,来加深对知识点的理解。
对于数据结构的学习,难在其中的算法及实现。有条件的考生,可以在计算机上编写程序,自己实现教材上的算法(要注意,书上的算法通常都采用伪代码编写,需要我们自己用某种程序设计语言去具体实现)。数据结构的核心就是算法,首先必须理解经典算法,然后才能创造性的发明简单的算法解决遇到的问题。所以不管是上机实现,还是在纸上写出来,都一定要注意规范性和程序的一些基本规范,这个对于应试是非常重要的。
【考纲考查目标】
1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。
2.掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。
3.能够选择合适的数据结构和方法进行问题求解。
一、线性表
(一)线性表的定义和基本操作
(二)线性表的实现
1.顺序存储结构
2.链式存储结构
3.线性表的应用
二、栈、队列和数组
(一)栈和队列的基本概念
(二)栈和队列的顺序存储结构
(三)栈和队列的链式存储结构
(四)栈和队列的应用
(五)特殊矩阵的压缩存储
三、树与二叉树
(一)树的概念
(二)二叉树
1.二叉树的定义及其主要特征
2.二叉树的顺序存储结构和链式存储结构
3.二叉树的遍历
4.线索二叉树的基本概念和构造
5.二叉排序树
6.平衡二叉树
(三)树、森林
1.书的存储结构
2.森林与二叉树的转换
3.树和森林的遍历
(四)树的应用
1.等价类问题
2.哈夫曼(Huffman)树和哈夫曼编码
四、 图
(一)图的概念
(二)图的存储及基本操作
1. 邻接矩阵法
2. 邻接表法
(三)图的遍历
1. 深度优先搜索
2. 广度优先搜索
(四)图的基本应用及其复杂度分析
1. 最小(代价)生成树
2. 最短路径
3. 拓扑排序
4. 关键路径
五、查找
(一)查找的基本概念
(二)顺序查找法
(三)折半查找法
(四)B-树
(五)散列(Hash)表及其查找
(六)查找算法的分析及应用
六、内部排序
(一)排序的基本概念
(二)插入排序
1. 直接插入排序
2. 折半插入排序
(三)气泡排序(bubble sort)
(四)简单选择排序
(五)希尔排序(shell sort)
(六)快速排序
(七)堆排序
(八)二路归并排序(merge sort)
(九)基数排序
(十)各种内部排序算法的比较
(十一)内部排序算法的应用












