还剩4页未读,继续阅读
文本内容:
《数据结构与算法》教学大纲2
一、课程基本信息数据结构与算法课程名称Data Structureand Algorithins课程编码SCC260821030开课院部理学院课程团队数据结构与算法学分
3.0课内学时48讲授48实验|0上机
(16)|实践0课外学时64适用专业数学与应尸数学授课语言中文先修课程程序设计K)程性质本课程是信息与计算科学专业的必修课,是数学与应用数学专业的选修课.是信息与计算科学专业的重要的专业课主要教学内容研究数据的逻辑结构及其操作的表示和实现、算法设计的思想策略.包括线性结构(线性表、栈、队列)、树形结构(二叉树、树、森林)、图结构的存储方式、基本操作、常用算法的实现及其应用问遨求解;查找算法(顺序查找、折半查找);排序方法(直接插入排序、简单选择排序、快速排序、堆排序、归并排序等);算法设计的常用策略,包括递归与分治策略、动态规划、回溯法、分支限界法等.一些典型问题算法设计例子课程教学目标培养学生的数据抽象能力、算法设计能力,综合应用本课程知识求解实际的能力,提高学生的软件开发能力为从事IT等相关行业的软件软件开发莫定基础The courseproperty:This isa compulsorycourse forthe majorof inrorniation andcomputing scioncespecialily andis an课程简介(限选)elective coursefor mathematicsand appliedmathematics speciality.The mainteaching contents:Research onthe representationand realizationof thedata logicstructure andoperation,andalgorithmdesigningstrategy.Themaincontentsincludedatastorage,basicoperations,conunonalgorithms,andapplicationproblemsolvingofthelinearstructurelinearlist,stack,queue,treestructurebinarytree,tree,forestandgraphstruclure;searchingalgori thmssequent ialsearch,binary search,sorting algorithms straightinsertion sort,simple selectionsort,quick sort,heap sort,merging sort,etccomnonly usedalgorithms ofstrategy,including recursiveand divide-conquer strategy,dynamicprograraning,backtracking algorithm,branch andbound algorithm,and sometypical examplesin algorithmdesign.The teachinggoal ofthe course:To cultivatethe studentsability ofdata abstractionand algorithmdesign,and toapplytheknowledgethemtosolvethepracticalproblemsandimprovethestudentsabi1ityofsoftwaredeveloixnent.Tolaythefoundationfor softwaredevelopment inIT andother relatedindustries.负责人大纲执笔人审核人
二、课程目标毕业要求指标点序号代号课程目标OBE任务自选1Ml目标1:掌握数据的逻辑结构及其操作的表示方法与实现是
1.42M2目标2:拿握数据结构应用问题的求解.掌握算法的设计策略,是
1.43M3目标3培育认识和发现问题的能力、综合运用知识解决实际问题的能力是
1.4三课程内容支撑课课内学课外序号章节号标题课程内容/重难点教学方式课外环节程目标时学时1第1章第1章结论本章重点难点抽象数据类型的概念.算法设计要求.算法复杂度分析/////
21.
11.1数据结构引例数据结构引例.课程的研究内容Ml
0.5讲授
0.5作业语解释,包括数据、数据元素、数据结构、线性结构、树形结构、图状
31.
21.2基本概念Ml
0.5讲授
0.5作业结构、逻辑结构、存储结构、抽象数据类型等,
1.3算法质量与算法分算法的概念,算法的特性,算法设计的要求,算法复杂度分析,算法分析
41.3Ml
0.5讲授
0.5作业析的方法
51.
41.4学习指导对学习方法指导.对例题与习题的说明,对作业的要求.Ml
0.5讲授
0.5作业本章里点难点线性表的类型定义、存储结构、算法实现.栈和队列的定6第2章第2堂线性结构/////义
2.1线性表的类型定义
72.1线性表的抽象数据类型定义Ml1讲授1作业
2.2线性表的顺序表示
82.2顺序表的表示方法,几个基本算法的实现M22讲授3作业与实现
2.3线性表的链式表示线性链表的表示方法,几个基本算法的实现;循环链表,双向链表线性
92.3M23讲授4作业与实现表的存储结构与算法实现10上机1上机1线性表的顺序表与链表的常用操作,包括线性表的逆置、归并、拆分、M32上机作业1算法添加元素、删除元素.
112.
42.4栈栈的定义、存储结构与基本操作的实现,栈的应用M32讲授2作业
122.
52.5队列队列的定义、存储结构与基本操作的实现,队列的应用M32讲授作业1上机2栈与队列的算法栈和队列的基本操作与应用,包括入栈、出栈、入队、出队,括号匹配13上机2M32上机1作业与应用问题求解、迷宫问题求解,14笫3章第3$树形结构本章重点难点二叉树和树的定义、存储结构、算法实现/////
3.1二叉树的定义和二叉树的抽象数据类型定义,基本术语,二叉树的性质,二叉树的存储结
153.1Ml2讲授1作业存储结构构二叉树的4种遍历(先序、中序、后序、层序),二叉树的常用算法的实
163.
23.2遍历二叉树M22讲授5作业现
3.3树与森林的定义
173.3树的抽象数据类型定义,森林的定义Ml1讲授
0.5作业
3.4树与森林的存储结
183.4双亲孩子表示法.二叉树表示法,森林与二叉树的转换Ml1讲授
0.5作业构
3.5树与森林的遍历树的遍历(先序、后序、层序).森林的遍历(先序、中序、层序),树
193.5M22讲授3作业和森林的常用算法的实现
203.
63.6Huffman树Huffman树,Huffman算法,Huffman编码,M32讲授2作业上机3二叉树与树的存二叉树的遍历、树的遍历常用算法.包括建立与删除、统计某类结点、21上机3储结构与算M32上机1作业求高度、查找元素法第1堂查找与排本章重点难点顺序查找,折半查找,二叉排序树;直接插入排序,简单22第4章//1///序选择排序,快速排序,堆排序,归并排序
234.
14.1概述查找的有关概念,排序的有关概念,Ml
0.5讲授作业1顺序表的顺序查找及其算法分析.有序表的折半查找及其算法分析
244.
24.2静态查找表Ml
0.5讲授1作业
254.
34.3动态查找表二叉排序树的定义、性质与算法实现Ml2讲授1作业26上机4上机4查找算法顺序查找,折半查找,二叉排序树的操作M32上机作业
1274.
44.4简单排序直接插入排序.折半插入排序,耳泡排序,简单选择排序,Ml2讲授2作业
284.
54.5先进排序快速排序,堆排序,归并排序Ml4讲授5作业直接插入排序、简单选择排序、快速排序,推排序,归并排29上机5上机5排序算法M32上机1作业序30第5章第5堂图状结构本章重点难点图的存储结构,图的遍历,图的应用,/////
5.1图的定义与术语
315.1图的抽象数据类型定义,图的基本术语Ml1讲授1作业
325.
25.2图的存储结构数组表示法.邻接表表示法;图的基本算法的实现C Ml讲授作业1I
335.
35.3图的遍历图的深度优先搜索遍历,图的广度优先搜索遍历M22讲授3作业连通网的最小生成树,A0V网的拓扑排序,A0E网的关键路径,网的最短
345.
45.4图的应用M34讲授6作业路径上机6图的存储结构与图的存储结构.图的遍历,最小生成树,拓扑排序.关键路径,最短路径35上机6M32上机1作业应用本章至点难点递归算法,分治策略,动态规划,贪心算法,回溯法,分36第6章第6章算法设计/////支限界法
376.
16.1递归与分治法递归算法与分治策略及其应用排列问题,棋盘覆盖问题,M32讲授作业1动态规划算法及其应用矩阵连乘问题,最长公共子序列问题.0T背包问
386.
26.2动态规划算法M32讲授3作业题.钱币组合问题.编辑距离问题上机7递归与分治、动实现几个典型问题的算法,包括排列问题、棋盘覆盖问题、最长公共子序39上机7M32上机1作业态规划列问题,0T背包问题,贪心算法及其应用钱币组合问题.背包问题.多机调度问题”
406.
36.3贪心算法M31讲授1作业回溯法及其应用批处理作业调度问题,07背包问题,旅行商销售问题.
416.
46.4回溯法M32讲授3作业无向图的着色问题优先队列,分支限界法及其应用0-1背包问题,旅行商销售问题,整数
426.
56.5分支限界法M32讲授2作业变换问题43上机8上机8贪心算实现几个典型问题的算法,包括最优服务次序问题、钱币组合M32上机作业1法、回溯法与分支限界问题、07背包问题、旅行商销售问题,法
四、君核方式序号考核环节操作细节总评占比
1.每周布置3T个基础知识练习题、23个算法设计编程题前者主要练习学生对基本概念、基本算法的理解和掌握,后者主要练习学生提高算法设计能力和算法实现能力要求学生根据教师的批语改进作业1平时作业40%
2.成绩采用百分制,根据作业的质后、提交是否延迟、对作业的改进情况,综合评定作业成绩
3.考核学生对数据的存储结构与算法的掌握水平、编程实现算法的能力、综合运用课程知识求解问题的能力
1.半开卷考试,成绩采用百分制,卷面成绩总分100分
2.主要考核学生对本课程的基本知识的掌握情况好算法设计与实现的能力S5型包括两类一类S5以填空、简答、绘图、填表等形式考2期末考试50%核学生对数据结构的基本概念、存储方式、基本算法的掌握情况一类是编程题,考核学生的算法设计与实现水平3平时表现根据学生的考勤情况、学习态度、课堂回答问题情况与课外师生讨论交流情况综合评定成绩10%
五、评分细则序号课程目标考核环节大致占比评分等级A-按时完成全部作业、首次提交的作业质量很高,作业偶尔有质量问题.能尽快把作业修改好B-基本按时完成绝大部分的作业,作业质量较高,对有问题的作业多数能修改好c-完成大部分作业,或者作业迟交比蛟严重.或者作业质量蛟低,对1Ml平时作业40%作业修改后仍有部分作业有质量问题D-作业有作弊现象,或者完成作业比例太低.或者作业迟交严重或者作业质量太低并且忽视批语而不改进作业2Ml期末考试40%(见试卷评分标准)A-无旷课现象,学习态度端正,学习认真主动努力,课堂积极问答问题.遇到疑难问题时能主动与教师或同学交流讨论B旷课不超过1次,学习态度基本端正、学习比较认良、课堂回答问题较好、遇到疑难问题时有时与教师或同学讨论C-旷课2-33Ml平时表现20%次,学习态度一般、学习不够认真不够主动、课堂不主动答题或回答质量较低,遇到疑难问题时很少与教师或同学交流讨论D旷课1次以上次,学习态度较差、学习不认真不努力、课爱不回答问题或回答错误太多,几乎不与教师或同学交流讨论学习问题.,卜按时完成全部作业、首次提交的作业质量很高.作业偶尔有质量问题、能尽快把作业修改好.B基本按时完成绝大部分的4M2平时作业50%作业,作业质量较高.对有问题的作业多数能修改好,c完成大部分作业.或者作业迟交比蛟严重.或者作业质量较低,对作业修改后仍有部分作业有质量问遨D-作业有作弊现象,或者完成作业比例太低,或者作业迟交严重或者作业质量太低并且忽视批语而不改进作业5M2期末考试30%(见试卷评分标准),卜无旷课现象,学习态度端正,学习认真主动努力,课堂积极问答问题,遇到疑难问题时能主动与教师或同学交流讨论B-旷课不超过1次,学习态度基本端正、学习比较认真、课堂回答问题较好、遇到疑难问题时有时与教肺或同学讨论C-旷6M2平时表现20%课2-3次,学习态度一般、学习不够认真不够主动、课堂不主动答地或回答质量较低,遇到疑难问题时很少与教师或同学交流讨论0旷课1次以上次,学习态度较差、学习不认真不努力、课堂不回答问题或回答错误太多,几乎不与教师或同学交流讨论学习问题.卜按时完成全部作业、首次提交的作业质量很高.作业偶尔有质量问题.能尽快把作业修改好B基本按时完成绝大部分的作业,作业质量较高,对有问题的作业多数能修改好,c-完成大部分作业.或者作业迟交比较严重.或者作业质量较低,对作业7M3平时作业50%修改后仍有部分作业有质量问题,D-作业有作弊现象,或者完成作业比例太低,或者作业迟交严重或者作业质量太低并且忽视批语而不改进作业8M3期末考试20%(见试卷评分标准),卜无旷课现象,学习态度端正.学习认真主动努力,课堂积极问答问题,遇到疑难问题时能主动与教师或同学交流讨论B旷课不超过1次,学习态度基本端正、学习比蛟认真、课堂回答问题蛟好、遇到疑难问题时有时与教肺或同学讨论C-旷课9M3平时表现30%2-3次,学习态度一般、学习不够认真不够主动、课堂不主动答题或回答质量较低,遇到疑难问题时很少与教师或同学交流讨论匕旷课1次以上次,学习态度较差、学习不认真不努力、课堂不回答问题或回答错误太多,几乎不与教师或同学交流讨论学习问题评分等级说明[A,B,C,D]=[90-100,75-89,60-74,0-59]
六、教材与参考资料序号教学参考资料明细1图书数据结构与算法.、桑兆阳、张华清,中国石油大学出版社,2017,lSBN:978-7-5636-5679-
0.(*主教材)2图书数据结构(C语言版),严蔚敏、吴伟民,清华大学出版社,1997,lSBN:978-7-302-
023689.3图书算法设计与分析(第2版),王晓东,清华大学出版社,2008,ISBN:978-7-302T6343-
5.。