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

数据结构与算法分析教学大纲适用范困：2O2X版本科人才培养方案课程代码:22140181课程性质：专业必修i果学分：4学分学时：N学时（理论56学时，上机8学时先修课程：程序设计基础等后排课程：操作系统等适用专业：人工智能专业开课单位：智能工程学院一、课程说明4数据结构与算法分析？是人工智能专业的一门专业必修课，是人工智能与教学、操作系统、机器学习、深度学习等课程的先修课其主饯内容有：<1）线性结构：规性表、栈、队列、申和数组的的范本概念、逻辑结构、存储结构、框本操作及应用：（2）树型结构；W和二叉树的基本概念、逻辑结构、存储结构、基本操作及应用：（3）图状结构的基本概念、逻辑结构、存储结构、鎏本操作及应用:<4）查找：静态查找表、动态查找表和哈希表：（5）排序：辅入排序、交换排序、选择排序、归并排序、基数排序：（6）算法的基本概念、特征、评价舞法的方法、算法分析方法。工数据结构与算法分析3课程系统介绍了软件设计中常用的数据结肉及相应的存储结构和匏法，介绍了多种查找和排序方法.通过本课程的学习,学生应掌握分析研究计算机加工的数据结构的特性：以便在实际应用中选择适当的逻辑结构、存储结构及相应算法，并至到算法的时间分析和空间分析方法：为应用软件的研制打下坚实的理论基础.二、课程目标通过本课程的学习，使学生达到如下目标：课程目标I：能够掌握数据结构中线性结构、树型结构和图状结构的逻辑特征、存储结构及基本操作，并能在实际同时中合理应用。课程目标2：针对特定前求，能够综合运用数据结构知识设计合埋的逻辑结构、存储结构及律法,并旎编写程序实现算法能好从时间、空间等方面对算法进行分析和评价.课程目标3：理解i1.算机有关的国家标准、行业标准、企业标准、法律法规以及相关知识产权、行业政策，课程目标4：引导学生利用科学辩证法行待和解淡向题；激发学生科技报国的家国情怀和使命担当，培养学生的队协作能力及创新创业思维：树立正确的劳动观念，形成良好的劳动习惯，具有劳动精神和劳动能力。三、课程目标与毕业要求数据结构与算法分析"出程教学目标时人工智能专业毕业要求的支掠见表1.表1课程教学目标与毕业聂求关系毕业要求指标点课程目标支撑1.TSftiR1.3能够将f业和数学等相关知识用于专业工程问题的解决方案设计、比较和综合。课程目标1：能坡掌握数据结构中线性结构、树型结构和图状结构的逻轼特征、存储结构及基本操作,并能在实际问题中合理应用.H3.设计/开发解决方案3.1鸵握人工智能及相关应用领域的系统集成、算法优化、软件设计的基本设计理论和设计方法,能鲂根据需求确定设计目标研究、确定技术方案。课程目标2,针对特定需求.能够综合据用数据结构知识设计合理的逻辑结构、存储结构及算法.并能编写程序实现算法，能师从时间、空间等方面对算法进行分析和评价.课程目标4：引导学生利用科学样证法看待和解决问题：激发学生科技报国的家国华怀和使命担当，培养学生的团队仍作能力及创新创业思维：树立正确的劳动观念,形成良好的劳动习惯.具有劳动精神和劳动能力“M注：表中“H（高）、M（中）”表示课程与相关毕业要求的关联度.四、教学内容,基本要求与学时分配1.理论部分理论部分的教学内容、基本要求与学时分配见表2。表2教学内容、基本要求与学时分配教学内容教学要求，教学置点难点理论学时上机学时对应的谭程目标1 .数据结构基破知识1.1 数据结构的基本概念和术语;1.2 抽象数据类型的表示与实现：1.3 算法和算法分析.思玫1：从“田忌窕马”引入，讨论算法的重要性思政2：引入我国软件行业现状,美国对中兴、华为的科技封教学要求：r解数据结构相关的基本柢念.包括数据、数据元素、数据顶、数据结构、逻辑结构、存储结构等：能熟练掌握数据结构两个层次的具体含义及其相互关系；能弊理解抽缴数据类型的定义、衣示和实现方法:能够理解算法的特性和评价标准：能分析灯法的时间复杂位和空间红杂度.点：数甥结构相关的基本概念、术语、抽软数据类型的农示与实现，理解兑法分析的具体方法.难点，掌握算法时间复杂度的分析方法.4O1、2.3、4锁，坐定爱国情怀2.线性表2.1线性我的逻辑结构；2.2战性表的序去示和实现：2.3线性表的链式表示和实现:2.1成性表的应用；一元多项式的表示及相加思政3：线性表的逻辑特征是：先进先出，将遵守社会公热、维护公共秩序的内容引出,弓I导学生树立正确的社会价值观.教学要求，熟悉编程实现顺序衣和琏衣的基本操作：学握数据要求选择合适的存储结构及相应算法,掌握时间和空间红杂性的角度算法分析:了好线性我的应用.点t戏性表的两种存储结构顺序表和钻表上的范本操作的实现。难点1从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合,明确它们各自的优映点.6O1、23.tt*KU13. 1栈和队列的定义和特点：3 .2的表示和操作的实现：4 .3栈与递归;3.4队列的表示和操作的实现.教学要求，理解编程实现栈和队列的基本操作：理解并实现栈和队列的基本应用：具备将递归程序转化为非递归程序的能力：理解递归算法的设计与分析方法：地过栈和递归的实现机制，皖对算法的时间、空间度量进行深入分析。点I栈和队列的特点及两种存储结构上的操作实现.难点，能罅灵活运用栈和队列设计解决实际应用向SS,掌握衣达式求他算法，深刻理解遢归算法执行过程中栈的状态变化过程，便于更好地使用递归算法621、24.申、数Ia和广义表4.1串的定义和相关术语:4.2申的表示和实现；4匕申的模式匹配算法。4.4数组.4.5广义表教学要求，解申的存储方法：理解审的两种模式见配算法,重点掌握K-MP算法.掌握数组地址计算方法：能进行特殊矩阵的压缩存储：了解广义表的定义、性质.点：中的模式匹配完法的原理及实现.数组地址的计切方法以及时称矩阵等特殊矩阵的压缗存储方法，难点I掌抑珅的存储方法,理解串的两杵模式匹配算法,尤其是KMP算法.掌握数组存储时地址计算方法,掌握几种特殊矩阵的压缩存储方法，数组地址的计算方法以及对称矩阵等特殊矩阵的压缩存储方法.6O1、25.忖和二叉树5.1 树的携本慨念和术语,结构定义和基本操作：5. 2二叉捋的定义与葩本操作；5.3:叉树的性质；5. 4二叉树的存储结构：5.5遍历二叉树:5.6线索二叉树：5.7树、森林与二叉树的转换:5.8树的存储结构:5.9哈夫强树及哈夫蚣嫔码.思i¾4;科学方法一社会结构，从树和二房树引入国家组织结构，以武汉防疫胜利为例说明中国行政管理的高效性，社会主义制度的优越性.培养学生科学思维及家国情怀.教学要求：理解根据：叉树的性砥进行问趣分析；掌握利用二叉树的递归讷历算法实现二叉树的其他操作：掌握递归遍历W法到非递P1.遍历。法的转换方法.掌旌非递归遍历算法：掌握通过线索二叉树出行二叉树的递归遍历：掌握利用哈夫她树进行貌码和译码：掌握树与：叉树的转换方法，进行树的遍历和森林的遍历。点I二叉树的基本概念、性质和存储结构及二叉树的遍历和线索，掌握哈夫密树和哈夫姓编码的构造方法，充点：利用树的核子兄弟表示法将饿的树结构转换为二叉树进行存储。掌握森林与二叉树之间的相互转换方法。1221、2、3&图6.1图的定义和基本术语：6. 2图的存储结构：6.3图的邈历（深度优先搜索和广度优先搜索）：6. 4图的连通性问越：6.5有向无环图及其应用：6.6坡短路径，思政5：介绍图在生活中的应用:从货郎担问Sfi到城市之间修建褥速公路或高铁、输送水气电铺设,再到GIS求最短路径何遨.培养学生家国情怀及工程思维.教学要求,广解图的避历以法、最小生成树以法、拓扑排序、关键路径、最短路径算法.能根据实际问鹿需求选择合适的数据结构并建立数学模型：能利用图的遍历算法及基本应用算法,解决麓杂工程问题.点：图的基本概念、存储结构、图的DFS和BFS遍历算法,掌握图在实际应用中的主要算法.难点，熟嫉掌握图的两种遍历算法.熟练或旌图在实际板用中的主要算法：最小生成树算法、最短路径算法、拓扑排序和关谈跖径算法，1221、2、37. 三tt7.1 查找的基本概念：7.2静态位找表；7.3动态在找去<二叉排序树.平衡二叉树）：7.4哈看表，教学要求：解颤序自找和折半,我的½本操作算法：并能对此进行效率分析；拿押一二又排序椅的构造和查找过程、插入、删除过程:掌握二叉排序树的平衡化操作；学旌通过哈希农的构造方法与处理冲突的方法，根据同咫需求构造合适的哈希表.点：部态育找去、动态查找衣及哈希表上的各种杳找算法。难点，明确各种不同S找方法之间的区别和各自的适用情况,能够按定义计算各种«5找方法在等概率情况下查找成功的平均查找长度.6O1、2&排序8.1排序的范本概分8.2插入排序：8.3交换排序：8.4选择排序：8.5归并排序：8.6基数排序，教学要求：竽握持序的基本概念：熟练学握口接插入排序、希尔排序、官泡排序、快途排序、直接选择挂序、堆排序、归并排序、基数排序的实现：掌握各种排序方法的时间空间复杂性分析方法.并能根据实际向应需求选择合适的排序算法.At各种排序方法的排序过程和实现算法，深刻理解各种排序方法的特点。点，掌掷各种排序方法的时间空间杂性分析方法，并能根据实际问题需求选择合适的排序算法.42K25682,上机部分上机部分的教学内容、基本要求与学时分配见表3。表3上机项目、上机内容与学时上机项目上机内容和要求上机学时对应的修程目标1.我性去、栈、队列的基本操作及应用上机内容：线性衣、校'队列的基本操作及应用。上机要求:通过问题启发式引导学生依据所掌握找性表的相关知识点，寻找问题的解抉方案,加深学生时找性表、栈、队列的依式存砧结构的理解,增强学生分析问应、解决同Sfi的能力，2I、22.二叉树的基本探作及应用上机内卷1二叉树的基本操作及应用.上机要求，笊提二叉树的桐关知识点,寻找问国的解决方案,加深学生对二叉树存储结构的理解，增强学生分析何题、解袂问愿的能力.2K23.图的基本操作及应用上机内图的册本操作及应用。上机要求：问麹启发式引导学生依据所学提图的相关知识点,寻找问题的解决方案,加深学生对图的逻辑结构、存储结构及应用的理解，增强学生分析时时、解决问JB的能力.21、21,杳我和排序的应用上机内容：位找和排序的应用,上机襄求t问题启发式引导学生依据所学匏杳找和排序的相关知识点,寻找何翻的解决方案,加深学生对各种查找和排序方法的理解,增强学生分析何时、解决同Sfi的能力。21、28五、教学方法及手段课程教学以课堂讲授为主,结合上机、作业、骁深、泛雅平台资源配合多媒体课件等共同课完成堂投谀内容.采用Emai1.QQ.微信等交流工具,加强和学生之间的交流和沟讯六、课程资源1 .推荐教材：(I)严西敏吴伟民.数据结构(C语言).清华大学出版社2021.H2 .参考书：(1)程杰.大话数据结构.清华大学出版社2O2OJ2(2)严一-吴伟民.数据结构(C语言).清华大学出版社2015.2(3) E1.1.isHorowitzSanajSahniSusanAnderSon-FreCd(李建中、张岩、李治军谛).%据结构(C语言版).机械工业出版社,2012.3(4) MarkAnenWeiSM冯舜气的数据结构与算法分析一C语言描述.机械工业出版tt.2OI2.1.1.3 .期刊：(1) A1.aeiH.BagheriA.DecomposingandConcatenatingBinarySearchTreesandApp1.icaiionsinMakingDaiaStructuresDynamiCJ.ce.sharif.ac.ir,2022.(2) TantcdcschiV,KusncrMJ,Nicu1.acV.IqamingBinaryDecisionTreesbyAminDiftcrcntiation1.CVnntcrnaiionaIConferenceonMachine1.carning.PM1.R.2021.(3) Bcn1.1.cyJ1.Mu1.tidimensiona1.binarysearchtreesusedforassociativescarching(J.Coinniunica1.ionsoftheAcm.(4) 1.iu1.YuM.Shao1.1.atentStructurePreservingHashingIJ.Internationa1.JoumaIofComputerVision.2017.(5)于睿娟.黄珊DNA计算机中队列数据结构的设计及实现叫,计算机学报.2014.(5) SS玲,魏永江.裔长元.1富于Bigtab1.eMapReduce的APriOri算法改进计算机科学，2015.(6) 王尚平.张亚玲.王育民.证书吊铺的线索二叉排序Hash树解决方案|从软件学报.2001.12(9):1343-1350.4 .网络资源：(1)数据结构知识点大汇总.2O21S2O.hiipr:"ZhUanIan.7hihu.CCmp,'3564787()(2)十三张图带你彻底了解所有数据结构.2021-8-18.hitpq，,ZhUanIan.zhihu.cQmg,'138523723(3)PCI1.的笔记.DataStructure)数据结构中各种树.2015-08-15.h(pb1.ogs.conVmaybe2030'p1,4732377.htm1.(4)小草莓皿.数据结构可础概念群2O171114(5) h(tp:/b1.og.csdn.nei'qq_31.196849a11ic1.edetai1.78529724(6)静默废空.程序员的内功一一数据结构和算法系列.2015-03-11.b1.ogs.c«<n'jingmoxukong,'p/4329079.htm1.七、课程考核对课程目标的支撑课程成绩由过程性考核成绩和期末考核成绩两部分构成,具体考核/评价细则及对课程目标的支挥关系见表4。表4课程考犊对售程目标的支撑考核环节占比考核/评价细则课程目标1234课堂表现8(1)根据深堂出勤情况和线上学习情况进行考核.满分100分.(2)以平时考核成绩乘以及在总评成绩中所占的比例计入课程总评成绩.4222上机16(D根据每次上机操作完成情况质制垠独评分，满分100分；(2)每次上机球独评分，取各次上机成绩的平均值作为此环节的球终成绩，(3)以上机成绩乘以其在总评成成中所占的比例计入课程总评成绩.663作业16(1)主要考核学生对各讹节知识点的更习、理解和掌握程度.满分100分：<2)每次作业服独评分，取各次成缄的平均值作为此环节的跛终成绩.(3)以作业成绩乘以其在总评成缄中所占的比例计入课程总评成绩.J87末核期考60<1)卷面成绩100分，以卷面成绩乘以其在总评成绩中所占的比例计入课程趋评成绩。(2)主要考核线性结构、树型结构、图状结构、查找、排序、算法、算法分析方法等内容.<3)考试即型为：域空即、选择的、计算四、编程烟和综合分析题簪，252510合计：1.oo分43W152八、考核与成绩评定1 .考核方式及成绩济定考核方式：本课程主要以课堂表现、上机、作业、期末考试等方式对学生进行考核评价.考核基本要求：（加强过程考核）考核总成绩由期末试卷成绩和过程性评价成绩组成.其中：期末笔试考核成绩为100分（权型为60%）,试跑类型为填空题、选择题、计算题、编程胞和综合分析题等类型：试卷中基本知识、基本理论、基本技能的试题分值不超过5州粽合应用题、分析题不低于50%：课堂表现、作业评价、上机等过程性评价成绩为100分（权重40%）。过程性评价和考试试题分值分配应与教学大纲各章节的学时用本成比例。2 .过程性考核成较的标准过程性考核方式!f1.点考核内容、评价标准、所占比重见表5.«5过程性考校方式评价标准考核方式所占比窟（»）100>x9090>x8080>x>7070>x>60x<60课堂表现20线上学习任务完成好,出勋率岛,笫记完整,积极参与教学活动，踊跃回答问题.准确率大于90%“线上学习任务完成较好，出勤率离,笔记完整，积极参与教学活动，踊跃回答问题,准确率大于80%,现上学习任务完成较好，出勤率高，笔记不完整.偶尔参马教学活动，回答问SS准确率大于70践上学习任务完成一般，出勤率较高，上课不认其，上课不记第记，偶尔参与教学活动。线上学习任务完成较出勤率不高，上课不认直，上课不记笔记.不参与教学活动.作业40多次作业平均得分290多次作业平均得分90>x80多次作业平均得分分80>x70多次作业平均得分80>x70多次作业平均得分<60上机40多次上机平均得分力90多次上机平均得分90>x80多次上机平均得分80x70多次上机平均得分80>x70多次上机平均得分<60