2013年考研计算机数据结构冲刺班讲义

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

1、统考计算机专业综合——数据结构冲刺提高班目录一、知识框架体系3二、知识点串讲3三、常考点、易考点总结23四、考试题型讲解27五、考前注意事项33一、知识框架体系本门课程的知识架构如图所示本门课程的重要知识点如下：第一章线性表：线性表的逻辑特性，顺序表与链表的实现方式、操作细节，线性表的综合应用，其中顺序表的操作细节、线性表的综合应用是常考点，统考四年来，每年必考，但是这也是一个难点，因为题目总是要求考生能够对线性表应用尽可能的高效。第二章栈、队列和数组：栈和队列的逻辑特性，栈和队列的存储结构（特别是循环队列），栈和队列的应用，矩阵的压

2、缩存储。其中栈的逻辑特性、循环队列是常考点，操作受限的双端队列是一个难点。第三章树和二叉树：树的基本术语概念、性质（二叉树），二叉树的遍历，二叉树的存储，二叉树的线索化，森林、树与二叉树的转换，特殊二叉树（huffman树、二叉排序树、平衡二叉树）。其中二叉树的五个基本性质、二叉树的遍历、平衡二叉树等是常考点，二叉树的线索化及平衡二叉树的旋转是难点。这些知识点之间有时也会交叉命题，考生也要留意。第四章图：图的基本概念，图的存储结构，图的遍历，图的四个应用（最小生成树、拓扑排序、关键路径、最短路径），这四块内容是图这一章的重要内容，哪一

3、个知识点都很重要，都容易出题，考生要特别留意，尤其是图的存储结构和图的四个应用既可以出主观题也可以出客观题目。当然图的四个应用，考生如果基础不好的话，掌握起来会很费劲，但是不管当时自身情况怎么样，考前一定要将这些知识点都搞清楚。第五章查找：顺序查找，折半查找，B_树的基本概念、查找过程、分裂与合并，B+树的基本概念，哈希表。其中折半查找的查找过程、B_树的结点的分裂与合并、哈希表是常考点，B—树的结点分裂与合并是难点。第六章排序：对于每一种排序方法，考生要从四方面来把握，即排序思想，排序过程，效率分析，稳定性分析，其中排序过程、效率分

4、析、稳定性分析是常考点。对于这么多中排序方法，考生要能够识别，知道每一种排序方法的名字，特别是快速排序、堆排序、希尔排序考生要特别留意。当然有些排序的效率分析比较复杂，利用快速排序、希尔排序等。除此之外，考生对于绪论部分的时空复杂度的问题，也不能掉以轻心。二、知识点串讲绪论部分：除了掌握逻辑结构、存储结构、数据结构、算法、复杂度等基本概念外，还有掌握度量算法有两个标准，时间复杂度和空间复杂度。时间复杂度也称渐进时间复杂度，记着：T(n)=O(f(n))，含义是随着问题规模n的增大，算法执行时间的增长率和f(n)增长率相同。f(n)求解

5、过程：①、选择一个所谓的元操作，一般来说被循环语句包的最深的操作可以作为原操作；②、计算频度，得到一个关于问题规模n的表达式；③、提取支配项。空间复杂度主要用来刻画某算法对应的程序要想在计算机上执行，除了需要内存空间来存储程序代码和输入的数据外，还需要的额外空间，一般记着S(n)=O(f(n))，这里f(n)的求法与时间复杂度类似。另外，如果f(n)是一个常数，则可称该算法原地工作。线性表部分：（一）线性结构（线性表）一个线性表是n个数据元素的有序序列。这n个数据元素应该是性质相同的，或者说对每个元素的操作方式是一样的，例如，一个班的

6、学生可以组成一个线性表，而学生和飞机组成线性表的意义不大。线性表是最简单最常用的一种数据结构。一般来说，在线性表上进行的操作主要有遍历、插入、删除、修改、查找（有时也会依赖遍历），其中遍历操作是最重要的操作，自从全国统考以来，每年都是以综合应用题的形式考查。当然，对于同一个线性表的同一操作，不同的存储结构对应的实现细节也是有区别的。（二）顺序表顺序表即线性表的顺序表示，就是用一组地址连续的内存单元依次存储线性表的各个元素。存储示意图如图2.1所示。图2.1顺序表的存储示意图高级程序设计语言中一般都有用来描述结构的工具，以C语言为例，它

7、就是用结构体来实现存储结构的，如表2.1所示。表2.1顺序表的Ｃ语言实现方法动态顺序存储结构静态态顺序存储结构typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;typedefMAX100;typedefstruct{ElemTypeelem[MAX];intlength;}SqList;（三）链表（存储结构）链表即线性表的链式表示，如图2.2所示，L是头指针，一个普通的指针变量；L之后的第一个结点，称为头结点，它的数据域是空的，没有任何值，指针域是第一个元素所在结点的位

8、置。图2.2单向链表的存储示意图图2.3中结点可以用Ｃ语言的结构体来描述，其中LNode是结点类型，LinkList是结点的地址类型。typedefstructLNode{ElemTypedata;structLNode