《数据结构》课程教学大纲

《数据结构》课程教学大纲一、课程基本信息课程编号：B022314课程名称：数据结构英文名称：DataStructure先修课程：高等数学、C语言程序设计适用专业：通信工程课程类别：专业教育选修课程/拓展课程课程总学时/学分：48/3（其中理论38学时，实验10学时）二、课程目标通过本课程的学习，使学生具备下列能力：1．掌握数据结构的基本概念，了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序和查找等常用算法中的应用。2．学会分析研究数据结构的特性，能为应用问题涉及的数据选择适当的逻辑结构、存储结构和操作，培养对给定实际问题选择和构造合适数据结构及设计有效算法的能力。3．初步掌握算法的时间分析和空间分析技术，提高理论水平，增强抽象和设计的能力，为以后进行软件开发和学习后续课程打下一个坚实的基础。三、课程目标与毕业要求的关系毕业要求指标点课程目标3.设计/开发解决方案：能够针对信息通信领域的复杂工程问题提出有效的解决方案，设计满足功能需求、性能指标的软硬件系统或功能单元，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。3-4能够对通信系统进行测试和评价、优化和改进；课程目标2课程目标34.研究：能够基于科学原理并采用科学方法对信息通信领域复杂工程问题进行研究，包括设计实验、分析与解释数据，并通过信息综合得到合理有效的结论。4-1针对信息通信领域复杂工程问题的关键因素，基于科学原理制定实验目标和方法，设计实验方案；课程目标1课程目标2课程目标3四、教学内容、要求及重难点第一章绪论（2学时）教学要求：1.熟悉数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构和数据类型等概念术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。2.了解逻辑结构和存储结构的性质，抽象数据类型的定义及表示方法。3.理解算法五个特性的确切含义。4.掌握计算语句频度和估算算法时间复杂度的方法。5.熟悉算法描述规范与设计风格。教学重点：各概念术语的确切含义，算法的概念、评价标准及从时间和空间角度分析算法的方法。教学难点：数据结构的基本概念，数据的逻辑结构、存储结构及其差异，算法的时间复杂度分析。第二章线性表（10学时）教学要求：1.了解线性表的逻辑结构特性。2.熟练掌握顺序存储结构和链式存储结构的描述方法。3.熟练掌握在顺序存储结构中线性表的查找、插入、删除和合并操作。4.熟练掌握在单链表存储结构中线性表的查找、插入、删除和合并操作。5.了解在循环链表、双向链表存储结构中实现线性表操作的基本方法。6.了解静态链表。7.掌握线性表两种存储结构的不同特点及其使用场合。教学重点：顺序表的存储结构的描述方法，线性表在顺序存储结构上的基本操作，链式存储结构的描述方法，线性表在链式存储结构上的基本操作。教学难点：各种链表的特点及在其上实现线性表基本操作的方法。[实验名称]链表[实验类型]设计性[实验要求]1.编写程序实现链表的创建、插入、查找、删除操作。2.通过本实验加深对链表的理解，掌握链表的创建、插入、查找、删除操作。[实验学时]2学时第三章栈和队列（6学时）教学要求：1.掌握栈和队列的操作特性，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.掌握栈满和栈空的条件以及它们的描述方法。4.掌握循环队列和链队列的基本操作实现算法。5.掌握队满和队空的条件以及它们的描述方法。教学重点：栈和队列这两种结构的特点，栈和队列在两种存储结构中的实现。教学难点：队满和队空的条件以及它们的描述方法，循环队列的基本操作实现算法。[实验名称]栈及其运算[实验类型]设计性[实验要求]1.编写程序实现栈的进栈、出栈和判栈空等运算。2.通过本实验加深对栈的理解，掌握栈的进栈、出栈和判栈空等运算。[实验学时]2学时第四章串（2学时）教学要求：1.熟悉串的七种基本操作的定义，并能利用这些基本操作实现串的其它各种操作的方法。2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握堆串存储结构以及在其上实现串操作的基本方法。4.了解串匹配的KMP算法。5.了解块链串的结构定义。教学重点：串的基本操作和存储方法。教学难点：在串的存储结构上实现基本操作，KMP算法。第五章数组和广义表（2学时）教学要求：1.掌握数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.理解掌握对特殊矩阵进行压缩存储的下标变换公式。3.了解稀疏矩阵的两种存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4.掌握广义表的结构特点及其存储表示方法。5.了解对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。教学重点：数组的顺序存储，矩阵的压缩存储。教学难点：稀疏矩阵的两种压缩存储方法。第六章树和二叉树（8学时）教学要求：1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.熟练掌握二叉树各种遍历策略的递归算法。4.理解二叉树线索化的实质。5.了解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。6.熟悉树的各种存储结构及其特点，了解树和森林与二叉树的转换方法。7.掌握建立哈夫曼树和构造哈夫曼编码的方法。教学重点：二叉树的定义、性质和存储结构，二叉树的遍历，哈夫曼树的基本概念及哈夫曼算法。教学难点：理解二叉树的性质及其证明，各种二叉树遍历策略的递归算法及应用，哈夫曼算法的实现。[实验名称]二叉树的建立及输出[实验类型]设计性[实验要求]1.编写程序实现的二叉树的创建和遍历。2.通过本实验加深对二叉树的二叉链表存储结构的理解，掌握二叉树的三种遍历算法。[实验学时]2学时第七章图（8学时）教学要求：1.熟悉图的各种存储结构及其构造算法。2.熟练掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法。3.掌握应用图的遍历算法求解各种简单路径问题的方法。4.掌握图的最小生成树算法及最短路径的求法。5.理解拓扑排序及关键路径的的推导方法。教学重点：图的邻接矩阵表示法和邻接表表示法，图的深度优先和广度优先遍历算法，最小生成树的概念及构造方法，拓扑排序，最短路径的求解思路。教学难点：图的邻接表表示法，深度优先和广度优先遍历算法，最小生成树的构造方法，求解最短路径的思路及算法。[实验名称]图及其遍历[实验类型]综合性[实验要求]1.编写程序实现图的存储和图的深度优先搜索算法以及广度优先搜索算法。2.通过本实验加深对图的邻接矩阵和邻接表的存储结构的理解，掌握图的深度优先搜索算法以及广度优先搜索算法。[实验学时]2学时第八章查找（6学时）教学要求：1.熟练掌握顺序查找法和折半查找法，熟悉分块查找法。2.熟练掌握二叉排序树的构造和查找方法。3.了解平衡二叉排序树的维护平衡方法。4.掌握哈希表的构造方法，深刻理解哈希表与其他表的实质性差别。5.掌握哈希表处理冲突的方法。6.熟悉求等概率情况下查找成功时的平均查找长度的方法。教学重点：顺序查找、折半查找、索引顺序查找各自的思路与特点，二叉排序树的插入、删除算法和查找方法，哈希表处理冲突的方法，哈希表的查找及其分析。教学难点：各种查找算法的思路和算法实现，平衡二叉排序树的维护平衡方法，哈希表处理冲突的方法及其分析。[实验名称]树表的查找[实验类型]设计性[实验要求]1.编写程序实现树表的查找。2.通过本实验加深对二叉排序树的理解，掌握二叉排序树的插入、查找等操作。[实验学时]2学时第九章内部排序（4学时）教学要求：1.深刻理解排序的定义，理解插入排序、交换排序、选择排序、归并排序、基数排序各种方法的基本思想。2.了解各种方法的排序过程及其依据的原则。3.掌握各种排序算法及时间复杂度的分析方法。4.理解排序方法的“稳定”或“不稳定”的含义。5.了解各种内部排序方法的应用。教学重点：各种排序的基本思想、算法特点、稳定性及算法时间复杂度的分析。教学难点：希尔排序、快速排序、堆排序及基数排序的基本思想和算法实现，各种排序算法时间复杂度的分析方法。五、课程教学内容、教学方式对课程目标的支撑序号课程内容框架教学内容教学方式学时支撑课程目标1绪论数据结构的基本概念；逻辑结构和存储结构的性质，抽象数据类型的定义及表示方法；算法的五个特性；计算语句频度和估算算法时间复杂度的方法；算法描述规范与设计风格。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置2课程目标12线性表线性表的逻辑结构特性;顺序存储结构和链式存储结构的描述方法；在顺序存储结构中线性表的查找、插入、删除和合并操作；在单链表存储结构中线性表的查找、插入、删除和合并操作；在循环链表、双向链表存储结构中实现线性表操作的基本方法；静态链表；线性表两种存储结构的不同特点及其使用场合。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告10课程目标1课程目标2课程目标33栈和队列栈和队列的操作特性；栈类型的两种实现方法；栈满和栈空的条件以及它们的描述方法；循环队列和链队列的基本操作实现算法；队满和队空的条件以及它们的描述方法。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告6课程目标1课程目标2课程目标34串串的七种基本操作的定义，利用这些基本操作实现串的其它各种操作的方法；在串的定长顺序存储结构上实现串的各种操作的方法；堆串存储结构以及在其上实现串操作的基本方法；串匹配的KMP算法；块链串的结构定义。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告2课程目标1课程目标2课程目标35数组和广义表数组的两种存储表示方法；数组在以行为主的存储结构中的地址计算方法；对特殊矩阵进行压缩存储的下标变换公式；稀疏矩阵的两种存储方法的特点和适用范围；以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；广义表的结构特点及其存储表示方法；非空广义表进行分解的两种分析方法。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告2课程目标1课程目标2课程目标36树和二叉树二叉树的结构特性及相应的证明方法；二叉树的各种存储结构的特点及适用范围；二叉树各种遍历策略的递归和非递归算法；二叉树线索化的实质；二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法；树的各种存储结构及其特点；树和森林与二叉树的转换方法；实现树的各种操作；哈夫曼树和构造哈夫曼编码的方法。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告8课程目标1课程目标2课程目标37图图的各种存储结构及其构造算法；图的深度优先搜索算法和广度优先搜索算法；应用图的遍历算法求解各种简单路径问题的方法；图的最小生成树算法及最短路径的求法；拓扑排序及关键路径的的推导方法。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告8课程目标1课程目标2课程目标38查找顺序查找法、折半查找法和分块查找法；二叉排序树的构造和查找方法；平衡二叉排序树的维护平衡方法；B树的特点以及它的建树过程；哈希表的构造方法；哈希表与其他表的实质性差别；哈希表处理冲突的方法；求等概率情况下查找成功时的平均查找长度的方法；讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告6课程目标1课程目标39内部排序排序的定义；插入类排序的基本思想；直接插入排序、折半插入排序、希尔排序的算法、排序过程、时间复杂度及稳定性；交换类排序的基本思想；冒泡排序、快速排序的算法、排序过程、时间复杂度及稳定性；选择类排序的基本思想；简单选择排序、树形选择排序、堆排序的算法、排序过程、时间复杂度及稳定性；归并排序的基本思想；归并排序的算法、排序过程、时间复杂度及稳定性；分配类排序的基本思想；基数排序的算法、排序过程、时间复杂度及稳定性。讲授、课堂讨论、课堂引导与启发下的课堂训练和课外作业布置、学生动手实验和课后撰写实验报告4课程目标1课程目标3六、课程目标与考核内容课程目标考核内容课程目标1：掌握数据结构的基本概念，了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序和查找等常用算法中的应用。1.数据结构和算法的基本概念，线性表、栈和队列、串、数组和广义表、树和二叉树以及图的基础知识和相关操作，查找和排序的算法。2.出勤和平时作业的完成情况。3.期末考试成绩。课程目标2：学会分析研究数据结构的特性，能为应用问题涉及的数据选择适当的逻辑结构、存储结构和操作，培养对给定实际问题选择和构造合适数据结构及设计有效算法的能力。1.利用四种逻辑结构和两种存储结构的知识分析实际的问题，选择适当的逻辑结构和存储结构，并分析问题所涉及的操作，编写出算法，解决问题。2.出勤和平时作业的完成情况。3.期末考试成绩。课程目标3：初步掌握算法的时间分析和空间分析技术，提高理论水平，增强抽象和设计的能力，为以后进行软件开发和学习后续课程打下一个坚实的基础。1.对给定算法分析其时间和空间复杂度并根据分析优化算法。2.出勤和平时作业的完成情况。3.期末考试成绩。七、考核方式与评价细则考核方式比例考核/评价细则平时成绩出勤10%1.全勤100分；2.旷课一次扣5分；3.迟到、早退、事假一次扣3分；4.上课时玩手机一次扣3分；5.上课睡觉一次扣3分；6.病