《数据结构B》教学大纲.docx

数据结构B教学大纲适用楚困：202X版本科人才培养方案课程代码：08150371课程性质：专业选修课学分：3学分学时：48学晡（理论32学时，实验16学时）先修课程：C潘吉程序设计B等后续课程：智能机器人等适用专业：机器人工程专业开课单位：计算机科学与技术学院一、课程说明寸数匏结构是机器人工程专业的专业选修课.本课程主要使学生体会“豫法的设计建立于逻辑结构算法的实现依赖于物理（存储）结构”,并能根据实际情况选择相应的数据结构和功法.学习如何合理地组织数据、有效地存谛和处理数据.正确比设计律法以及对算法的分析和评价,为以后在本专业方面的优质程序设计打下基础.二、课程目标通过本课程的学习，使学生达到如下目标；课程目标1：节握利理解线性结构与非税性结构数据组织形式及基本算法.课程目标2：具有简或运用和应的数据结岗和算法合理组织数刖、处理数据的能力.邨程目标3：在课程教学中把理想信念教百与科学精神的培养结合起洪.提高学生用马克思主义的世界观和方法论认识、分析和解决问SS的能力：让学生在学好专业知识的同时室定理想信含，不断增强科技演国的使命感和揖任感：培养学生精益求精的工匠精神和创新制神。三、课程目标与毕业要求数据结构8深程教学目标对机涔人工程专业毕业要求的支拽见&I.«1课程教学目标与毕业聂求关系毕业要求指标点课程目标支樨2.忖分析:能终应用数学、自然科学和工程噩础的基本原理，识别、衣达、并通过文献研究分析机器人工程航域的红杂工程问题.农握对望特性，以狭得有效结2.2成用数学、物理等方法和专业知识，能够时机器人工程领域发杂工程问他进行建模.课程H标1：掌握和现轿戏性结构与非线性结构数据组织形式及基本算法.课程目标2；具有荷单运用相应的数据结构和算法合理组织数据、处理数据的能力.M论。4研先，能够域于机器人机械、电子电路、计算机、控制等科学原理，并采用数学建模、系统仿真等科学方法，对机落人工程领域的复杂工程问题进行研究,包括设计实段、建模、分析与解秣数据、并通过信息综合得到合理有效的结论.1.3能够采用计算机仿真、实物或半实物仿真等方法,设计实验方案,搭建实验系统，进行实蛤。课程目标3：在课程教学中把理患信合教育与科学拓神的培养结合起来，提离学生用马克思主义的世界观和方法论认识、分析和解决何超的能力：让学生在学好专业知识的同时坚定埋患伯含，不断增强科技强国的使命礴和责任塔；培养学生精益求精的工匠精神和创新精神。M注：表中-H（WXM（中）”表示课程与相关毕业要求的关联度.四、教学内容,基本要求与学时分配I.理论部分理论部分的教学内容、基本要求与学时分配见表2。表2教学内容、苓本要求与学时分配教学内容敕学要求，敕学工点魔点理论学时实验学时对应的爆程目标1 .缗论1.I什么是数据法构：1.2肌本概念和术语：1.3算法和算法分析。教学要求：使学生能师知道为什么学习数据结构这门课,这门课的主要内容是什么：知道本门课的基本学习方法：能准确理解各种基本概念和术语：会估算算法的时间复杂度.点：了解数据结构这门课的主要研究内容及学习方法；熟恚基本概念和术谱：算法时间更杂度的计算：难点：究法时间复杂度的计尊.41、2、32.线性表2.1线性表的类型定义:2.2成性表的顺序表示和实现：2.3线件表的故式表示和实现：2.4循环链表和双向祖表。假学要求：使学生理解线性衣的定义和特点：理解线性表的顷序表示和实现：理解线性表的链式表示和实现：掌握线性表的基本操作和应用.点：单桂表的插入、删除和查询；潼点:通过单链去举一反三对循环徒表和双向跳表进行操作.4213.栈和队列3.1栈的定义、特点、表示和操作、应用：3.2队列的定义、料点、表示和操作、应用教学襄求：使学生掌握栈和队列的定义、特点、送卷结构及其基本运算：了解栈和队列在实际编程中的基本应用.点：栈和队列的定义、特点、然本321、2操作;难点：循环队列的表示和实现，4.申、数蛆和广义衰1.1串的定义、存储、运算：4.2 数匐的定义、顺序存储、压缩存储：4.3 广义表的定义和存储.做学夫求：使学生了解申和广义表的定义和基本特点：明白申、广义表的编程适用场合：能对稀说矩阵进行压缩存储.点：申的定义和运算、广义去的定义和存储：难点：中的运算.341、35.材与二叉树5. 1树和二叉树的定义：5.2:叉树的性质和存储：53遍历二叉树:5. 4树和森林：5.5哈夫里柯及其应用.收学要求，使学生理解树和叉树的定义和特点：熟练掌握二叉树的存储方法和遍历方法：）能完成树、森林:叉树间的相互转换；理解哈夫曼树的构造方法,他用哈夫曼树解决实际问题.重点：二叉树的定义、性质、存储、遍历、应用；难点：哈夫曼树及其应用.622、36.图6.1 图的定义和术语：6.2图的存储结构：6.3图的遍历：6.，1图的应用。.教学要求：使学生理解图的批本概念及术语：掌握图的存储方式和遍历方法：能用图解决实际问题.点：图的存储、遍历和应用：充点：图的应用。.422、37.查找7.1查找的基本概念；7.2线性表的连找：7.3树表的查找：74fft列表的查找.t学央求：使学生了解任找的权本利想：掌握交找的第本方法：了解杳找的实际应用.点:线性表、树表的i?找：难点:敢列上的查找.421、2.38.排序8. 1择序的基本概念;8.2 内部排序的基本方法插入、交换、选择、归并、基数：8.3 外部排序与内部排序的不同之处、外部排序的基本方法.教学要求：使学生了解排序的基本思ffi；掌握插入类、交换类、选择类排序的基本思想和方法：了解芬种排序算法的优缺点,在现实问起解决中能选用合适的排序算法.点：插入、交换、选择排序的基本思想：球点：希尔排序.快速排序、堆排序.421、2,332162.实验部分实脸部分的教学内容、基本要求与学时分配见表3。表3实验项目、实险内容与学时实验项目实腕内容和要求实验学时对应的课程目标1,线性表（栈和队列实3内M设计一个我性表,分别采用顺序存储结构插入个元索：和采用链式存储结构册除一个结点.栈和队列两种类型二选一，完成创建、入栈或出枝（入队或出鼠）.实验要求：掌握线性衣的捅入、删除和查询：了解栈的先进先出及队列的范本愫作.41、22.单琏表和串实验内容：从键盆输入-率.求率长度：从键盘输入两率.实现申的连接；从键盘输入一申，求从该申第i个字符开始的j个子那I选作：从键盘输入两个串,实现两个串的比较：从板盘情入一个事.捌除该串中指定字符.实验要求：熟悉单链我的创建、插入、捌除、衽询'输出：掌握申的掂本操作和应用.41.23.二叉树和图实验内容：创建：叉树：遍历：叉树或求：叉树叶子节点故谈求二叉树深度（透一）：图；图的遍历、最小生成树、关键路径、破短路径等操作（选一实MMa掌握二叉树的基本操作和应用：掌握图的基本操作和应用.42、34.查找与排序实验内容：二分法查找、二叉排序树的查找、哈布表的创建与查找选一：寸泡排序、插入排序选一.实验襄求1熟悉食找和排序的经典眸法，42、3合计16五、教学方法及手段本课程以课堂讲授为主,结合讨论、案例、网络资源共享、实脸等教学手段完成课程教学任务和相关能力的培养，学生比较全面他体会”算法的设计建立于选料结构，算法的实现依赖于物埋（存储）结构”，并能根据实际情况选择相应的数据结树和算法，所以本课程教学强调思维训练,为随后的程序设H-和技能训练打好基础.在实骁教学环节中，通过启发式教学、讨改式教学培养学生的对问题的分析、数据结构的基本理论、基本知识和基本技能.培养学生自主学习能力、实际动手能力，激发学生的创新思维.每完成一项实验,要认真完成一份实验报告.六、课程资源I,推荐教材：（D数据结构C语言版,严JStft,吴伟民著M.北京：消华大学出版社,2021.102 .参考书:（1）产萌敏.李冬梅.吴伟民等著数据结构（C谙=第2版北M.北京：人民邮电出版社，2021.10（2）刘畅著,一据结构IM1.北京r上海交通大学出版社,2016.08（3）程杰，4大话数据结构3M匕京：清华大学出版社，2020.123 .期刊：(1) E1.1.isHorowitzSartajSahniSusanAnderSOnFrccd（李建中、张岩、李治军画.数据KJ(C语言版HM.北京:机械工业出版社:.2012.3(2) MarkA1.1.enWeiSS(冯舜依译).数据结构与算法分析一C语言描述M匕京：机械工业出版社2012.1.1.(3) Bcnt1.cyJI.Mu1.tidimensiona1.binarysearchtreesusedforassociativesearching!Jj.CommunicationsoftheAcm.(4) 1.iu1.YuM.Shao1.1.atentStructurePreservingHashingJ.Internationa1.Journa1.ofComputerVision.2017.(5)于智娟,差肌DNA计算机中队列数据结何的设计及实现J,计算机学报.2014.4 .网络资源：(1) POi1.的笔记.DataStructure)数据结构中各种树.2015-08-15.1.t1.pr'b1.ogs.cm>1.11aybc2030*p,4732377.htn1.(2)小草莓川I1.数据结构基础概念篇.2017-11-14.http:b1.og,(3)静默虚空.程序员的内功一一数据结构和算法系列.2015-03-11.http:/ww»'七、课程考核对课程目标的支撑邨程成绩由过程性考核成绩和期末考核成绩两部分构成,具体考核/评价细则及对课程目标的支撑关系见表4.表4课程考核对课程目标的支撑考核环占比考核/价价细Je课程目标112330<1）根据课堂出勤情况和课堂回答何题情况进行考核,满分100分.<2）以平时考核成绩乘以其在总评成绩中所占的比例计入课程总评成绩。12135实脍10< 1）根据每个实验的实验操作完成情况和实物报告域量单独评分，满分100分：< 2）彳H次实验单独评分，取各次实验成缄的平均值作为此环节的最终成绩。< 3）以实验成绩乘以其在总评成绩中所占的比例计入课程总评成绩.IO作业10<1）主要考核学生时各堂节知识点的双习、理解和掌握程度.潮分100分：<2）每次作业单独评分,Ik各次成绩的平均值作为此环节的最终成绩.<3）以作业成绩乘以其在总评成统中所占的比例计入课程总评成储。442期末考50<1>卷面成绩100分,以卷面成绩乘以共在总评成