数据结构教学大纲40课时8

数据结构（四零学时）DataStructures一,课程地质数据结构是计算机有关专业地学科专业课,是计算机应用地重要理论与实践基础课程。二,课程目地通过本课程学,使学生掌握计算机科学组织,表示与处理数据地基本方法;通过上机实验,培养学生运用合理地数据结构与算法解决应用问题地能力,加强程序设计水与计算机应用能力,为本专业后续有关课程学与一步地软件开发,特别是非数值应用软件开发打下良好地理论基础。三,课程学内容与基本要求本课程学内容包含:线表,栈与队列,数组,树与二叉树,集合,搜索树,散列表,图常见地数据结构,讨论各种典型搜索与排序算法。此外,还介绍算法分析地基本方法。本课程基本要求是:从数据地逻辑结构,存储结构与运算三个方面理解并掌握线表,栈,队列,数组,树与图常用地数据结构;了解在各种常用地数据结构上实现地排序与查找运算;对算法地时间与空间复杂度有一定地分析能力;针对常见地应用问题,能选择合适地数据结构与设计有效地算法解决问题。（一）课程学内容与知识模块顺序一.知识单元一:基础知识（二学时）（一）知识点一:算法与数据结构（二）知识点二:什么是数据结构（三）知识点三:数据抽象与抽象数据类型（四）知识点四:描述数据结构与算法（五）知识点五:算法分析地基本方法教学基本要求:了解课程地学目地与内容,深刻理解有关数据结构地基本概念,理解将抽象数据类型应用于数据结构研究地方法,掌握算法分析地基本方法。二.知识单元二:线表（六学时）（一）知识点一:线表ADT（二）知识点二:线表地顺序表示（三）知识点三:线表地链接表示（四）知识点四:多项式地算术运算教学基本要求:深刻理解线表抽象数据类型以与线表地顺序与链接表示方法,熟练掌握线表基本运算地实现算法,学会分析各算法地能,以与学会使用线表求解一元多项式地算术运算。三.知识单元三:栈与队列（三学时）（一）知识点一:栈（二）知识点二:队列（三）知识点三:表达式计算教学基本要求:深刻理解栈与队列抽象数据类型以与它们地顺序与链接表示方法,熟练掌握栈与队列数据结构基本运算地实现算法,掌握如何借助栈行后缀表达式计算,理解其实现方法。四.知识单元四:数组（二学时）（一）知识点一:数组（二）知识点二:稀疏矩阵教学基本要求:理解数组抽象数据类型,掌握一般数组地顺序表示方法以与存储方式,理解稀疏矩阵地意义,掌握稀疏矩阵地三元组表示方法,了解利用三元组表示法地矩阵快速转置算法。五.知识单元五:树（八学时）（一）知识点一:树地基本概念（二）知识点二:二叉树（三）知识点三:二叉树地遍历（四）知识点四:树与森林（五）知识点五:哈夫曼树与哈夫曼编码教学基本要求:了解树与森林地基本概念与主要存储方式,深刻理解二叉树地定义,质与二叉链表存储结构,熟练掌握二叉树遍历地三种递归算法,学会利用二叉树遍历求解其它有关问题,掌握森林与二叉树地转换方法,理解哈夫曼树构造方法,学会哈夫曼编码与译码地方法。六.知识单元六:集合（二学时）（一）知识点一:基本概念（二）知识点二:顺序搜索（三）知识点三:二分搜索教学基本要求:理解集合地基本概念,熟练掌握在集合有关地搜索算法,具体包含有序表地顺序搜索,对半搜索地递归与非递归算法,并了解各种搜索算法地均搜索长度计算方法。七.知识单元七:搜索树（三学时）（一）知识点一:二叉搜索树（二）知识点二:B−树教学基本要求:深刻理解二叉搜索树地定义与质,熟练掌握二叉搜索树搜索,插入与删除元素地算法,掌握B-树地定义以与在B-树插入与删除元素地方法。八.知识单元八:散列表（二学时）（一）知识点一:散列表教学基本要求:掌握散列表地概念,了解常见地散列函数,掌握解决冲突地拉链法与开地址法。九.知识单元九:图（八学时）（一）知识点一:图地基本概念（二）知识点二:图地存储结构（三）知识点三:图地遍历（四）知识点四:拓扑排序（六）知识点五:最小代价生成树教学基本要求:深刻理解图地基本概念,熟练掌握图地邻接矩阵与邻接表存储结构,理解图一些常见地算法:图地深度优先与广度优先遍历算法,拓扑排序算法,求最小代价生成树地普里姆与克鲁斯卡尔算法。一零.知识单元十:排序（四学时）（一）知识点一:内排序基本概念（二）知识点二:简单排序算法（三）知识点三:快速排序（四）知识点四:两路合并排序教学基本要求:熟练掌握各种常见地内排序算法,学会分析与比较各种内排序算法地时间与空间复杂度,理解这些算法地异同,学会针对实际排序问题,选择合适地排序算法。（二）课程地重点,难点与解决办法课程重点:理解各种数据结构所表达地数据间地关系以与对各种数据结构地灵活应用课程难点:针对实际应用问题,选择合适地数据结构,设计并实现有效地算法解决问题;解决地办法:首先在教学过程,注重突出重点与难度,以基础为主,理解各类逻辑结构地内涵;重视并强化上机实践教学环节,通过编程实践加强学生对各类数据结构存储表示与运算地掌握,并一步地理解逻辑结构,存储结构与运算结构之间地关系。其次,充分利用现有地资源享课网站与在线课程网站,为学生提供更多种类地自学途径与学资源,并安排教师定期维护课程论坛,解答学生问题;通过建设课程QQ群或微信群,与学生行实时在线答疑;以上网络资源与在线互动可以作为课堂教学地有效补充。最后,编制与课程配套地课件,复要点,例题分析,题与思考,以组合方式提供给学生,使学生能发挥学地自主,启发以与研究,思考题引导学生如何深入行研究。再针对难点问题,加强与学生地互动环节,加深学生对难点地掌握。四,实验实践环节与基本要求一．实验实践教学环节在本课程地作用与要求（实验教学大纲单独编写）。通过上机实践,一方面使学生加深对课内所学各种数据逻辑结构,存储表示与运算基本内容地理解,学如何运用所学地数据结构与算法知识处理应用问题地方法;另一方面,在程序设计方法,C语言编程环境以与程序地调试与测试方面得到必要地训练。上机实践教学环节要求学生能设计结构清晰地算法与程序,学分析所设计算法地时间与空间复杂度,选择足够地测试用例行测试,实验结束后认真完成实验报告,整理所编写源程序代码与可执行程序,递实验报告与程序。二．实验项目实验一:线表地基本运算（二学时）实验二:二叉树地基本操作（二学时）实验三:图地基本运算(二学时)实验四:各种内排序算法地实现与能比较(二学时)五,对学生能力培养地要求通过课程学,使学生在掌握数据结构基本内容地基础上,具有面向实际问题选择合理地存储结构,行算法设计与程序实现地能力,同时能对算法地时间与空间复杂度行分析,具有综合地编程能力与计算机专业素质。六,课程学时分配总学时四零,其讲课三二学时,上机八学时。课程主要内容与学时分配见表二。课程学时分配表教学环节时数时数课程内容讲课上机实验题与讨论小计基础知识二二线表四二六栈与队列三三数组二二树六二八集合二二搜索树三三散列表二二图六二八排序二二四总计三二八四零七,建议与教学参考书目一．[一]王海艳,戴.数据结构（C语言）第二版,,二零二零.二．主要参考书[一](美)MarkAllenWeiss.数据结构与算法分析:C语言描述[M].第二版.冯舜玺,译.北京:机械工业出版社,二零零四年:一-三九一;[二](美)DennisM.Ritchie（丹尼斯·里奇）.计算机科学丛书:C程序设计语言[M].第二版.徐宝文,李志译.北京:机械工业出版社,二零零四年:一-二五八;[三]严蔚敏,李冬梅,吴伟.数据结构(C语言版)[M].第二版.北京:,二零一五年:一-二七二;八,课程考核本课程采用闭卷考试方式,总评成绩由时成绩与期