《2022年数据结构专升本大纲 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构专升本大纲 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 数据结构考试大纲第 1 章概论1.数据结构的基本概念和术语。1.1 数据、数据元素、数据项、数据结构等基本概念。1.2 数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。1.3 数据结构的两大类逻辑结构和常用的存储表示方法。2.算法的描述和分析。2.1 算法概念、特征及评价算法的标准2.2 算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。2.3 算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。2.4 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。第 2 章线性表1.线性表的逻辑结构。1.1 线性表的逻辑结构特征。1.2 线性表上定义的基
2、本运算，并能利用基本运算构造出较复杂的运算。2.线性表的顺序存储结构。2.1 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。2.2 顺序表上的插入、删除操作及其平均时间性能分析。2.3 利用顺序表设计算法解决简单的应用问题。3.线性表的链式存储结构。3.1 链表如何表示线性表中元素之间的逻辑关系。3.2 链表中头指针和头结点的使用。3.3 单链表、双链表、循环链表链接方式上的区别。3.4 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。3.5循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。3.6 双链表的定义及其相关的算
3、法。3.7 利用链表设计算法解决简单的应用问题。4.顺序表和链表的比较。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -2 4.1 顺序表和链表的主要优缺点。4.2针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。第 3 章栈和队列1.栈的逻辑结构、存储结构及其相关算法。1.1 栈的逻辑结构特点，栈与线性表的异同。1.2 顺序栈和链栈上实现的入栈、出栈等基本算法。1.3 栈的“上溢”和“下溢”的概念及其判别条件。1.4 利用栈设计算法解决简单的应用问题。2.队列的逻辑结构、存储结构及其相关算法。2.1 队列的逻辑结构特点，队列
4、与线性表的异同。2.2 顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。2.3 队列的“上溢”和“下溢”的概念及其判别条件。2.4 使用数组实现的循环队列取代普通的顺序队列的原因。2.5 循环队列中对边界条件的处理方法。2.6 利用队列设计算法解决简单的应用问题。2.7 栈和队列的特点，什么样的情况下能够使用栈或队列。第 4 章串1.串及其运算。1.1 串的有关概念及基本运算。1.2 串与线性表的关系。2.串的存储结构。2.1 串的两种存储表示。2.2 串上实现的模式匹配算法及其时间性能分析。第 5 章数组和广义表1.数组。1.1 数组的逻辑结构特征。1.2 数组的顺序存储结构
5、及地址计算方式。1.3 数组是一种随机存取结构的原因。2.矩阵的压缩存储。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -3 2.1 特殊矩阵和稀疏矩阵的概念。2.2 特殊矩阵和压缩存储时的下标变换方法。2.3 稀疏矩阵的三元组表的表示方法及有关算法。3.广义表的概念。3.1 广义表的有关概念及其与线性表的关系。3.2 广义表的括号表示和图形表示之间的转换。3.3 求给定的非空广义表的表头和表尾运算。第 6 章树1.树的概念。1.1树的逻辑结构特征。1.2 树的不同表示方法。1.3 树的常用术语及含义。2.二叉树。2.1 二叉树的递归定义及树与二叉树的差别。2.2 二叉
6、树的性质，了解相应的证明方法。2.3 二叉树的两种存储方法、特点及适用范围。3.二叉树的遍历。3.1 二叉树的三种遍历算法，理解其执行过程。3.2 确定三种遍历所得到的相应的结点访问序列。3.3 以遍历算法为基础，设计有关算法解决简单的应用问题。4.线索二叉树。4.1 二叉树线索化的目的及实质。4.2 在中序线索树中查找给定结点的中序前趋和中序后继的方法。4.3 查找给定结点的前序前趋和后序后继并非有效的原因。5.树和森林。5.1 树和森林与二叉树之间的转换方法。5.2 树的各种存储结构及其特点。5.3 树的两种遍历方法。6.哈夫曼树及其应用。6.1 最优二叉树和最优前缀码的概念及特点。名师资
7、料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -4 6.2 哈夫曼算法的思想。6.3 根据给定的叶结点及其权值构造出相应的最优二叉树。6.4 根据最优二叉树构造对应的哈夫曼编码。第 7 章图1.图的概念。1.1 图的逻辑结构特征。1.2 图的常用术语及含义。2.图的存储结构。2.1 邻接矩阵和邻接表这两种存储结构的特点及适用范围。2.2 根据应用问题的特点和要求选择合适的存储结构。3.图的遍历。3.1连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。3.2 确定两种遍历所得到的顶点访问序列。3.3 图的两种遍历与树的遍历之间的关系。3.4 两种
8、遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用。3.5 利用图的两种遍历设计算法解决简单的应用问题。4.生成树和最小生成树。4.1 生成树和最小生成树的概念。4.2 对遍历给定的图，画出深度优先和广度优先生成树或生成森林。4.3Prim和 Kruskal算法的基本思想、时间性能及这两种算法各自的特点。4.4 要求对给定的连通图，根据Prim 和 Kruskal算法构造出最小生成树。5.最短路径。5.1 最短路径的含义。5.2 求单源最短路径的Dijkstra算法的基本思想。6.拓扑排序。6.1 拓扑排序的基本思想和步骤。6.2 拓扑排序不成功的原因。6.3 对给定的有向图，若拓扑序
9、列存在，则要求写出一个或多个拓扑序列。第 8 章查找名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -5 1.基本概念。1.1 查找在数据处理中的重要性。1.2 查找算法效率的评判标准。2.线性表的查找。2.1 顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。2.2 顺序查找中哨兵的作用。2.3 二分查找对存储结构及关键字的要求。2.4通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。3.树的查找。3.1 二叉排序树特点以及用途。3.2 二叉排序树的插入、删除、建树和查找算法及时间性能。3.3建立一棵二叉排序树的过程实
10、质上是对输入实例的排序过程，输入实例对所建立的二叉排序树形态的影响。4.哈希技术。4.1 哈希表、哈希函数、哈希地址和装填因子等有关概念。4.2 哈希函数的选取原则及产生冲突的原因。4.3 几种常用的哈希函数构造方法。4.4 两类解决冲突的方法及其优缺点。4.5 产生“堆积”现象的原因。4.6采用线性探测法和拉链法解决冲突时，哈希表的建表方法、查找过程以及算法实现和时间分析。4.7 哈希表和其它表的本质区别。第 9 章 排序1.排序的目的、分类和排序方法的稳定性的定义。2.插入排序2.1 直接插入排序的算法。2.2 折半插入排序的算法。2.3 希尔排序的思想。3.快速排序名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -6 3.1 起泡排序的算法。3.2 快速排序的思想。4.选择排序4.1 简单的选择排序的算法。4.2 堆的定义、堆排序的思想。5.归并排序的思想。6.基数排序的思想及特点。7.各种内部排序方法的比较。参考书：数据结构（C 语言版）严蔚敏等编著清华大学出版社名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -