2020年陇东学院专升本数据结构考试大纲

2020年陇东学院专升本考试计算机科学与技术专业课数据结构参考教材：

1.《数据结构用C语言描述》(第二版)，耿国华等编写，高等教育出版社，2015年;2.《数据结构》(C语言版)，严蔚敏、吴伟民编著，清华大学出版社，2011年。

一、考试目的

考核普通高等学校专科(含高职)应届毕业生对于《数据结构》课程基本知识掌握是否达到教学大纲所规定的要求。

二、考试要求及内容

第1章 绪论

1、掌握数据、数据元素、数据项、数据结构等基本概念。

2、掌握数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。

3、掌握数据结构的两大类逻辑结构和四种常用的存储表示方法。

4、理解算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。

5、掌握算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。

第2章 线性表

1、理解线性表的逻辑结构特征。

2、理解线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。

线性表的顺序存储结构，要求达到“综合利用”层次。

3、 理解顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。

4、掌握顺序表上的插入、删除操作及其平均时间性能分析。

5、理解利用顺序表设计算法解决简单的应用问题。

6、掌握链表如何表示线性表中元素之间的逻辑关系。

7、掌握链表中头指针和头结点的使用。

8、理解单链表、双链表、循环链表链接方式上的区别。

9、 掌握单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。

10、理解循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。

11、理解双链表的定义及其相关的算法。

12、掌握利用链表设计算法解决简单的应用问题。

13、理解顺序表和链表的主要优缺点。

14、掌握针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。

第3章 栈和队列

1、理解栈的逻辑结构特点，栈与线性表的异同。

2、掌握顺序栈和链栈上实现的进栈、退栈等基本算法。

3、理解栈的“上溢”和“下溢”的概念及其判别条件。

4、掌握利用栈设计算法解决简单的应用问题。

5、理解队列的逻辑结构特点，队列与线性表的异同。

6、掌握顺序队列(主要是循环队列)和链队列上实现的入队、出队等基本算法。

7、理解队列的“上溢”和“下溢”的概念及其判别条件。

8、了解使用数组实现的循环队列取代普通的顺序队列的原因。

9、掌握循环队列中对边界条件的处理方法。

10、掌握利用队列设计算法解决简单的应用问题。

第4章 串

1、掌握串的有关概念及基本运算。

2、理解串与线性表的关系。

3、掌握串的两种存储表示。

4、掌握使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。

第5章 数组和广义表

1、掌握数组的逻辑结构特征。

2、掌握数组的顺序存储结构及地址计算方式。

3、掌握数组是一种随机存取结构的原因。

4、理解特殊矩阵和稀疏矩阵的概念。

5、理解特殊矩阵和压缩存储时的下标变换方法。

6、理解稀疏矩阵的三元组表表示方法及有关算法。

7、掌握广义表的有关概念及其与线性表的关系。

8、掌握广义表的括号表示和图形表示之间的转换。

第6章 树

1、掌握树的逻辑结构特征。

2、掌握树的不同表示方法。

3、掌握树的常用术语及含义。

4、二叉树的递归定义及树与二叉树的差别。

5、掌握二叉树的性质，了解相应的证明方法。

6、掌握二叉树的两种存储方法、特点及适用范围。

7、掌握二叉树的三种遍历算法，理解其执行过程。

8、掌握确定三种遍历所得到的相应的结点访问序列。

9、理解以遍历算法为基础，设计有关算法解决简单的应用问题。

10、理解二叉树线索化的目的及实质。

11、理解在中序线索树中查找给定结点的中序前趋和中序后继的方法。

12、掌握树和森林与二叉树之间的转换方法。

13、掌握树的各种存储结构及其特点。

14、掌握树的两种遍历方法。

15、掌握最优二叉树和最优前缀码的概念及特点。

16、掌握哈夫曼算法的思想。

17、掌握根据给定的叶结点及其权值构造出相应的最优二叉树。

18、掌握根据最优二叉树构造对应的哈夫曼编码。

第7章 图

1、理解图的逻辑结构特征。

2、理解图的常用术语及含义。

3、掌握邻接矩阵和邻接表这两种存储结构的特点及适用范围。

4、掌握根据应用问题的特点和要求选择合适的存储结构。

5、理解连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。

6、掌握确定两种遍历所得到的顶点访问序列。

7、掌握图的两种遍历与树的遍历之间的关系。

8、 理解两种遍历所使用的辅助数据结构(栈或队列)在遍历过程中所起的作用。

9、理解利用图的两种遍历设计算法解决简单的应用问题。

10、掌握生成树和最小生成树的概念。

11、掌握对遍历给定的图，画出深度优先和广度优先生成树或生成森林。

12、掌握Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。

13、掌握要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。

14、了解最短路径的含义。

15、了解求单源最短路径的Dijkstra算法的基本思想和时间性能。

16、掌握对于给定的有向图，根据Dijkstra算法画出求单源最短路径的过程示意图。

17、掌握拓扑排序的基本思想和步骤。

18、理解拓扑排序不成功的原因。

19、了解对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。

第9章 查找

1、了解查找在数据处理中的重要性。

2、理解查找算法效率的评判标准。

3、掌握顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。

4、理解顺序查找中哨兵的作用。

5、理解二分查找对存储结构及关键字的要求。

6、理解通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。

7、掌握二叉查找树和B-树的定义和特点以及用途。

8、掌握二叉查找树的插入、删除、建树和查找算法及时间性能。

9、掌握建立一棵二叉查找树的过程实质上是对输入实例的排序过程，输入实例对所建立的二叉查找树形态的影响。

10、了解B-树的插入、删除及查找方法的基本思想。

11、掌握散列表、散列函数、散列地址和装填因子等有关概念。

12、掌握散列函数的选取原则及产生冲突的原因。

13、掌握几种常用的散列函数构造方法。

14、理解两类解决冲突的方法及其优缺点。

15、了解产生“堆积”现象的原因。

16、理解采用线性探测法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析。

17、了解散列表和其它表的本质区别。

第10章 排序

1、了解排序在数据处理中的重要性。

2、掌握排序方法的“稳定”性含义。

3、理解排序方法的分类及算法好坏的评判标准。

4、掌握直接插入排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析。

5、理解直接插入排序中哨兵的作用。

6、掌握针对给定的输入实例，要能写出直接插入排序的排序过程。

7、掌握冒泡排序的基本思想。

8、掌握快速排序的基本思想和算法实现，以及在最坏和平均情况下的时间性能分析，了解算法的稳定性。

9、了解基准元素(划分元)对划分是否平衡的影响。

10、掌握针对给定的输入实例，能写出快速排序的排序过程。

11、理解堆、小根堆、大根堆、堆项等有关概念和定义。

12、理解堆性质及堆与完全二叉树的关系。

13、掌握直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析。

14、掌握针对给定的输入实例，写出堆排序的排序过程。

15、掌握归并排序的基本思想和算法实现，以及时间性能分析。

16、掌握针对给定的输入实例，能写出归并排序的排序过程。

17、掌握通过对被排序的记录数目、记录信息量的大小、关键字的结构及初始状态、稳定性要求、辅助空间的大小、各种时间性能等方面的比较掌握各种排序的优缺点。

另外，校还有免费课程福利专区，各省统招专升本/专插本/专接本/专接本免费课程、试听课程、特色课程、真题题库等统统0元学，更多优质免费课程持续更新中。马上点击专升本免费课程，立即领取!