陇东大学于2021年升格为计算机科学与技术专业

专业课数据结构考试大纲

一、考试的目的

检查专升本(含高职院校)毕业生是否掌握数据结构课程的基础知识，达到教学大纲规定的要求。

二、考试要求和内容

靠前章引言

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

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

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

4.了解算法的概念，算法的时间复杂度，空，最差和平均时间复杂度等。

5.掌握算法描述和算法分析的方法，能对一般算法进行时间复杂度分析。

第二章线性表

1.了解线性表的逻辑结构特征。

2.理解线性表上定义的基本运算，可以用基本运算构造更复杂的运算。要求线性表的顺序存储结构达到“综合利用”的水平。

3.了解序列表的含义和特点，即序列表是如何反映线性表中元素之间的逻辑关系的。

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

5.了解如何使用序列表设计算法解决简单的应用问题。

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

7.掌握链表中头指针和头节点的使用。

8.了解单链表、双链表和循环链表的链接方式的区别。

9.掌握单链表的创建表、搜索、插入、删除等基本算法，并分析其时间复杂度。

10.了解循环链表上尾指针代替头指针的作用，以及单循环链表上的算法与单循环链表上对应算法的异同。

11.了解双链表的定义及其相关算法。

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

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

14.掌握线性表上需要执行的主要操作，知道是选择顺序表还是链表作为其存储结构，以获得更好的time 空性能。

第3章堆栈和队列

1.了解栈的逻辑结构特点以及栈和线性表的异同。

2.掌握在顺序栈和链栈上实现的栈入口和栈出口等基本算法。

3.理解栈的“上溢”和“下溢”的概念及其准则。

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

5.了解队列的逻辑结构特征以及队列和线性表的异同。

6.掌握顺序队列(主要是循环队列)和链式队列上队列进入和队列退出的基本算法。

7.理解“上溢”和“下溢”的概念及其判断条件。

8.理解数组实现的循环队列取代普通顺序队列的原因。

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

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

第四章字符串

1.掌握字符串的概念和基本操作。

2.了解字符串和线性表的关系。

3.掌握字符串的两种存储表示。

4.掌握C语言提供的字符串运算功能，构造字符串相关算法，解决简单的应用问题。

第五章数组和广义表

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

2.掌握数组的顺序存储结构和地址计算方法。

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

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

5.了解压缩存储中的特殊矩阵和下标变换方法。

6.了解稀疏矩阵的三表表示方法及相关算法。

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

8.掌握括号表示和图形表示的转换。

第六章树和二叉树

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

2.掌握树的不同表现方法。

3.掌握树木的常用术语和含义。

4.二叉树的递归定义及树与二叉树的区别。

5.掌握二叉树的性质，知道相应的证明方法。

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

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

8.掌握并确定通过三种遍历获得的相应节点访问序列。

9.了解基于遍历算法，设计相关算法解决简单应用问题。

10、了解二叉树线索的用途和本质。

11.了解在中序线索树中找到给定节点的中序先行词和中序后继词的方法。

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

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

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

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

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

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

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

第七章图

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.要明白，对于一个给定的有向图，如果存在一个拓扑序列，就需要写出一个或多个拓扑序列。

第九章搜索

1.理解数据处理中搜索的重要性。

2.了解搜索算法效率的评价标准。

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

4.了解哨兵在顺序搜索中的作用。

5.了解二分搜索法对存储结构和关键字的要求。

6.明白通过比较线性表上三种搜索方法的优缺点，可以根据实际问题的要求和特点选择合适的搜索方法。

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

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

9.掌握构建二叉查找树的过程，本质上是输入实例的排序过程，以及输入实例对已建立的二叉查找树形状的影响。

10.了解B-树插入、删除、搜索方法的基本思路。

11、掌握哈希表、哈希函数、哈希地址和加载因子等相关概念。

12、掌握哈希函数的选择原则和冲突的原因。

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

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

15.了解“积累”的原因。

16.了解使用线性检测法和拉链法解决冲突时哈希表的构造方法、搜索过程、算法实现和时间分析。

17.讨论了溶出度表与其他表格的本质区别。

第十章内部排序

1.理解数据处理中排序的重要性。

2.把握整理方法“稳定性”的含义。

3.了解排序方法的分类和判断算法好坏的标准。

4.掌握直接插入排序的基本思想和算法实现，分析最佳、最差和平均条件下的时间性能。

5.了解哨兵在直接插入排序中的作用。

6.掌握给定输入示例的直接插入排序的排序过程。

7.掌握气泡排序的基本思路。

8.掌握快速排序的基本思想和算法实现，分析最坏和一般情况下的时间性能，了解算法的稳定性。

9.了解参考元素(除法元素)对除法是否平衡的影响。

10、掌握针对给定输入的例子，可以编写快速排序流程。

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

12.了解堆的本质和堆与完全二叉树的关系。

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

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

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

16、掌握针对给定输入的例子，可以编写合并排序的排序流程。

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

参考材料:

1.《C语言数据结构描述》(第二版)，耿国华著，高等教育出版社，2015；

2.《数据结构》(C语言版)，严为民吴伟民主编，清华大学出版社，2020年。

部分内容来源于网络转载、学生投稿，如有侵权或对本站有任何意见、建议或者投诉，请联系邮箱（1296178999@qq.com）反馈。 未经本站授权，不得转载、摘编、复制或者建立镜像， 如有违反，本站将追究法律责任！