如何备考数据结构

如何备考数据结构？一、考试大纲概况

二、复习重点难点

三、复习规划建议

一、考试大纲概况

二、复习重点难点

三、复习规划建议

大纲要求：

考生比较系统地掌握专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。统考：数据结构45分自主命题：绝大多数院校的考核科目数据结构课程考查目标：1.掌握数据结构的基本概念、基本原理和基本方法。2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3.能够数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++或JAVA语言设计与实现算法的能力。

一、考试大纲概况

二、复习重点难点

三、复习规划建议

复习要点1.数据结构基础知识。2.从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握线性表、栈、队列、数组、树和二叉树、图等常用的数据结构。3.掌握在各种常用的数据结构上实现查找和排序运算，从基本思想、具体算法描述、性能等方面掌握不同的查找、内部排序方法，还需注意不同查找方法和不同排序方法之间的比较。具体章节：

(1)绪论

(2)线性表

(3)栈、队列和数组

(4)树与二叉树

(5)图

(6)查找

(7)排序第1章绪论对后续章节的学习非常重要，其中时间复杂度和空间复杂度的分析是考查的重点，并可以结合后续内容进行考查。本章常考点：算法的性能分析，主要包括时间复杂度和空间复杂度的分析，是数据结构课程教学的基本要求，常以选择题的形式单独出现，另外在算法设计题中也会涉及到。应试技巧与方法：对于算法的时间复杂度分析的考核，需要考生注意两点：第一，需要理解并记住教材中经典算法的时间复杂度；第二，会分析简单算法的时间复杂度。第2章线性表

对于线性结构乃至整个数据结构课程的学习都是非常重要的，是进行算法设计的基础。本章重点是顺序表和链表上实现的各种基本算法及相关的时间和空间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储结构(1)线性表的顺序存储结构，靠元素存储的先后位置反映出数据元素的逻辑关系。(2)用一维数组表示，给定下标，可以存取相应元素，属于随机存取结构。(3)线性表的顺序存储结构实现插入、删除、定位等运算的算法。2.链式存储结构(1)线性表的链式存储结构，靠指针来反映数据元素的逻辑关系。(2)链表的存取需要从头指针开始，顺链而行，不属于随机存取结构，而是顺序存取结构。(3)几种常用链表的特点和相关算法设计，即单链表、单循环链表、双向链表、双向循环链表的生成、检索、插入、删除、遍历、逆置、分解、归并等操作。(4)从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点及其各自适用的场合。3.线性表的应用运用顺序表和链表的特点解决复杂的应用问题。本章常考点：顺序表、链表应用的综合应用题，主要是以算法设计题的形式出现。应试方法与技巧：算法设计题是很多考生的软肋，对这个题目如何备考？建议：1、需要熟练掌握顺序表、链表的基本操作的实现；2、考生应该清楚“复杂的操作都是由一种或几种基本操作的组合来实现的”，因此对于这些复杂的操作首先要分析它是由哪些基本操作实现的；3、考试时，如果不具备拿全部分值的能力，就要考虑如何尽可能拿到较多的部分分值，也就是说，题目中“时间和空间上尽可能高效的算法”这一点要求，考生若不能写出最优的算法或是花费时间过长而影响后面题目的作答时间，那么次优的或者较笨的算法能写出来也会拿到部分分值；4、当然需要考生平时也多积累算法设计的经验。本章对于整个数据结构课程的学习都非常重要，是进行算法设计的基础。第3章栈、队列和数组栈和队列是受限运算的线性表，数组是数据元素为线性表的线性表。本章是考研的重点之一。本章的重点是掌握栈和队列在两种存储结构上实现的基本运算、多维数组的存储方式、矩阵的压缩存储方式。（一）栈和队列的基本概念栈、队列的定义及其相关数据结构的概念，栈与队列存取数据的特点。（二）栈和队列的顺序存储结构1.顺序栈的进栈和退栈的算法，判断栈空、栈满的条件。2.顺序队列的入队和出队的算法，特别是循环队列的入队和出队算法以及判断队空、队满的条件。（三）栈和队列的链式存储结构

1.链栈上的进栈和退栈的算法，注意因栈在一端操作，故通常链栈不设头结点。2.链队列的入队和出队的算法，注意对仅剩一个元素的链队列删除元素时的处理。（四）栈和队列的应用

1.在程序设计中，常需要栈这样的数据结构，使得与保存数据时相反顺序来使用这些数据。2.在后续章节中多处有栈和队列的应用。（五）特殊矩阵的压缩存储

