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

《年考研计算机数据结构强化班讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、统考计算机考研--数据结构强化提高班目录考情分析3重难点解析4第1章绪论4一、知识点归纳4二、重、难点内容解析5第2章线性表5一、知识点归纳5二、重、难点内容解析6第3章栈、队列和数组8一、知识点归纳8二、重、难点内容解析9第4章树与二叉树12一、知识点归纳12二、重、难点内容解析13第5章图18一、知识点归纳18二、重、难点内容解析18第6章查找23一、知识点归纳23二、重、难点内容解析24第7章排序26一、知识点归纳26二、内容提要27真题解析302012年302011年342010年372009年41总结4

2、5考情分析1、历年考试分值分布情况　知识点2009年2010年2011年2012年总计时间、空间复杂度计算00224线性表的综合应用1513151356栈与队列的概念、细节、应用444416矩阵的压缩存储00涉及一点0二叉树的定义（特殊）262212树、二叉树的性质22408二叉树的遍历20226树、森林与二叉树的转换20002二叉树的应用0001010图的基本概念22228图的存储结构008（应用）2（应用）10图的遍历00022图的应用1028（存储）4（存储）24静态查找表02002B树20024Hash表

3、0102012排序4444162、考试分析（1）统考以来，考试的题型、题量、分值变化情况总结；自从2009年计算机统考以来，数据结构课程知识点在计算机专业综合统考试卷中所占分值均为45分，题型为单向选择题和综合应用题，除了2009年外（10道选择题20分、2道综合应用题25分），每年都是11道选择题22分、2道综合应用题23分。（2）统考以来，考核的知识点变化情况分析；统考四年来，虽然每年考研大纲都有所变化，但是变化的很小，2013新考纲出来之后，我们仔细对照一下即可，现在只需要对照2012年考纲按部就班的准备就

4、行了。讲义中所涉及所有的知识点，考生务必掌握。（3）对未来考试的分析与预测；通过对四年考卷的分析，可以看出，题型、题量基本不变，唯一变化的就是分值在各知识点之间的分布。从命题的角度看，该课程比较成熟并且题目繁多，所以考生如果不注意复习方法，仅凭自己在课堂上学到的知识，在课下不进行系统的学习和精心的总结，即使平时感觉良好的考生，在应考的时候也往往失利。考生在数据结构课程的备课过程中，首先要对本门课程有个全局的把握，然后对各个知识点逐一击破即可。另外，理解学习本门课程的基本要求，不要压题。重难点解析本门课程的知识架构

5、第1章绪论一、知识点归纳内容要求基本概念理解算法的度量方法理解、掌握本章内容如图1.1所示。图1.1本章知识归纳图二、重、难点内容解析（一）基本概念数据、数据元素、数据项、数据对象、逻辑结构、存储结构、数据结构等（二）算法1、算法的定义2、算法的特性3、算法设计的要求4、算法的度量。度量算法有两个标准，时间复杂度和空间复杂度。时间复杂度也称渐进时间复杂度，记着：T(n)=O(f(n))，含义是随着问题规模n的增大，算法执行时间的增长率和f(n)增长率相同。f(n)求解过程：①、选择一个所谓的元操作，一般来说被循环

6、语句包的最深的操作可以作为原操作；②、计算频度，得到一个关于问题规模n的表达式；③、提取支配项。空间复杂度主要用来刻画某算法对应的程序要想在计算机上执行，除了需要内存空间来存储程序代码和输入的数据外，还需要的额外空间，一般记着S(n)=O(f(n))，这里f(n)的求法与时间复杂度类似。另外，如果f(n)是一个常数，则可称该算法原地工作。第2章线性表一、知识点归纳内容要求线性表的概念了解顺序存储结构理解并掌握链式存储结构理解并掌握线性表的应用综合应用本章内容如图2.1所示。图2.1本章知识归纳图二、重、难点内容解

7、析（一）线性结构（线性表）一个线性表是n个数据元素的有序序列。这n个数据元素应该是性质相同的，或者说对每个元素的操作方式是一样的，例如，一个班的学生可以组成一个线性表，而学生和飞机组成线性表的意义不大。线性表是最简单最常用的一种数据结构。一般来说，在线性表上进行的操作主要有遍历、插入、删除、修改、查找（有时也会依赖遍历），其中遍历操作是最重要的操作，自从全国统考以来，每年都是以综合应用题的形式考查。当然，对于同一个线性表的同一操作，不同的存储结构对应的实现细节也是有区别的。（二）顺序表顺序表即线性表的顺序表示，就

8、是用一组地址连续的内存单元依次存储线性表的各个元素。存储示意图如图2.2所示。图2.2顺序表的存储示意图高级程序设计语言中一般都有用来描述结构的工具，以C语言为例，它就是用结构体来实现存储结构的，如表2.1所示。表2.1顺序表的Ｃ语言实现方法动态顺序存储结构静态态顺序存储结构typedefstruct{ElemType*elem;intlength;intlistsize