2015河南工业大学081201数据结构考研大纲
数据结构考研大纲【考查目标】1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。2.掌握基本的数据处
【知识点解析】
1.线性表
线性表是一种最简单的数据结构,在线性表方面,主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面,要掌握的是线性表的存储结构,包括顺序存储结构和链式存储结构,特别是链式存储结构,是考查的重点。另外,还要掌握线性表的基本应用。
2.栈、队列和数组
栈和队列是两种特殊的线性表,在这方面,要求我们掌握栈和队列的基本概念,以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解,对于栈和队列的应用,例如,排队问题、子程序调用问题、表达式问题等,要搞清楚。
一维数组属于线性表范畴,但多维数组不属于线性表。在这方面,主要掌握数组的存储结构,例如按行优先、按列优先等,某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。
3、树与二叉树
二叉树和树是两种不同的概念,这一点是必须要搞清楚的。在这个部分,我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面,特别是链式存储结构,因为很多应用都是建立在链式存储基础上,例如,二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。
在特殊的二叉树中,完全二叉树的概念是必须要搞清楚的,其次,线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用,特别是二叉排序树的基本性质和特点要能很好地理解。
多棵独立的树就组成了森林,树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识,也要有了了解。
最后就是树的应用,通常会作为综合应用类试题出现,包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。
4、图
在数据结构中,图的结构是最复杂的,这里的概念也是最多的。我们要掌握图的基本概念(有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等)。
图的存储及基本操作主要有邻接矩阵法和邻接表法,我们要掌握这有向图和无向图的这2种存储方法,要清楚图的连通和存储方法之间的关系。例如,一个顶点的出度和临界矩阵中1的个数有什么关系,等等。
图的遍历方法有深度优先搜索和广度优先搜索,我们要掌握这2种遍历方法的算法实现。给出一个具体的图,要能知道它的遍历次序。
在数据结构课程中,图的基本应用是最多的,也是最复杂的,我们要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小(代价)生成树、最短路径、拓扑排序、关键路径。在给出的一个具体的图中,我们要会利用已知条件,求出上述应用的结果。
5、查找
在给定的数据集合中查找某个关键值就是查找,查找的基本方法主要有顺序查找法、折半查找法、B-树、散列(Hash)表及其查找。考的比较多的是折半查找和散列表,我们要掌握它们的基本概念和方法,例如散列表的碰撞如何解决,装载因子的概念等。
另外,我们要掌握各种查找算法的分析及应用,最好能把各种查找在查找成功、查找失败的情况下的最好、平均、最坏的平均查找次数的计算方法搞清楚。
6、内部排序
根据考试大纲,只考查内部排序。所谓内部排序,就是在内存中进行排序。在这一部分中,主要要掌握直接插入排序、折半插入排序、冒泡排序(bubblesort)、简单选择排序、希尔排序(shellsort)、快速排序、堆排序、二路归并排序(mergesort)、基数排序的基本概念和方法。搞清楚这些排序方法的流程,以及它们之间的区别。
在这个知识点,一个很重要的考查点就是各种内部排序算法的比较,一般的书上都会有这样的一个表格,列出了所有排序在各种情况下(最好、最坏、平均)的时间复杂度和空间复杂度,这个表是需要我们记下来的。当然,如果我们能掌握复杂度的计算方法,自己能推算出来,那就更好了。
最后,就是要掌握内部排序算法的基本应用,以及算法的实现。
【复习方法】
1、教材的选择
从考试大纲来看,所要求的知识在一般的大学数据结构教材中都已经包含,所以,选择哪本书并不是最重要的事情。不过,根据希赛教育推荐,对于数据结构的复习,可以选择清华大学出版社的《数据结构(第二版)》(严蔚敏主编)。这本书有多种语言的版本,建议选择C语言的版本,在复习的过程中,还可以配以相应的习题集。
2、学习方法
对于数据结构的学习,难在其中的算法及实现。有条件的考生,可以在计算机上编写程序,自己实现教材上的算法(要注意,书上的算法通常都采用伪代码编写,需要我们自己用某种程序设计语言去具体实现)。如果没有条件,那就只有在心里进行推导了,可以使用实际的例子,手工"实现"算法。
>>>进入院校招生信息专题
【相关链接】
2015年考研招生信息汇总 | 专业课考研大纲 | 学费奖助 | 推荐免试
2015年考研大纲专题 | 2015年考研讨论版 | 2014报录比
- 2021-10-01.........
- 2021-03-01南京财经大学812
- 2020-10-21求国际商务资料
- 2020-07-21美学
- 2022-01-16安师大
- 2020-04-03浙大材料科学基础第1前辈的经验分享十初试复试
- 2020-04-03浙大教育学综合高分学长的经验分享
- 2020-04-03浙大832机械设计基础最新复试初试资料
- 2020-04-03浙大药学基础综合第1学姐的经验分享
- 2020-04-0321浙大法学专业硕士高分学长分享资料