1.数组（主要是二维）在以行序为主和列序为主的存储中的地址计算方法。2.特殊矩阵（对称矩阵、对角矩阵、三角矩阵）在压缩存储时的下标变换公式。本章常考点：栈和队列的定义、基本操作及应用，主要是以选择题的形式出现。其中某些应用题虽然涉及到了特殊矩阵的压缩存储问题，但重点不在此，而是其他。应试方法与技巧：栈的先进后出和队列的先进先出的操作特性，几乎每年必考，题目比较灵活。第4章树和二叉树主要内容有二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等。本章重点是二叉树的遍历算法及其有关应用，难点是使用有关知识设计出有效算法解决与树或二叉树相关的应用问题。（一）树的概念

（二）二叉树

1.二叉树的定义及其主要特征

（1）理解二叉树与普通双分支树的区别；（2）满二叉树和完全二叉树的概念；（3）二叉树的五个性质及其证明方法，以及这些性质的推广。2.二叉树的顺序存储结构和链式存储结构

3.二叉树的遍历

（1）二叉树的先序，中序和后序遍历算法以及按层次遍历。（2）遍历是基础，在三种基本遍历算法的基础上实现二叉树的其它算法。4.线索二叉树的基本概念和构造

（三）树、森林

1.树的存储结构2.森林与二叉树的转换

3.树和森林的遍历

（四）树的应用

1.二叉排序树

二叉排序树的定义及建立、查找、插入、删除等算法。2.平衡二叉树

平衡二叉树的定义及平衡二叉树的四种调整方式。3.哈夫曼（Huffman）树和哈夫曼编码

本章常考点：二叉树的性质及推广、二叉树的遍历、线索二叉树、森林和二叉树的转换、二叉排序树、平衡二叉树、哈夫曼树和哈夫曼编码。应试方法与技巧：树和二叉树的相关知识比较零散，又都很重要。虽然已有的统考题中本章全部以选择题的考核形式出现，但是本章完全可以出综合题，例如：二叉树遍历的应用以算法设计题的形式出现，哈夫曼树和哈夫曼编码也可以以算法应用题的大题形式考核，希望广大考生对于本章内容要充分重视。第5章图图形结构是最具有普遍性的数据结构，树形结构可以看成是图形结构的特例，而线性结构可以看成是树形结构的特例，因此图形结构的算法设计难度最大。本章重点是在图的两种存储结构上实现的遍历算法。本章难点是图的应用算法：最小生成树、拓扑排序、关键路径、最短路径，要求掌握这些算法的基本思想及时间空间性能。（一）图的概念

图的定义和特点、无向图、有向图、入度、出度、完全图、生成树、路径、路径长度、回路、（强）连通图、（强）连通分量等概念。（二）图的存储及基本操作

1.邻接矩阵法

2.邻接表法

（三）图的遍历

1.深度优先搜索

2.广度优先搜索

（四）图的基本应用及其复杂度分析

1.最小（代价）生成树

2.最短路径

3.拓扑排序

4.关键路径

本章常考点：图的概念及相关术语的理解、图的存储及遍历、以及基本上每年都考的图的4个基本应用（最小生成树、最短路径、拓扑排序、关键路径）。应试方法与技巧：图的基本概念和性质主要是以选择题的形式考核，对于图的这4个应用，要求掌握算法（Prim算法、Kruskal算法、Dijsktra算法、Floyd算法、拓扑排序算法和关键路径算法）的基本思想，一般不要求写出具体算法，但是需要能用这些算法思想来求解具体题目，因此，这些算法要深刻理解。第6章查找查找指的是按关键字查找，它与数据组织方式和关键字顺序有关。数据组织方式有线性表、树表和散列表，关键字顺序存在有序和无序之分。本章重点掌握顺序查找、二分查找以及散列表上查找的基本思想和算法实现。（一）查找的基本概念

（二）顺序查找法

采用顺序查找方法，逐个比较，设置监视哨使查找效率大大提高。（三）折半查找法

对于有序顺序表采用折半查找法，其判定树是唯一的。注意该方法的适用条件以及其递归实现方法。（四）B树及其基本操作、B+树的基本概念B-树是多路平衡外查找树，用于文件系统。B+树是应文件系统所需而产生的一种B树的变形树。（五）散列表

