《数据结构与算法1》课程教学大纲

《数据结构与算法1》教学大纲一、课程基本信息课程名称数据结构与算法DataStructureandAlgorithm课程编码SCC250811030开课院部理学院课程团队数据结构与算法学分3.0课内学时48讲授48实验0上机(16)实践0课外学时64适用专业数据科学与大数据技术授课语言中文先修课程程序设计（C）课程简介（必修）课程性质：本课程是数据科学与大数据技术专业的必修课。主要教学内容：研究数据的逻辑结构及其操作的表示和实现、算法设计的思想策略。包括线性结构(线性表、栈、队列)、树形结构(二叉树、树、森林)、图结构的存储方式、基本操作、常用算法的实现及其应用问题求解；查找算法(顺序查找、折半查找)；排序方法(直接插入排序、简单选择排序、快速排序、堆排序、归并排序等)；算法设计的常用策略，包括递归与分治策略、动态规划、回溯法、分支限界法等，一些典型问题算法设计例子。课程教学目标：培养学生的数据抽象能力、算法设计能力，综合应用本课程知识求解实际问题的能力，提高学生的软件开发能力。为从事IT等相关行业的软件软件开发奠定基础。Coursenature:Thiscourseisarequiredcourseforthemajorofdatascienceandbigdatatechnology.Mainteachingcontents:Studythelogicalstructureofdataandtherepresentationandimplementationofitsoperation,andtheideologicalstrategyofalgorithmdesign.Includinglinearstructure(lineartable,stack,queue),treestructure(binarytree,tree,Forest),storagemodeofgraphstructure,basicoperation,implementationofcommonalgorithmsandsolutionofapplicationproblems;searchalgorithm(sequentialsearch,halfsearch);Sortingmethods(directinsertionsort,simpleselectionsort,quicksort,heapsort,mergesort,etc.);Commonstrategiesforalgorithmdesign,includingrecursionanddivide-and-conquerstrategies,dynamicprogramming,backtracking,branchandboundmethods,andsomeexamplesofalgorithmdesignfortypicalproblems.Teachingobjectivesofthecourse:tocultivatestudents'abilityofdataabstractionandalgorithmdesign,tocomprehensivelyapplytheknowledgeofthiscoursetosolvepracticalproblems,andtoimprovestudents'abilityofsoftwaredevelopment.LaythefoundationforsoftwaredevelopmentinITandotherrelatedindustries.负责人大纲执笔人审核人二、课程目标序号代号课程目标OBE毕业要求指标点任务自选1M1目标1：掌握数据的逻辑结构及其操作的表示方法与实现。是3.12M2目标2：掌握数据结构应用问题的求解，掌握算法的设计策略。是4.33M3目标3：培育认识和发现问题的能力、综合运用知识解决实际问题的能力。是4.3三、课程内容序号章节号标题课程内容/重难点支撑课程目标课内学时教学方式课外学时课外环节1第1章第1章绪论本章重点难点：抽象数据类型的概念，算法设计要求，算法复杂度分析。/////21.11.1数据结构引例数据结构引例，课程的研究内容。M10.5讲授0.5作业31.21.2基本概念语解释，包括：数据、数据元素、数据结构、线性结构、树形结构、图状结构、逻辑结构、存储结构、抽象数据类型等。M10.5讲授0.5作业41.31.3算法质量与算法分析算法的概念，算法的特性，算法设计的要求，算法复杂度分析，算法分析的方法。M10.5讲授0.5作业51.41.4学习指导对学习方法指导，对例题与习题的说明，对作业的要求。M10.5讲授0.5作业6第2章第2章线性结构本章重点难点：线性表的类型定义、存储结构、算法实现，栈和队列的定义。/////72.12.1线性表的类型定义线性表的抽象数据类型定义。M11讲授1作业82.22.2线性表的顺序表示与实现顺序表的表示方法，几个基本算法的实现。M22讲授3作业92.32.3线性表的链式表示与实现线性链表的表示方法，几个基本算法的实现；循环链表，双向链表。线性表的存储结构与算法实现。M23讲授4作业10上机1上机1线性表的算法顺序表与链表的常用操作，包括线性表的逆置、归并、拆分、添加元素、删除元素。M32上机1作业112.42.4栈栈的定义、存储结构与基本操作的实现，栈的应用。M32讲授2作业122.52.5队列队列的定义、存储结构与基本操作的实现，队列的应用。M32讲授1作业13上机2上机2栈与队列的算法与应用栈和队列的基本操作与应用，包括：入栈、出栈、入队、出队，括号匹配问题求解、迷宫问题求解。M32上机1作业14第3章第3章树形结构本章重点难点：二叉树和树的定义、存储结构、算法实现。/////153.13.1二叉树的定义和存储结构二叉树的抽象数据类型定义，基本术语，二叉树的性质，二叉树的存储结构。M12讲授1作业163.23.2遍历二叉树二叉树的4种遍历(先序、中序、后序、层序)，二叉树的常用算法的实现。M22讲授5作业173.33.3树与森林的定义树的抽象数据类型定义，森林的定义。M11讲授0.5作业183.43.4树与森林的存储结构双亲孩子表示法，二叉树表示法，森林与二叉树的转换。M11讲授0.5作业193.53.5树与森林的遍历树的遍历（先序、后序、层序），森林的遍历（先序、中序、层序），树和森林的常用算法的实现。M22讲授3作业203.63.6Huffman树Huffman树，Huffman算法，Huffman编码。M32讲授2作业21上机3上机3二叉树与树的存储结构与算法二叉树的遍历、树的遍历。常用算法，包括：建立与删除、统计某类结点、求高度、查找元素。M32上机1作业22第4章第4章查找与排序本章重点难点：顺序查找，折半查找，二叉排序树；直接插入排序，简单选择排序，快速排序，堆排序，归并排序。/////234.14.1概述查找的有关概念，排序的有关概念。M10.5讲授1作业244.24.2静态查找表顺序表的顺序查找及其算法分析，有序表的折半查找及其算法分析。M10.5讲授1作业254.34.3动态查找表二叉排序树的定义、性质与算法实现。M12讲授1作业26上机4上机4查找算法顺序查找，折半查找，二叉排序树的操作。M32上机1作业274.44.4简单排序直接插入排序，折半插入排序，冒泡排序，简单选择排序。M12讲授2作业284.54.5先进排序快速排序，堆排序，归并排序。M14讲授5作业29上机5上机5排序算法直接插入排序、简单选择排序、快速排序，推排序，归并排序。M32上机1作业30第5章第5章图状结构本章重点难点：图的存储结构，图的遍历，图的应用。/////315.15.1图的定义与术语图的抽象数据类型定义，图的基本术语。M11讲授1作业325.25.2图的存储结构数组表示法，邻接表表示法；图的基本算法的实现。M11讲授1作业335.35.3图的遍历图的深度优先搜索遍历，图的广度优先搜索遍历。M22讲授3作业345.45.4图的应用连通网的最小生成树，AOV网的拓扑排序，AOE网的关键路径，网的最短路径。M34讲授6作业35上机6上机6图的存储结构与应用图的存储结构，图的遍历，最小生成树，拓扑排序，关键路径，最短路径。M32上机1作业36第6章第6章算法设计本章重点难点：递归算法，分治策略，动态规划，贪心算法，回溯法，分支限界法。/////376.16.1递归与分治法递归算法与分治策略及其应用。排列问题，棋盘覆盖问题。M32讲授1作业386.26.2动态规划算法动态规划算法及其应用。矩阵连乘问题，最长公共子序列问题，0-1背包问题，钱币组合问题，编辑距离问题。M32讲授3作业39上机7上机7递归与分治、动态规划实现几个典型问题的算法，包括排列问题、棋盘覆盖问题、最长公共子序列问题，0-1背包问题。M32上机1作业406.36.3贪心算法贪心算法及其应用。钱币组合问题，背包问题，多机调度问题。M31讲授1作业416.46.4回溯法回溯法及其应用。批处理作业调度问题，0-1背包问题，旅行商销售问题，无向图的着色问题。M32讲授3作业426.56.5分支限界法优先队列，分支限界法及其应用。0-1背包问题，旅行商销售问题，整数变换问题。M32讲授2作业43上机8上机8贪心算法、回溯法与分支限界法实现几个典型问题的算法，包括最优服务次序问题、钱币组合问题、0-1背包问题、旅行商销售问题。M32上机1作业四、考核方式序号考核环节操作细节总评占比1平时作业1.每周布置3-4个基础知识练习题、2-3个算法设计编程题。前者主要练习学生对基本概念、基本算法的理解和掌握，后者主要练习学生提高算法设计能力和算法实现能力。要求学生根据教师的批语改进作业。2.成绩采用百分制，根据作业的质量、提交是否延迟、对作业的改进情况，综合评定作业成绩。3.考核学生对数据的存储结构与算法的掌握水平、编程实现算法的能力、综合运用课程知识求解问题的能力。40%2期末考试1.半开卷考试，成绩采用百分制，卷面成绩总分100分。2.主要考核学生对本课程的基本知识的掌握情况好算法设计与实现的能力。题型包括两类：一类题以填空、简答、绘图、填表等形式考核学生对数据结构的基本概念、存储方式、基本算法的掌握情况。一类是编程题，考核学生的算法设计与实现水平。50%3平时表现根据学生的考勤情况、学习态度、课堂回答问题情况与课外师生讨论交流情况综合评定成绩。10%五、评分细则序号课程目标考核环节大致占比评分等级1M1平时作业40%A-按时完成全部作业、首次提交的作业质量很高，作业偶尔有质量问题，能尽快把作业修改好。B-基本按时完成绝大部分的作业，作业质量较高，对有问题的作业多数能修改好。C-完成大部分作业，或者作业迟交比较严重，或者作业质量较低，对作业修改后仍有部分作业有质量问题。D-作业有作弊现象，或者完成作业比例太低，或者作业迟交严重或者作业质量太低并且忽视批语而不改进作业。2M1期末考试40%（见试卷评分标准）3M1平时表现20%A-无旷课现象，学习态度端正，学习认真主动努力，课堂积极问答问题，遇到疑难问题时能主动与教师或同学交流讨论。B旷课不超过1次，学习态度基本端正、学习比较认真、课堂回答问题较好、遇到疑难问题时有时与教师或同学讨论。C-旷课2-3次，学习态度一般、学习不够认真不够主动、课堂不主动答题或回答质量较低，遇到疑难问题时很少与教师或同学交流讨论。D-旷课4次以上次，学习态度较差、学习不认真不努力、课堂不回答问题或回答错误太多，几乎不与教师或同学交流讨论学习问题。4M2平时作业50%A-按时完成全部作业、首次提交的作业质量很高，作业偶尔有质量问题，能尽快把作业修改好。B基本按时完成绝大部分的作业，作业质量较高，对有问题的作业多数能修改好。C-完成大部分作业，或者作业迟交比较严重，或者作业质量较低，对作业修改后仍有部分作业有质量问题。D-作业有作弊现象，或者完成作业比例太低，或者作业迟交严重或者作业质量太低并且忽视批语而不改进作业。5M2期末考试30%（见试卷评分标准）6M2平时表现20%A-无旷课现象，学习态度端正，学习认真主动努力，课堂积极问答问题，遇到疑难问题时能主动与教师或同学交流讨论。B-旷课不超过1次，学习态度基本端正、学习比较认真、课堂回答问题较好、遇到疑难问题时有时与教师或同学讨论。C-旷课2-3次，学习态度一般、学习不够认真不够主动、课堂不主动答题或回答质量较低，遇到疑难问题时很少与教师或同学交流讨论。D-旷课4次以上次，学习态度较差、学习不认真不努力、课堂不回答问题或回答错误太多，几乎不与教师或同学交流讨论学习问题。7M3平时作业50%A-按时完成全部作业、首次提交的作业质量很高，作业偶尔有质量问题，能尽快把作业修改好。B-基本按时完成绝大部分的作业，作业质量较高，对有问题的