《数据结构与算法》教学大纲

数据结构与算法课程教学大纲课程基本信息二、课程简介及教学基本要求《数据结构与算法》是计算机程序设计的重要理论基础，是计算机相关专业的核心专业基础课程，针对我校计算机学院大学二年级学生开设，它前承高级语言程序设计和高等数学，后接操作系统、编译原理、数据库原理、人工智能等专业课程。程序设计就像搭积木，数据结构是零件，而算法则是设计图纸。高效运行且节约存储空间的程序，取决于数据结构和算法的设计。课程的学习效果不仅关系到后续课程的学习，而且直接关系到软件设计水平的提高和专业素质的培养，在计算机学科教育中有非常重要的作用。本课程将按照“线性结构，树型结构，图形结构，集合结构”四大模块循序渐进展开，重点学习线性表、字符串、栈和队列、树和二叉树、图以及集合在计算机上的存储和处理。课程采用“线下+线上”“课程+思政”“理论+实践”六位一体，“课前导学→理论精讲→小组实验→闯关训练→实践扩展→答疑反馈”六阶递进的混合教学模式。理论课要求：讲解数据结构与算法的基础理论、基本操作、手工模拟和算法实现，通过理论讲解、实操演示、动画模拟、翻转课堂等方法组织教学，每周提供一次线上辅导答疑。实验课要求：使用学校在线教育综合平台（网址：），每位学生根据提供的素材完成数据结构与算法实验作业，并将实验报告上传到课程平台。课前和课后要求：基于“学堂在线”（网址：/）和学校在线教育综合平台（网址：）精品在线课程学习平台，拓展延伸学生知识面，引导学生自主学习，积极完成课前导学、闯关训练、习题微课等内容，提高学生针对现实问题的分析、设计和编码能力。三、课程教学目标通过本课程的学习，使学生掌握数据结构的基本理论与知识，算法设计与分析的基本方法与技巧，培养学生分析和解决实际问题的能力，并为其开展计算机学科应用奠定数据结构与算法方面的基础。通过解决工程问题，践行学术道德教育，增强学生软件岗位职业道德和团队合作意识，理论联系实际、精益求精的工作态度以及勇于开拓的创新精神。具体目标如下：目标1.理解数据结构和算法的基本概念。掌握常用基本数据结构的逻辑特征、存储表示和基本运算。掌握常用查找和排序算法，并能够分析不同算法的适用场景。目标2.具备初步的算法分析能力，会计算算法的时间、空间复杂度。目标3.提升分析解决问题的能力，学会分析数据对象的特性，选择（应用）有效的数据结构，设计合适的算法，并编写和调试程序。目标4.培养软件岗位职业道德和团队合作意识，理论联系实际、精益求精的工作态度以及勇于开拓的创新精神。毕业要求毕业要求分解指标点课程教学目标课程贡献度1.工程知识1.1掌握数学、自然科学、工程基础和计算机专业的基本概念和基本理论知识，并能够将其用于计算机领域复杂工程问题的表述。（知识掌握）目标1H2.问题分析2.1具备应用数学、自然科学和工程科学的基本原理，识别和判断复杂工程问题的关键环节和参数的能力。（识别）目标2H3.工程设计3.2理解和分析计算机应用的特定需求，对复杂工程问题进行分解，对子系统模块和业务流程进行设计与开发。（功能设计）目标3H4.调查研究4.1基于计算机专业技术原理，通过文献研究、信息分析等相关方法，研究和分析计算机领域复杂工程问题的解决方案。（研究分析）4.2针对相关领域关键问题，研究对象特征，运用计算机科学相关原理和专业知识选择研究路线，设计实验方案。（设计方案）目标3H8.沟通表达和团队合作8.1具有团队精神，能够胜任团队成员角色，具有一定独立解决工程问题的能力，同时又能配合团队合作完成任务，能组织团队成员开展工作，并具有合理协调和决策的能力。（组织与协作）目标4L注：课程贡献度用标志表示（“H”表示“高”，“M”表示“中”，“L”表示“低”）四、教学内容与教学方法第一章绪论【课程内容】数据结构与算法课程主要研究非数值计算的现实问题中的数据在计算机中表示、存取和处理。本章内容包括：1.什么是数据结构2.数据结构的基本概念和术语3.算法和算法分析4．抽象数据类型知识点：数据的三层次，数据结构的三要素，四种逻辑结构，四种存储结构，算法的概念和特点，算法的时间和空间复杂度。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2。【重/难点】重点：数据结构的概念和术语、算法时间复杂性分析方法。难点：数据逻辑结构和存储结构的定义以及区别，算法时间复杂性分析方法以及复杂性函数的渐进表示。【学时分配】线下理论教学2学时，线下实验0学时，线上单元导学0.5学时，线上习题解析0.5学时，线上答疑辅导1学时课程总学时64，其中：理论学时4课程总学时64，其中：理论学时48，实验学时16。线上学习内容未计入总学时计算。下同，不再赘述。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第二章线性表【课程内容】线性结构是最简单、最常用的数据结构，其特点是数据元素之间的逻辑关系是线性关系。线性结构是数据元素间约束力最强的一种数据结构：在非空线性结构的有限集合中，存在唯一一个被称为“第一个”的数据元素；存在唯一一个被称为“最后一个”的数据元素；除“第一个”数据元素无前驱外，集合中的每个数据元素均有且只有一个“直接”前驱；除“最后一个”元素无后继外，集合中的每个数据元素均有且只有一个“直接”后继。本章内容包括：1．线性表的类型定义2．线性表的顺序表示和基本运算3．线性表的链式表示和基本运算4．双链表的概念和基本运算5．循环链表的概念和基本运算6．线性表实现方法的比较7．算法设计举例知识点：顺序表、单链表的定义、特点及基本操作，双向链表、循环链表的特点、定义及基本操作。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：顺序表、单链表、双向链表、循环链表的插入、删除操作。难点：顺序表和单链表操作的实现。【学时分配】线下理论教学6学时，线下实验4学时，线上单元导学1.5学时，线上习题解析1.5学时，线上答疑辅导3学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第三章栈和队列【课程内容】栈和队列仍属于线性结构，它们的逻辑结构和线性表相同，具有线性结构的共同特征。学习本章时，既要注意栈和队列所具有的线性结构的共性，更要掌握其个性。栈和队列的基本操作是线性表操作的子集，限定插入和删除元素的操作只能在线性表的一端进行。栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作。本章内容包括：1.栈的概念、特点、逻辑结构、存储结构和基本运算2.栈的应用举、栈与递归3.队列的概念、特点、逻辑结构、存储结构和基本运算4.算法设计举例知识点：栈的特点及基本操作，顺序栈和链栈的实现，栈与递归，队列的特点和基本操作，循环队列的实现，栈与队列的综合应用【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：栈的压栈和弹栈操作、队列的入队和出队操作、中缀表达式求值难点：栈的应用：中缀表达式求值、中缀表达式转后缀表达式、后缀表达式求值【学时分配】线下理论教学6学时，线下实验2学时，线上单元导学1.5学时，线上习题解析1.5学时，线上答疑辅导3学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第四章字符串【课程内容】从数据结构角度讲，串属于线性结构，是一种数据元素（简称元素）为字符的特殊的线性表。串的逻辑结构和线性表相似。学习本章时，要注意串所具有的线性结构的共性，更要掌握其个性。串的特殊性主要表现在以下两个方面：①串中的一个元素是一个字符；②操作的对象一般不再是单个元素，而是一组元素。串的基本操作和线性表的基本操作有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，而在串的基本操作中，通常以“串的整体”作为操作对象，例如，在主串中查找子串的位置，在主串中截取一个子串。本章内容包括：1.串的基本概念2.串的表示和实现3.串的模式匹配算法知识点：字符串的概念、存储和基本操作，模式匹配方法。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：串的基本概念和操作的实现，KMP算法的手工模拟。难点：KMP算法的实现。【学时分配】线下理论教学2学时，线下实验0学时，线上单元导学0.5学时，线上习题解析0.5学时，线上答疑辅导1学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第六章树和二叉树【课程内容】在前几章主要介绍了线性结构，线性结构主要反映了数据元素之间的线性关系。从本章开始介绍非线性结构，其中树结构就是一种重要的非线性结构，它可以用来描述数据元素间的层次关系。这种层次关系的特点是，任意一个结点的直接前驱（结点）如果存在，则一定是唯一的；直接后继（结点）如果存在，则可以有多个，这也被称为一对多的关系。本章内容包括：1.树的概念2.二叉树的概念和性质3.二叉树的表示和实现4.树和森林的遍历运算5.树与二叉树的转换6.算法设计举例知识点：树的定义和术语、二叉树的定义、术语和主要性质、二叉树的遍历算法、二叉树的扩展算法、二叉树结构的性质、树的链接存储结构、树与二叉树的转换、树和森林的遍历。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：二叉树的性质、二叉树的二叉链式存储结构、二叉树的遍历、二叉树结构的性质、树与二叉树的转换、树和森林的遍历。难点：二叉树的性质、二叉树的遍历及扩展算法、二叉树结构的性质、树和森林的遍历、树与二叉树的转换【学时分配】线下理论教学6学时，线下实验2学时，线上单元导学1.5学时，线上习题解析1.5学时，线上答疑辅导3学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第七章树和二叉树的应用【课程内容】第6章已经介绍了树和二叉树的相关概念、性质、存储结构和基本运算，二叉树具有广泛的应用，常被用作表达式树、哈夫曼树、堆、二叉搜索（排序）树、平衡二叉树、判定树等。本章内容包括：1.表达式树2.哈夫曼树和哈夫曼编码3.堆和优先级队列4.算法设计举例知识点：哈夫曼树的概念；哈夫曼树的创建和哈夫曼编码，二叉堆的概念和特点、优先级队列的概念及其二叉堆实现。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：1．哈夫曼树的创建和哈夫曼编码的过程。2．基于二叉堆的优先级队列的创建、入队、出队运算。难点：优先级队列的入队、出队、创建算法。【学时分配】线下理论教学4学时，线下实验2学时，线上单元导学1学时，线上习题解析1学时，线上答疑辅导2学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第八章图【课程内容】图是一种复杂的非线性结构，线性结构和树结构也可以看成简单的图结构。在图结构中，结点之间的关系是任意的，是一种“多对多”的关系，即每个结点可以有零个或多个直接前驱和直接后继。本章内容包括：1.图的概念和术语2.图的存储结构3.图的遍历知识点：图的基本概念和术语、存储结构、图的遍历算法、图的生成树【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：基本概念（特别是完全图、连通分量、生成树和邻接点）、图的邻接矩阵和邻接表存储表示的特点、图的深度优先和广度优先遍历算法难点：图的深度优先和广度优先遍历算法【学时分配】线下理论教学4学时，线下实验4学时，线上单元导学1学时，线上习题解析1学时，线上答疑辅导2学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第九章图的应用【课程内容】第8章已经介绍了图的基本概念和性质，重点讨论了图的存储结构和遍历运算。本章重点介绍最小生成树、最短路径、拓扑排序等内容，简单介绍关键路径算法，这些内容都属于图的应用，内容包括：1.最小生成树2.有向无环图及其应用3.最短路径知识点：MST性质、最小生成树（Prim和Kruscal）、拓扑排序算法、求每对顶点之间最短路径的Dijkstra算法、求所有顶点间最短路径的Floyd算法。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：求最小生成树的Prim算法和Kruscal算法、拓扑排序算法、求最短路径的Dijkstra和Floyd算法难点：最小生成树Prim算法、最短路径Dijkstra和Floyd算法【学时分配】线下理论教学4学时，线下实验0学时，线上单元导学1学时，线上习题解析1学时，线上答疑辅导2学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第十章集合与查找【课程内容】集合是基本的数据结构之一。集合中的数据元素除属于同一个集合之外，没有任何逻辑关系。集合上的运算主要有：查找某个元素是否存在，将集合中的元素按照它的某个唯一标识排序。集合有多种组织形式，例如，集合可以用线性表、搜索树和散列表表示。本章首先介绍集合与查找的基本概念，然后讨论与集合相关的查找方法和简单的性能分析方法，包适用于静态查找表的顺序查找和折半查找，以及适用于动态查找表的二叉查找树、AVL树等，内容包括：1.集合与查找的基本概念2.静态查找表上的查找3.动态查找表上的查找4.算法设计举例知识点：集合与查找的基本概念、静态查找表（顺序查找算法，折半查找算法）；动态查找表（二叉查找树基本概念、性质和操作）。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：有序表的折半查找，二叉查找树的查找、插入和删除算法，平均查找长度的计算难点：二叉查找树的查找、插入和删除算法【学时分配】线下理论教学4学时，线下实验0学时，线上单元导学1学时，线上习题解析1学时，线上答疑辅导2学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第十一章散列表【课程内容】本章介绍的散列法是专用于集合的数据存储和检索方式，它不是利用比较的办法，而是用一个散列函数将数据和它的存储位置关联起来，这样就可以通过这个散列函数快速存储和检索数据。本章内容包括：1.散列表的概念2.构造散列函数的方法3.解决冲突的方法4.散列表的查找性能分析知识点：散列的基本概念和术语、散列函数，解决冲突方法。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：构造散列函数的除留余数法，解决冲突的线性探查法和链地址法，平均查找长度的计算难点：解决冲突方法：线性探查法和链地址法【学时分配】线下理论教学2学时，线下实验0学时，线上单元导学0.5学时，线上习题解析0.5学时，线上答疑辅导1学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。第十二章排序【课程内容】排序是数据处理中经常用到的一种重要操作，通过排序可以将一组无序的数据元素按其关键字的非递减（或非递增）次序排列成有序序列，排序的目的之一就是方便数据的查找。本章将介绍几种常用的排序方法及各种内部排序方法的比较，内容包括：1.排序的基本概念2.插入排序：直接插入排序、折半插入排序、希尔排序3.交换排序：起泡排序、快速排序4.选择排序：直接选择排序、堆排序5.归并排序：2路归并排序6.各种内部排序方法的比较知识点：直接插入排序，冒泡排序，快速排序，直接选择排序，堆排序，合并排序，基于关键词比较的排序算法下界分析。【教学方法】讲授法结合讨论法、翻转课堂、案例教学、项目教学等多种教学方法。【支撑课程目标】目标1，目标2，目标3。【重/难点】重点：直接插入排序，Shell排序，冒泡排序，快速排序，直接选择排序，堆排序，归并排序，基于关键词比较的排序算法分析。难点：Shell排序，快速排序，堆排序，归并排序。【学时分配】线下理论教学8学时，线下实验2学时，线上单元导学2学时，线上习题解析2学时，线上答疑辅导2学时。【评价方式】在线学习数据的形成性评价+闯关训练和实验作业的结果性评价。五、课内实验（实践）序号实验项目名称实验内容及要求学时支撑课程目标类型必做/选做1顺序表顺序表的类型定义及基本操作2目标3目标4设计性必做2单链表单链表的类型定义及基本操作2目标3目标4设计性必做3栈与队列（1）栈的类型定义及基本操作（2）队列的类型定义及基本操作2目标3目标4设计性必做4二叉树二叉树的类型定义和基本操作2目标3目标4设计性必做5Huffman树建立Huffman树并进行Huffman编码2目标3目标4设计性必做6图的邻接矩阵表示法图的邻接矩阵表示法义及基本操作2目标3目标4设计性必做7图的邻接表表示法图的邻接表表示法义及基本操作2目标3目标4设计性必做8排序实现常用排序算法：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、2路归并排序，能够测试上述算法性能。2目标3目标4验证性必做注：类型包括验证性、综合性、设计性、演示性等。六、课程考核与评价课程考核包括过程性考核和期末考核，过程性考核包括平时考核和实验/实践考核，其中平时考核含考勤和课堂表现、微课学习情况、章节测验或作业等。课程总评成绩=平时成绩（30%）+实验/实践成绩（20%）+期末成绩（50%）过程性考核成绩占总成绩的比例为50%，其中考勤和课堂表现占总成绩的10%。成绩组成考核/评价环节权重考核/评价细则平时成绩考勤和课堂表现10%统计雨课堂上的出勤率和课堂表现，给予相应分值微课学习情况10%统计优慕课（或学堂在线）由各专业授课教师选择适合的在线教学平台上的视频观看率和在线时长，给予相应分值由各专业授课教师选择适合的在线教学平台章节测试或作业10%统计优慕课（或学堂在线）由各专业授课教师选择适合的在线教学平台上的章节测试或作业成绩由各专业授课教师选择适合的在线教学平台实验/实践成绩实验报告20%以实验报告为主要评价依据，以展演视频（选做）作为参考期末成绩在线考试50%依托“百科园”平台开展在线考试七、教学资源（一）教材《算法与数据结构（C++语言版）》，主编:冯广慧，出版社：电子工业出版社，出版时间：2018.12。（二）参考资料1.《算法与数据结构考研试题精析》，主编:陈守孔，出版社：机械工业出版社，出版时间：2020.62.《数据结构：思想与实现,高等教育出版社》，主编:翁惠、玉俞勇，出版社：高等教育出版社，出版时间：20183.《数据结构（C语言版）》，主编:严蔚敏，出版社：清华大学出版社，出版时间：1997.44.《TheArtofComputerProgramming,Volume1/FundamentalsAlgorithms:Volume3/SortingandSearching》，主编:D.E.Kunth,出版社：MA:Addison-Wesley，出版时间：19735.本课程在珠海科技学院在线教育综合平台网址：/meol/jpk/course/layout/newpage/index.jsp?courseId=227346.本课程在“学堂在线”慕课平台网址：/course/jluzh61021002425/12425244附录1、课程思政知识点参考本课程通过提炼中国好故事，展示中国好成果，植入中国好素材，传递中国好声音，把爱国基因融入学生血脉，培养以爱国主义为核心的精神品格。本课程思政点设计如下表所示。内容或章节思政教学案例融入实例思政元素挖掘第一章概论1.1什么是数据结构在介绍《数据结构与算法》课程的发展历程、研究内容和重要性时，通过数据的对比分析，让学生感受到软件行业的快速发展。使学生在了解数据结构课程的同时，了解到中国软件和信息技术服务业取得了长足的进步，目前正处于高速发展的成长期，激发学生职业价值认同感。第一章概论1.2基本概念和术语在集合结构的教学设计中，通过在幻灯片中播放新冠疫情期间全国志愿者驰援武汉的相关图片，引入众志成城的志愿者集体来类比集合结构，替换只注重知识传授的传统案例。引导学生在理解集合结构的概念和特点的同时，感受中华民族万众一心、同舟共济、顾全大局、逆行而上的集体主义精神，以及个人命运与国家民族命运的血脉相连。第1章概论1.3算法和算法分析(1)在讨论算法的重要性时，介绍图灵奖获得者DonaldE.Knuth教授的经典公式“算法+数据结构=程序”，这说明优秀的算法能够让程序运行的更高效，比如金山WPS、钉钉、华为鸿蒙等（国产）软件的更新，就是在更新算法。(2)更新算法设计例题，引入中国古代约5—6世纪成书的《张邱健算经》中的“百钱买百鸡”问题，组织学生以小组为单位讨论多种求解方法，并开展翻转课堂活动，请3名学生登台演示，分析不同求解方法的差别，最后引入李开复的话阐述算法的重要性。(1)强调中国的软件产业肩负着通过国产化替代工程来增强关键领域信息安全的历史使命，为将来可能成为行业中坚力量的学生们敲响信息安全预警，厚植爱国主义教育，强化信息安全意识。(2)使学生认识到算法设计的重要性，并了解到中国古代源远流长的文化底蕴，增强文化自信。第2章线性表在介绍线性结构时，结合线性结构元素间1：1的特点，在幻灯片中播放十年间我国的GDP数据表。其中，GDP表的每行可以看作一条记录（也称