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

《数据结构与算法》课程教学大纲一、课程简介课程中文名数据结构与算法课程英文名DataStructureandAlgorithm双语授课□是√否课程代码10112010课程学分5总学时数80（含实践32）课程类别□通识教育课程□公共基础课程√专业教育课程□综合实践课程□教师教育课程课程性质√必修□选修□其他课程形态□线上√线下□线上线下混合式□社会实践□虚拟仿真实验教学考核方式√闭卷□开卷□课程论文□课程作品□汇报展示√报告√课堂表现□阶段性测试□平时作业√其他（可多选）开课学院大数据与智能工程学院开课系(教研室)数据科学与大数据技术系面向专业数据科学与大数据技术开课学期第2学期先修课程C语言程序设计后续课程Python程序设计选用教材耿国华.数据结构-用C语言描述（第3版）[M].北京：高教出版社,2021.参考书目[1]严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社，2007.[2][美]马克·艾伦·维斯（Mark，Allen，Weiss）著，冯舜玺译.数据结构与算法分析-语言描述（原书第2版）.机械工业出版社,2019.课程资源[1]中国大学MOOC—西北大学：/sCourse/course_4246.html[3]中国大学MOOC—北京大学：/course/PKU-1002534001课程简介《数据结构与算法》是数据科学与大数据技术专业必修的专业核心课程，教学内容包括绪论、线性表、栈和队列、串、树和二叉树、图、查找、排序。通过理论与实践相结合的系统学习，对工程问题中用计算机解决的非数值问题进行分析、总结出计算机加工处理的数据对象的特性，用合适的抽象数据类型加以描述，以达到对问题的正确理解和描述；在对工程问题正确理解和描述的基础上，选择合适的存储结构，进行算法设计、C语言程序编写、运行调试及总结评价，从而实现问题求解。二、课程目标表1课程目标序号具体课程目标课程目标1通过数据结构与算法理论与实践相结合的系统学习，能够识别并应用合适的数学、自然科学和数据结构与算法的知识，对工程问题中用计算机解决的非数值问题进行分析、总结出计算机加工处理的数据对象的特性，用合适的抽象数据类型加以描述，以达到对问题的正确理解和描述，获得关于问题的正确结论。课程目标2能够根据明确的需求，设计出针对计算机相关工程问题的解决方案并运用C语言实施，即在对工程问题正确理解和描述的基础上，选择合适的存储结构，进行算法设计、程序编写、运行调试及总结评价，从而实现问题求解。在此过程中能够根据用户需求确定计算机软件或相关产品的设计目标、设计和实施方案，在现实约束条件下，对设计方案进行可行性研究和验证；能够在设计环节中体现创新意识，并考虑社会、安全、法律、文化以及产品使用环境等因素。课程目标3能够根据需求和软件的使用环境对产品进行验证，包括设计实验数据、综合分析研究测试结果、对结果进行评估，得到合理有效的结论。表2-1课程目标与毕业要求对应关系（数据科学与大数据技术专业）毕业要求指标点课程目标毕业要求2：问题分析：能够应用数学、自然科学、计算机科学和工程科学的基本原理，通过文献研究、数学建模、工程经验提炼等方法，在大数据应用的构思与设计阶段，识别、表达、分析大数据应用领域复杂工程问题及其解决方法，以获得有效结论。【H】2.2能够识别与表达计算系统中的关键问题，针对计算系统设计与实现的需求进行系统分析和模拟。课程目标1毕业要求3：设计/开发解决方案：能够针对大数据应用领域的复杂工程问题，综合应用数据科学与大数据技术基本原理和方法，设计、开发满足特定应用需求的系统方案，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等多维度协同发展因素。【L】3.2能够识别计算机软件系统设计与实现中的关键问题，并对方案进行持续优化，体现创新性。课程目标2毕业要求4：研究：能够基于数据科学与大数据技术的相应原理，采用科学方法对大数据应用领域中的复杂工程问题进行研究，制定技术路线、设计实验方案并开展实验，通过实验分析得到合理有效的结论。【M】4.2能够针对大数据应用领域复杂工程问题，根据解决方案进行方案设计与实施，能对设计或实施过程的中间结果或数据进行正确分析和反馈。课程目标3三、课程学习内容与方法（一）理论学习内容及要求表3-1课程目标、学习内容和教学方法对应关系序号课程模块学习内容学习任务课程目标学习重点难点教学方法学时1绪论1.数据结构与算法这门课程发展简史；研究内容及在计算机科学中的地位与作用1.拓展阅读:数值计算与非数值计算2.练习：时间和空间复杂度课程目标1重点：1.理解在非数值计算的程序设计中算机操作对象的数学模型特点明确课程的研究内容2.数据结构的基本概念及相关术语3.数据结构的形式定义4.数据结构的不同存储结构及其特点5.抽象数据类型ADT的描述方法6.抽象数据类型ADT的高级语言表示和实现方法7.算法的概念及特性难点：8.数据结构的不同存储结构及其特点9.算法的评价方法1.课堂讲授：针对第1、2、3节2.案例教学：针对第4节52.数据结构的相关概念与术语，其中包括：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、数据类型、抽象数据类型ADT课程目标13.抽象数据类型ADT的表示和实现方法课程目标14.算法及算法的评价方法课程目标32线性表1.线性表的有关概念及定义1.拓展阅读：顺序存储和链式存储的应用场景2.练习：线性表的插入和删除课程目标1重点：1.线性表的有关概念及逻辑结构特点2.顺序表上插入、删除和定位运算的实现及效率分析3.线性表定位、插入、删除运算在单链表上的实现4.循环链表、双链表5.一元多项式的表示及相加难点：6.循环链表、双链表7.一元多项式的表示及相加1.课堂讲授：针对第1、2、3节2.案例教学：针对第4节72.线性表的顺序表示及实现课程目标23.线性表的链式表示及实现课程目标24.线性表的应用：多项式及其相加课程目标33栈和队列1.栈的定义、存储表示及实现1.拓展阅读：栈和队列的应用场景2.练习：栈的多种输出序列、循环队列课程目标1重点：1.栈的定义及特点2.栈的顺序存储结构及各种运算的实现3.栈的链式存储结构及各种运算的实现4.根据实际问题选择应用栈5.队列的定义及特点；6.队列的顺序存储结构及其上的运算实现7.队列的链式存储结构及其上的运算实现8.根据实际问题选择应用队列难点：9.队列的顺序存储结构及其上的运算实现1.课堂讲授：针对第1、3节2.案例教学：针对第2、4节62.栈的应用课程目标23.队列的定义、存储表示及实现课程目标14.队列的应用课程目标24串1.串的数据类型定义1.拓展阅读：串的匹配算法课程目标1重点：1．串类型的特点2．串的各种基本操作的含义3.串的定长表示和实现4.串的堆分配表示和实现5.串的简单模式匹配（布鲁特-福斯）算法难点：6.串的定长表示和实现7.串的堆分配表示和实现1.课堂讲授：针对第1、2节2.演示教学：针对第3节32.串的存储表示和各种基本操作的实现课程目标13.串的模式匹配算法课程目标25树和二叉树1.树的定义和基本术语1.拓展阅读：平衡二叉树2.练习：二叉树的遍历课程目标1重点：1.理解树的递归定义2.理解树的有关基本概念和术语3.二叉树的定义、性质及性质的推导过程、逻辑特点及五种基本形态、基本运算4.二叉树的顺序存储结构、链式存储结构特点及其类型说明5.二叉树的三种遍历方法及其算法6.在遍历基础上实现二叉树的建立7.二叉树遍历算法的应用：二叉树各类结点的输出、数目统计、深度的计算等8.二叉树的双亲表示法、孩子表示法、孩子兄弟表示法难点：9.树的表示方法10.树或森林与二叉树的转换11.哈夫曼树和哈夫曼编码1.课堂讲授：针对第1、2节2.演示教学：针对第3、4节3.案例教学：针对第5节82.二叉树的定义、性质和存储结构课程目标13.二叉树的遍历以及遍历算法的各种描述形式课程目标14.树的存储结构、树或森林与二叉树的转换、遍历课程目标25.哈夫曼树和哈夫曼编码课程目标36图1.图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）1.拓展阅读：最小生成树的应用场景2.练习：关键路径课程目标1重点：1.图的基本概念2.图的存储表示3.图的搜索遍历4.图的连同分量、最小生成树算法5.有向图的拓扑排序算法6.关键路径7.最短路径难点：8.图的搜索遍历9.拓扑排序10.关键路径11.最短路径1.课堂讲授：针对第1节2.演示教学：针对第2、3节3.案例教学：针对第4、5节82.图的遍历与连通性：深度优先搜索；广度优先搜索课程目标23.图的连通分量。最小生成树：普里姆算法；克鲁斯卡尔算法课程目标24.拓扑排序、关键路径课程目标25.最短路径课程目标27查找1.查找的基本概念1.拓展阅读：平衡二叉树2.练习：哈希表的建立及查找课程目标1重点：1.查找表的基本概念及查找原理。2.查找效率及平均查找长度的讨论。3.顺序表的顺序查找。4.有序表的查找。5.索引顺序表的查找。6.二叉排序树7.哈希表难点：8.二叉排序树的插入、删除9.哈希表的建立及查找分析1.课堂讲授：针对第1、2、3节2.案例教学：针对第4节62.静态查找表课程目标13.动态查找表课程目标14.哈希表课程目标38排序1.排序的基本概念1.拓展阅读：内部排序与外部排序2.练习：冒泡排序和快速排序课程目标1重点：1.排序有关基本概念和术语。2.排序算法效率讨论。3.插入类排序：简单插入排序、折半插入排序、Shell排序4.交换类排序：冒泡排序、快速排序5.选择类排序：简单选择排序、树形选择排序、堆排序6.二路归并排序7.分配类排序：多关键字排序、基数排序。难点：8.Shell排序、快速排序、堆排序9.对于每种排序方法要正确理解排序的基本思想、算法策略并能进行性能分析1.课堂讲授：针对第1节2.演示教学：针对第2、3、4、5、6节52.插入类排序课程目标33.交换类排序课程目标34.选择类排序课程目标35.归并排序课程目标36.分配类排序课程目标3实验学习内容及要求表3-2课程目标、学习内容和教学方法对应关系序号项目名称项目来源教学目标（观测点、重难点）学时数项目类型要求每组人数教学方法课程目标1实验1：C语言编程复习及训练实验教材1．复习C语言的基础知识与编程技能，熟悉开发环境、程序编辑、调试运行过程4设计性实验必做1实验指导课程目标12.C语言数组的定义、操作及应用（重点）3.C语言链表的定义、操作及应用（重点）4.C语言函数知识的应用（重点）2实验2：线性表的基本操作实现及应用实验教材1.实现线性表的顺序表示及各种操作（重点）4设计性实验必做1实验指导课程目标22.实现线性表的链式表示及各种操作（重点）3.线性表的应用（难点）3实验3：栈与队列的实现及应用实验教材1.完成栈的建立、各种操作的实现及在实际问题中应用（重点）4设计性实验必做1实验指导课程目标22.完成队列的建立、各种操作的实现及在实际问题中应用（重点）4实验4：字符串处理实验教材1.综合应用字符串的存储表示，C语言提供的各种基本操作函数实现指定串的操作，完成指定的应用串的编程任务2设计性实验必做1实验指导课程目标15实验5：二叉树的表示与遍历实验教材1.完成二叉树的二叉链表的建立（重点）4设计性实验必做1实验指导课程目标12.完成二叉树的遍历：先序遍历、中序遍历、后序遍历（重点）3.完成二叉树遍历操作的应用（难点）6实验6：图的存储表示及应用实验教材1.掌握图的邻接矩阵的建立、输出及应用（重点）4综合性实验必做1实验指导课程目标12.掌握图的邻接表的建立、输出及应用（重点）7实验7：图的搜索实验教材1.用不同的存储结构表示图，按照深度优先的方法搜索输出图的各个顶点（难点）2综合性实验必做1实验指导课程目标22.用不同的存储结构表示图，按照广度优先的方法搜索输出图的各个顶点（难点）8实验8：图的拓扑排序实验教材1.选择一种存储结构表示图2综合性实验必做1实验指导课程目标22.输出图的拓扑排序序列（难点）9实验9：基本查找、排序算法的实现及应用实验教材1.选用不同的存储结构表示查找表，并在此基础上实现、应用查找算法（重点）6设计性实验必做1实验指导课程目标32.选用不同的存储结构表示记录序列，并在此基础上实现、并运用各种排序算法（重点）3.根据不同的数据特性选择存储结构、查找和排序算法来解决实际问题。（难点）四、课程考核（一）考核内容与考核方式表4-1课程目标、考核内容与考核方式对应关系课程目标考核内容所属学习模块/项目考核占比考核方式课程目标11.数据结构与算法这门课程展简史；研究内容及在计算机科学中的地位与作用绪论40%课堂交互、闭卷考试、实验报告2.数据结构的相关概念与术语，其中包括：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、数据类型、抽象数据类型ADT绪论3.抽象数据类型ADT的表示和实现方法绪论4.线性表的有关概念及定义线性表5.栈的定义、存储表示及实现栈和队列6.队列的定义、存储表示及实现栈和队列7.串的数据类型定义串8.串的存储表示和各种基本操作的实现串9.树的定义和基本术语树和二叉树10.二叉树的定义、性质和存储结构树和二叉树11.二叉树的遍历以及遍历算法的各种描述形式树和二叉树12.图的基本概念、存储表示（邻接矩阵、邻接表、十字链表，邻接多重表）图13.查找的基本概念查找14.静态查找表查找15.动态查找表查找16.排序的基本概念排序课程目标21.线性表的顺序表示及实现线性表40%课堂交互、闭卷考试、实验报告2.线性表的链式表示及实现线性表3.栈的应用栈和队列4.队列的应用栈和队列5.串的模式匹配算法串6.树的存储结构、树或森林与二叉树的转换、遍历树和二叉树7.图的遍历与连通性：深度优先搜索；广度优先搜索图8.图的连通分量。