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

《数据结构与算法分析》教学大纲适用范围：202X版本科人才培养方案课程代码：22140181课程性质：专业必修课学分：4学分学时：64学时（理论56学时，上机8学时）先修课程：程序设计基础等后续课程：操作系统等适用专业：人工智能专业开课单位：智能工程学院一、课程说明《数据结构与算法分析》是人工智能专业的一门专业必修课，是人工智能与数学、操作系统、机器学习、深度学习等课程的先修课。其主要内容有：（1）线性结构：线性表、栈、队列、串和数组的的基本概念、逻辑结构、存储结构、基本操作及应用；（2）树型结构：树和二叉树的基本概念、逻辑结构、存储结构、基本操作及应用；（3）图状结构的基本概念、逻辑结构、存储结构、基本操作及应用；（4）查找：静态查找表、动态查找表和哈希表；（5）排序：插入排序、交换排序、选择排序、归并排序、基数排序；（6）算法的基本概念、特征、评价算法的方法、算法分析方法。《数据结构与算法分析》课程系统介绍了软件设计中常用的数据结构及相应的存储结构和算法，介绍了多种查找和排序方法。通过本课程的学习，学生应掌握分析研究计算机加工的数据结构的特性；以便在实际应用中选择适当的逻辑结构、存储结构及相应算法，并掌握算法的时间分析和空间分析方法；为应用软件的研制打下坚实的理论基础。二、课程目标通过本课程的学习，使学生达到如下目标：课程目标1：能够掌握数据结构中线性结构、树型结构和图状结构的逻辑特征、存储结构及基本操作，并能在实际问题中合理应用。课程目标2：针对特定需求，能够综合运用数据结构知识设计合理的逻辑结构、存储结构及算法，并能编写程序实现算法，能够从时间、空间等方面对算法进行分析和评价。课程目标3：理解计算机有关的国家标准、行业标准、企业标准、法律法规以及相关知识产权、行业政策。课程目标4：引导学生利用科学辩证法看待和解决问题；激发学生科技报国的家国情怀和使命担当，培养学生的团队协作能力及创新创业思维；树立正确的劳动观念，形成良好的劳动习惯，具有劳动精神和劳动能力。三、课程目标与毕业要求《数据结构与算法分析》课程教学目标对人工智能专业毕业要求的支撑见表1。表1课程教学目标与毕业要求关系毕业要求指标点课程目标支撑强度1.工程知识1.3能够将专业和数学等相关知识用于专业工程问题的解决方案设计、比较和综合。课程目标1：能够掌握数据结构中线性结构、树型结构和图状结构的逻辑特征、存储结构及基本操作，并能在实际问题中合理应用。H3.设计/开发解决方案3.1掌握人工智能及相关应用领域的系统集成、算法优化、软件设计的基本设计理论和设计方法，能够根据需求确定设计目标研究、确定技术方案。课程目标2：针对特定需求，能够综合运用数据结构知识设计合理的逻辑结构、存储结构及算法，并能编写程序实现算法，能够从时间、空间等方面对算法进行分析和评价。课程目标4：引导学生利用科学辩证法看待和解决问题；激发学生科技报国的家国情怀和使命担当，培养学生的团队协作能力及创新创业思维；树立正确的劳动观念，形成良好的劳动习惯，具有劳动精神和劳动能力。M注：表中“H（高）、M（中）”表示课程与相关毕业要求的关联度。四、教学内容、基本要求与学时分配1.理论部分理论部分的教学内容、基本要求与学时分配见表2。表2教学内容、基本要求与学时分配教学内容教学要求，教学重点难点理论学时上机学时对应的课程目标1.数据结构基础知识1.1数据结构的基本概念和术语；1.2抽象数据类型的表示与实现；1.3算法和算法分析。思政1：从“田忌赛马”引入，讨论算法的重要性思政2：引入我国软件行业现状，美国对中兴、华为的科技封锁，坚定爱国情怀教学要求：了解数据结构相关的基本概念，包括数据、数据元素、数据项、数据结构、逻辑结构、存储结构等；能熟练掌握数据结构两个层次的具体含义及其相互关系；能够理解抽象数据类型的定义、表示和实现方法；能够理解算法的特性和评价标准；能分析算法的时间复杂度和空间复杂度。重点：数据结构相关的基本概念、术语、抽象数据类型的表示与实现，理解算法分析的具体方法。难点：掌握算法时间复杂度的分析方法。401、2、3、42.线性表2.1线性表的逻辑结构；2.2线性表的顺序表示和实现；2.3线性表的链式表示和实现；2.4线性表的应用；一元多项式的表示及相加。思政3：线性表的逻辑特征是：先进先出，将遵守社会公德、维护公共秩序的内容引出，引导学生树立正确的社会价值观。教学要求：熟悉编程实现顺序表和链表的基本操作；掌握数据要求选择合适的存储结构及相应算法，掌握时间和空间复杂性的角度算法分析；了解线性表的应用。重点：线性表的两种存储结构顺序表和链表上的基本操作的实现。难点：从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合，明确它们各自的优缺点。601、23.栈和队列3.1栈和队列的定义和特点；3.2栈的表示和操作的实现；3.3栈与递归；3.4队列的表示和操作的实现。教学要求：理解编程实现栈和队列的基本操作；理解并实现栈和队列的基本应用；具备将递归程序转化为非递归程序的能力；理解递归算法的设计与分析方法；通过栈和递归的实现机制，能对算法的时间、空间度量进行深入分析。重点：栈和队列的特点及两种存储结构上的操作实现。难点：能够灵活运用栈和队列设计解决实际应用问题，掌握表达式求值算法，深刻理解递归算法执行过程中栈的状态变化过程，便于更好地使用递归算法621、24.串、数组和广义表4.1串的定义和相关术语；4.2串的表示和实现；4.3串的模式匹配算法。4.4数组.4.5广义表教学要求：了解串的存储方法；理解串的两种模式匹配算法，重点掌握KMP算法。掌握数组地址计算方法；能进行特殊矩阵的压缩存储；了解广义表的定义、性质。重点：串的模式匹配算法的原理及实现。数组地址的计算方法以及对称矩阵等特殊矩阵的压缩存储方法。难点：掌握串的存储方法，理解串的两种模式匹配算法，尤其是KMP算法。掌握数组存储时地址计算方法，掌握几种特殊矩阵的压缩存储方法。数组地址的计算方法以及对称矩阵等特殊矩阵的压缩存储方法。601、25.树和二叉树5.1树的基本概念和术语、结构定义和基本操作；5.2二叉树的定义与基本操作；5.3二叉树的性质；5.4二叉树的存储结构；5.5遍历二叉树；5.6线索二叉树；5.7树、森林与二叉树的转换；5.8树的存储结构；5.9哈夫曼树及哈夫曼编码。思政4：科学方法—社会结构，从树和二叉树引入国家组织结构，以武汉防疫胜利为例说明中国行政管理的高效性，社会主义制度的优越性。培养学生科学思维及家国情怀。教学要求：理解根据二叉树的性质进行问题分析；掌握利用二叉树的递归遍历算法实现二叉树的其他操作；掌握递归遍历算法到非递归遍历算法的转换方法，掌握非递归遍历算法；掌握通过线索二叉树进行二叉树的非递归遍历；掌握利用哈夫曼树进行编码和译码；掌握树与二叉树的转换方法，进行树的遍历和森林的遍历。重点：二叉树的基本概念、性质和存储结构及二叉树的遍历和线索，掌握哈夫曼树和哈夫曼编码的构造方法。难点：利用树的孩子兄弟表示法将一般的树结构转换为二叉树进行存储。掌握森林与二叉树之间的相互转换方法。1221、2、36.图6.1图的定义和基本术语；6.2图的存储结构；6.3图的遍历（深度优先搜索和广度优先搜索）；6.4图的连通性问题；6.5有向无环图及其应用；6.6最短路径。思政5：介绍图在生活中的应用：从货郎担问题到城市之间修建高速公路或高铁、输送水气电铺设，再到GIS求最短路径问题，培养学生家国情怀及工程思维。教学要求：了解图的遍历算法、最小生成树算法、拓扑排序、关键路径、最短路径算法。能根据实际问题需求选择合适的数据结构并建立数学模型；能利用图的遍历算法及基本应用算法，解决复杂工程问题。重点：图的基本概念、存储结构、图的DFS和BFS遍历算法，掌握图在实际应用中的主要算法。难点：熟练掌握图的两种遍历算法，熟练掌握图在实际应用中的主要算法：最小生成树算法、最短路径算法、拓扑排序和关键路径算法。1221、2、37.查找7.1查找的基本概念；7.2静态查找表；7.3动态查找表（二叉排序树、平衡二叉树）；7.4哈希表。教学要求：了解顺序查找和折半查找的基本操作算法；并能对此进行效率分析；掌握二叉排序树的构造和查找过程、插入、删除过程；掌握二叉排序树的平衡化操作；掌握通过哈希表的构造方法与处理冲突的方法，根据问题需求构造合适的哈希表。重点：静态查找表、动态查找表及哈希表上的各种查找算法。难点：明确各种不同查找方法之间的区别和各自的适用情况，能够按定义计算各种查找方法在等概率情况下查找成功的平均查找长度。601、28.排序8.1排序的基本概念；8.2插入排序；8.3交换排序；8.4选择排序；8.5归并排序；8.6基数排序。教学要求：掌握排序的基本概念；熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序的实现；掌握各种排序方法的时间空间复杂性分析方法，并能根据实际问题需求选择合适的排序算法。重点：各种排序方法的排序过程和实现算法，深刻理解各种排序方法的特点。难点：掌握各种排序方法的时间空间复杂性分析方法，并能根据实际问题需求选择合适的排序算法。421、2合计5682.上机部分上机部分的教学内容、基本要求与学时分配见表3。表3上机项目、上机内容与学时上机项目上机内容和要求上机学时对应的课程目标1.线性表、栈、队列的基本操作及应用上机内容：线性表、栈、队列的基本操作及应用。上机要求：通过问题启发式引导学生依据所掌握线性表的相关知识点，寻找问题的解决方案，加深学生对线性表、栈、队列的链式存储结构的理解，增强学生分析问题、解决问题的能力。21、22.二叉树的基本操作及应用上机内容：二叉树的基本操作及应用。上机要求：掌握二叉树的相关知识点，寻找问题的解决方案，加深学生对二叉树存储结构的理解，增强学生分析问题、解决问题的能力。21、23.图的基本操作及应用上机内容：图的基本操作及应用。上机要求：问题启发式引导学生依据所掌握图的相关知识点，寻找问题的解决方案，加深学生对图的逻辑结构、存储结构及应用的理解，增强学生分析问题、解决问题的能力。21、24.查找和排序的应用上机内容：查找和排序的应用。上机要求：问题启发式引导学生依据所掌握查找和排序的相关知识点，寻找问题的解决方案，加深学生对各种查找和排序方法的理解，增强学生分析问题、解决问题的能力。21、2合计8五、教学方法及手段课程教学以课堂讲授为主，结合上机、作业、慕课、泛雅平台资源，配合多媒体课件等共同课完成堂授课内容。采用E-mail、QQ、微信等交流工具，加强和学生之间的交流和沟通。六、课程资源1.推荐教材：（1）严蔚敏吴伟民.数据结构（C语言）.清华大学出版社2021.112.参考书：（1）程杰.大话数据结构.清华大学出版社.2020.12（2）严蔚敏吴伟民.数据结构（C语言）.清华大学出版社2015.2（3）EllisHorowitzSartajSahniSusanAnderson-Freed(李建中、张岩、李治军译).数据结构(C语言版).机械工业出版社.2012.3（4）MarkAllenWeiss(冯舜玺译).数据结构与算法分析——C语言描述.机械工业出版社.2012.113.期刊：(1)AlaeiH,BagheriA.DecomposingandConcatenatingBinarySearchTreesandApplicationsinMakingDataStructuresDynamic[J].ce.sharif.ac.ir,2022.(2)ZantedeschiV,KusnerMJ,NiculaeV.LearningBinaryDecisionTreesbyArgminDifferentiation[C]//InternationalConferenceonMachineLearning.PMLR,2021.(3)BentleyJL.Multidimensionalbinarysearchtreesusedforassociativesearching[J].CommunicationsoftheAcm.(4)LiuL,YuM,ShaoL.LatentStructurePreservingHashing[J].InternationalJournalofComputerVision,2017.(5)于智娟,姜珊.DNA计算机中队列数据结构的设计及实现[J].计算机学报,2014.(6)魏玲,魏永江,高长元.基于Bigtable与MapReduce的Apriori算法改进[J].计算机科学,2015.(7)王尚平,张亚玲,王育民.证书吊销的线索二叉排序Hash树解决方案[J].软件学报,2001,12(9):1343-1350.4.网络资源：（1）数据结构知识点大汇总.2021-5-20./p/356047870（2）十三张图带你彻底了解所有数据结构.2021-8-18./p/138523723（3）Poll的笔记.[DataStructure]数据结构中各种树.2015-08-15./maybe2030/p/4732377.html（4）小草莓lllll.数据结构基础概念篇.2017-11-14.（5）/qq_31196849/article/details/78529724（6）静默虚空.程序员的内功——数据结构和算法系列.2015-03-11./jingmoxukong/p/4329079.html七、课程考核对课程目标的支撑课程成绩由过程性考核成绩和期末考核成绩两部分构成，具体考核/评价细则及对课程目标的支撑关系见表4。表4课程考核对课程目标的支撑考核环节占比考核/评价细则课程目标1234过程性考核课堂表现8（1）根据课堂出勤情况和线上学习情况进行考核，满分100分。（2）以平时考核成绩乘以其在总评成绩中所占的比例计入课程总评成绩。√√√√4222上机16（1）根据每次上机操作完成情况质量单独评分，满分100分；（2）每次上机单独评分，取各次上机成绩的平均值作为此环节的最终成绩。（3）以上机成绩乘以其在总评成绩中所占的比例计入课程总评成绩。√√√663作业16（1）主要考核学生对各章节知识点的复习、理解和掌握程度，满分100分；（2）每次作业单独评分，取各次成绩的平均值作为此环节的最终成绩。（3）以作业成绩乘以其在总评成绩中所占的比例计入课程总评成绩。√√87期末考核60（1）卷面成绩100分，以卷面成绩乘以其在总评成绩中所占的比例计入课程总评成绩。（2）主要考核线性结构、树型结构、图状结构、查找、排序、算法、算法分析方法等内容。（3）考试题型为：填空题、选择题、计算题、编程题和综合分析题等。√√√252510合计：100分4340152八、考核与成绩评定1.考核方式及成绩评定考核方