散列函数的设计、处理冲突的方法、散列表的查找及分析。（六）查找算法的分析及应用本章常考点：折半查找法及性能分析、B树的定义及其基本操作、散列表的查找及性能分析。应试方法与技巧：顺序查找法比较简单，折半查找比较重要，需掌握折半查找的适用条件、折半查找算法和查找过程、判定树的构造、查找长度分析等。B树和B+树是本章难点，一般不要求掌握算法，对于B树要求能够执行插入、删除和查找操作，对于B+树，仅需了解基本概念和性质即可。散列查找也比较重要，容易出综合题。第7章排序排序指的是按关键字有序排列数据表中的记录，和查找一章不同，这里关键字可以重复出现。为了简单，设定排序的数据采用线性表方式进行组织，并且递增排序。本章重点是快速排序、堆排序、归并排序和基数排序的基本思想及排序过程，难点是这四个排序算法的实现。

另外统考的同学注意外部排序。（一）排序的基本概念

（二）插入排序

1.直接插入排序

2.折半插入排序

（三）起泡排序

（四）简单选择排序

（五）希尔排序

（六）快速排序

（七）堆排序

（八）二路归并排序

（九）基数排序（十）外部排序（十一）

各种内部排序算法的比较各种排序方法的算法思想、排序过程、算法实现以及性能分析（包括时间复杂度、空间复杂度、稳定性）。（十二）排序算法的应用本章常考点：各种排序的算法思想、排序过程、性能分析及各种排序方法的综合比较。应试方法与技巧：本章最常见的出题方式是给定一个数据序列，要求选出其所用的排序方法；或给定一个数据序列，求用某种排序方法一次排序后所得序列。因此，对于每一种排序需要从以下四个方面掌握：（1）理解算法的基本思想；（2）该排序算法的手工排序过程；（3）算法描述；（4）算法性能：时间复杂度（最好、最坏、平均），空间复杂度，稳定性。一、考试大纲概况

二、复习重点难点

三、复习规划建议

第一阶段：基础复习阶段(开始复习—7月)第二阶段：强化提高阶段(8月—11月初)第三阶段：冲刺阶段(11月－考前)第一阶段：基础复习阶段(开始复习—7月)阶段目标：对指定参考书目通读一遍，对考试情况有个基本的印象。细读一遍参考书目，理解书中的每一个知识点。对各门课程有深入了解，弄清每本书的大纲，内在逻辑结构，重点章节所在等，但不要求记住。1．细读一遍参考书，指的是对参考书每个知识点的彻底理解，要注意复习的全面性。2．本阶段学习重在理解，不在强记。3．每本书每章节学完后要做到能闭上眼在脑海中列出一个知识点的提纲，这样可以方便以后对需要记忆的内容进行复习。4．注意把握复习进度，不要拖，有不懂的要尽快和同学老师交流，避免拖慢整个复习进度。5．如果复习过程中有条件，可以有选择地去听学校开设的相关专业课程或翻看相关课件，加深印象。

第二阶段：强化提高阶段(8月—11月初)阶段目标：对指定参考书进行深入复习，加强知识点的前后联系，建立整体框架结构。分清、整理、掌握重难点，完成参考书配有的习题训练。做历年真题，弄清考试形式、题型设置和难易程度等内容，整理真题答案。8月：要关注新出台的本年度招生简章和专业目录，与往年的情况进行对比，新增考点往往是出题点，删改了的考点可以在复习过程中节省复习时间。9-10月：研究生开始网上报名，谨慎填报志愿，牢记自己的报名信息。11月：研究生考试报名确认工作开始，考生到指定的地点进行现场确认，缴费并照相。（一）参考书深入复习计划1.将参考书中的概念、原理要注意理解记忆，书中的例题要做会。2.完成相关的课后习题，要在纸面上按照考试要求一步步写出解答过程，加深解题思路的印象，提升解题速度。3．把书上可能考到的名词解释、问答、论述等文字性的题目都整理在笔记本上。4．将全书的重点归纳成一系列的知识点，一定要有系统性。这样做的好处是加深印象，并且对知识有更加系统的理解。5.通过相关习题分析，总结知识点的出题方向，特别是对于大题，应融会贯通，举一反三。（二）历年真题学习计划做历年真题，整理真题答案。试做真题，弄清每一道题属于书中的哪一章、哪个知识点。通过做真题要了解考试形式、考试重点、题型设置和难易程度等内容，揣摩出题人思路。整理所有真题的答案。真题答案一定要完整。整理过程中，每道真题，尤其是比较复杂的计算/分析题目要多做几遍。第三阶段：冲刺阶段(11月－考前)阶段目标：总结所有重点知识点，包括重点概念、理论和模型等，查漏补缺，回归教材。温习专业课笔记和历年真题，分析真题的