2012考研计算机数据结构强化班讲义PPT

考研强化班考研强化班计算机数据结构计算机—数据结构考试知识框架和结构考试知识框架和结构ƒ“数据结构”是计算机学科专业基础的重要组成部分之一，所涉及的基础知识、基本理组成部分之一，所涉及的基础知识、基本理论、基本方法是从事计算机学科研究和研究生学习阶段必须掌握的基本内容。在计算机生学习阶段必须掌握的基本内容。在计算机科学与技术学科硕士研究生入学专业联考的150分中占45分。150分中占45分。考试知识框架图考试知识框架图线性表数据结构栈、队列和数组结构知识结构树与二叉树结构图查找内部排序“数据结构”的考察目标数据结构”的考察目标1理解掌握数据结构的基本概念、基本原理ƒ1.理解掌握数据结构的基本概念、基本原理和基本方法；ƒ2.掌握数据的逻辑结构、存储结构及其差异及基本操作的实现，能够对算法进行基本的及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析；ƒ3能够选择合适的数据结构和方法进行运用ƒ3.能够选择合适的数据结构和方法进行运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C++或Java语言设计与求解，具备采用C、C++或Java语言设计与实现算法的能力。考察目标文字的变化考察目标文字的变化ƒ(1)只有考查目标部分有较大变化、考察内容没有变化ƒ(1)只有考查目标部分有较大变化、考察内容没有变化。y基本知识体系不变基本知识体系不变ƒ(2)数据结构由理解变为掌握，新增了对基本原理和基(2)数据结构由理解变为掌握，新增了对基本原理和基本方法的要求。ƒ(3)去掉了对数据的逻辑结构、存储结构的差异的考查。。ƒ(4)新增了运用数据结构基本原理分析问题的要求。ƒ(4)新增了运用数据结构基本原理分析问题的要求。考察目标内容的变化考察目标内容的变化1、考查目标中“具备采用C或C或JAVA语ƒ1、考查目标中“具备采用C或C++或JAVA语言设计与实现算法的能力”表示对实际编程能力的要求和考察，可以看出研究生入学考能力的要求和考察，可以看出研究生入学考试对知识实际应用能力的强调。当然，考生也不必因此而专门复习一遍或程序设计也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。有任何语法错误的程序。2012年考察目标分析2012年考察目标分析理解变掌握ƒ理解变掌握y可能会考某个数据结构上基本操作的实现可能会考某个数据结构上基本操作的实现知识覆盖点及难度不增加，综合应用能力得ƒ知识覆盖点及难度不增加，综合应用能力得到加强，可能出现设计编程的综合应用题型或者融合多科目的综合题型（比如写出基于某数据结构的操作系统的某个算法），加大某数据结构的操作系统的某个算法），加大能力考查。考情分析考情分析历年考试分值分布情况ƒ历年考试分值分布情况知识点2009年2010年2011年平均线性表2423栈、队列和数组10144+15/212树与二叉树10968树与二叉树109图1242+89查找71227查找71227内部排序444+15/26考试分析考试分析年考核的知识点主要是：栈、队列和数组、ƒ09年考核的知识点主要是：栈、队列和数组、树与二叉树、图。树与二叉树、图。ƒ10年考核的知识点主要是：栈、队列和数组、树与二叉树、查找。对比分值的变化，主要树与二叉树、查找。对比分值的变化，主要在综合应用题第一题的变化。ƒ11年考核定重点是栈、队列和数组、图、排序（查找）。决定分值分布的主要是综合应序（查找）。决定分值分布的主要是综合应用题第一题。考试分析考试分析ƒ各年综合应用题第二大题均是算法的题目，直接使用的知识是较简单的数据结构（栈、直接使用的知识是较简单的数据结构（栈、队列和数组），兼顾时空效率的查找或排序算法的简单修改或延伸。算法的简单修改或延伸。ƒ2012大家多看看树的算法。ƒ综上所述，数据结构中，大家要重视栈、队列和数组、树与二叉树的复习，明年的考试列和数组、树与二叉树的复习，明年的考试中，这些仍是高频考点。考研大纲解析考研大纲解析考试知识框架和结构ƒ考试知识框架和结构y“数据结构”是计算机学科专业基础的重要组成“数据结构”是计算机学科专业基础的重要组成部分之一，所涉及的基础知识、基本理论、基本方法是从事计算机学科研究和研究生学习阶段必方法是从事计算机学科研究和研究生学习阶段必须掌握的基本内容。在计算机科学与技术学科硕士研究生入学专业联考的150分中占45分。士研究生入学专业联考的分中占分。2012年考察目标预测2012年考察目标预测ƒ知识覆盖点及难度不增加，综合应用能力得到加强，可能出现设计编程的综合应用题型到加强，可能出现设计编程的综合应用题型或者融合多科目的综合题型（比如写出基于某数据结构的操作系统的某个算法），加大某数据结构的操作系统的某个算法），加大能力考查。综合应用题可能涉及树。ƒ综合应用题可能涉及树。大纲与考点分析大纲与考点分析ƒ通过对大纲的分析，得出考点与重点，针对性进行复习性进行复习大纲-线性表大纲-线性表线性表部分由于比较简单，又是整个数据结构的基ƒ线性表部分由于比较简单，又是整个数据结构的基础，所以考察的内容会比较细致。对于线性表灵活运用的程度要求较高。复习时，应充分理解线性表运用的程度要求较高。复习时，应充分理解线性表的顺序存储，链式存储(单链表、静态链表、循环链表、双向链表)。熟练掌握初始化、插入、删除等基表、双向链表)。熟练掌握初始化、插入、删除等基本操作。此部分，有可能出大题的地方：集合求并、一元多项式求和。、一元多项式求和。大纲-线性表大纲-线性表ƒ2010y(二)线性表的实现(二)线性表的实现1.顺序存储结构2.链式存储结构链式存储结构3.线性表的应用ƒ2011y(二)线性表的实现1.顺序存储2.链式存储大纲-线性表大纲-线性表（一）线性表的定义和基本操作ƒ（一）线性表的定义和基本操作ƒ（二）线性表的实现y1.顺序存储y2.链式存储链式存储大纲-线性表大纲-线性表考点ƒ考点y线性表是一种最简单的数据结构，在线性表方面线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。尽管大纲特别是链式存储结构，是考查的重点。尽管大纲没有提存储结构，但具体实现还是要根据存储结构来定的。构来定的。大纲-栈、队列和数组大纲-栈、队列和数组栈、队列和数组时数据结构的重要工具，考查重点ƒ栈、队列和数组时数据结构的重要工具，考查重点偏向于应用。对于具体的定义的方式简单清楚就可以，重点是理解栈、队列的特点，熟练掌握栈、队以，重点是理解栈、队列的特点，熟练掌握栈、队列的一些经典的应用，在应用题中，常常会用到栈、队列数组作为工具。、队列数组作为工具。大纲-栈、队列和数组大纲-栈、队列和数组ƒ（一）栈和队列的基本概念（一）栈和队列的基本概念ƒ（二）栈和队列的顺序存储结构ƒ（二）栈和队列的顺序存储结构ƒ（三）栈和队列的链式存储结构ƒ（四）栈和队列的应用ƒ（五）特殊矩阵的压缩存储（五）特殊矩阵的压缩存储大纲-栈、队列和数组大纲-栈、队列和数组考点ƒ考点y栈和队列是两种特殊的线性表，在这方面，要求栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。大纲-栈、队列和数组大纲-栈、队列和数组考点ƒ考点y一维数组属于线性表范畴，但多维数组不属于线一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。理也要搞清楚。大纲-树与二叉树大纲-树与二叉树ƒ树是数据结构最重要的部分，它的内容纷繁而复杂，但又尤为重要，是复习的重中之重而复杂，但又尤为重要，是复习的重中之重。对于树的复习方法，要重点掌握树的遍历，树的任何操作，其实都是以遍历为基础，，树的任何操作，其实都是以遍历为基础，稍加改动visit函数而已。大纲-树与二叉树大纲-树与二叉树（一）树的基本概念ƒ（一）树的基本概念ƒ（二）二叉树y1.二叉树的定义及其主要特征y2.二叉树的顺序存储结构和链式存储结构二叉树的顺序存储结构和链式存储结构y3.二叉树的遍历y4线索二叉树的基本概念和构造y4.线索二叉树的基本概念和构造大纲-树与二叉树大纲-树与二叉树ƒ（三）树、森林（三）树、森林y1.数的存储结构2森林与二叉树的转换y2.森林与二叉树的转换y3.树和森林的遍历ƒ（四）树与二叉树的应用ƒ（四）树与二叉树的应用y1.二叉排序树平衡二叉树y2.平衡二叉树y3.哈夫曼（Huffman）树和哈夫曼编码大纲-树与二叉树大纲-树与二叉树考点ƒ考点y二叉树和树是两种不同的概念，这一点是必须要二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的前序遍历、中序遍历、后序遍历)就是一种典型的应用。大纲-树与二叉树大纲-树与二叉树考点ƒ考点y在特殊的二叉树中，完全二叉树的概念是必须在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。能很好地理解。多棵独立的树就组成了森林，树的存储结构和y多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有所了解。和二叉树的转换等知识，也要有所了解。大纲-树与二叉树大纲-树与二叉树考点ƒ考点y最后就是树的应用，通常会作为综合应用类试题最后就是树的应用，通常会作为综合应用类试题出现，包括哈夫曼(Huffman)树和哈夫曼编码等。。大纲-图大纲-图图的概念比较多，没有基本概念的基础，是很难把ƒ图的概念比较多，没有基本概念的基础，是很难把知识掌握清楚的。解决图的问题，很多时候是借助树和二叉树来实现的，应注意树、二叉树和图之间树和二叉树来实现的，应注意树、二叉树和图之间的对应关系。此部分出大题的可能性很高。要重视用人名来命名的算法，这类算法是为了纪念作者而用人名来命名的算法，这类算法是为了纪念作者而命名的，可见其经典性，这类算法也相当有难度，考试时，不仅仅只会就此算法稍加改动，会应用算考试时，不仅仅只会就此算法稍加改动，会应用算法的思想来命题。大纲-图大纲-图ƒ2010y（一）图的概念（一）图的概念2011ƒ2011y（一）图的基本概念y为了和其他章相匹配大纲-图大纲-图（一）图的基本概念ƒ（一）图的基本概念ƒ（二）图的存储及基本操作y1.邻接矩阵法y2.邻接表法邻接表法（三）图的遍历ƒ（三）图的遍历y1.深度优先搜索y2.广度优先搜索大纲-图大纲-图（四）图的基本应用ƒ（四）图的基本应用y1.最小（代价）生成树y2.最短路径y3.拓扑排序y4.关键路径大纲-图大纲-图ƒ考点考点y在数据结构中，图的结构是最复杂的，这里的概念也是最多的。我们要掌握图的基本概念(有概念也是最多的。我们要掌握图的