《数据结构》教学大纲

《数据结构》教学大纲课程编号：13180503英文名称：DataStructure学分：5学时：总学时96学时，其中理论64学时，实践32学时先修课程：高级语言课程类别：专业基础课授课对象：计算机科学与技术专业学生教学单位：机械与电气工程学院修读学期：第2学期一、课程描述和目标本课程是计算机科学与技术专业的专业基础课和核心课程，理论性和实践性都很强，既要掌握理论知识，又要进行算法设计与实现，还要上机调试运行。通过本课程的学习，使学生具备较扎实的软件技术知识和技能；使学生基本具备从现实问题抽象到信息范畴再到计算机中数据组织和处理的转换，并编程实现解决问题的能力；培养学生分析和解决较复杂问题、算法设计和程序调试的能力，为学生的专业素质和分析及解决问题的能力奠定基础。通过学习本课程，达到以下课程目标：课程目标1：学习线性结构、树结构和图结构等常用的数据结构的逻辑结构、存储结构与基于这两种结构的算法，学习查找、排序等常用算法，培养算法设计和评价的初步能力。课程目标2：能根据实际问题选择合适的数据逻辑结构和存储结构，能运用数据结构相关知识编程求解实际问题，对复杂工程问题具有一定的算法设计能力和程序调试能力。二、课程目标对毕业要求的支撑关系毕业要求指标点课程目标权重指标点1-3：能够将算法设计、面向对象程序设计思想等知识与方法，用于计算机相关领域的复杂工程问题的分析、设计与实现课程目标1课程目标2H指标点2-2：能够对计算机相关领域的复杂工程问题进行有效的表达和建模、分析和评价，具备获得有效结论的能力课程目标1课程目标2M指标点4-1：能够通过文献阅读和实验设计并采用计算机专业知识，就复杂工程应用中涉及的局部性功能或性能问题进行研究，并对结果或数据进行分析与解释课程目标2H

三、教学内容、基本要求与学时分配序号教学内容基本要求及重、难点（含德育要求）学时教学方式对应课程目标1绪论：基本概念与术语；算法的概念及其分析方法。理解数据结构、逻辑结构、存储结构、算法等基础知识；能初步理解算法分析的方法。树立学好专业知识、助力中国梦的信念；获取仰望星空、探索创新的精神动力。4讲授式讨论式课程目标12线性表：线性表的基础知识；顺序表；链表；STL之vector、list。理解线性表、顺序表和链表的概念及结构特征等知识；理解顺序表和单链表的基本操作及其算法；能应用线性表及vector、list求解实际问题。树立攻坚克难、勇于挑战的信念；获取脚踏实地、精诚合作的精神动力。8讲授式启发式探究式讨论式练习式课程目标1课程目标23栈与队列：顺序栈；链栈；循环队列；链式队列；STL之stack、queue。理解栈/队列的概念和结构特点；理解栈/队列的在顺序/链式存储结构下的基本操作方法及算法；能应用栈/队列结构及stack、queue求解实际问题。获取团队合作、探索创新的精神动力；深刻理解社会主义核心价值观。8讲授式启发式探究式讨论式练习式课程目标1课程目标24其他线性结构：串；STL之string；数组；广义表。理解串、数组和广义表的概念与术语；理解数组元素存储地址的计算方法；理解求广义表的表头、表尾、长度和深度的方法；能应用string及串相关算法求解实际问题。养成脚踏实地、精益求真的习惯；获取奋发向上、探索创新的精神动力。2讲授式讨论式练习式课程目标1课程目标25树结构：树的基本概念与术语；二叉树的概念、性质、存储结构、遍历；哈夫曼树和哈夫曼编码；树、森林与二叉树的转换。理解树的基本概念与术语；理解二叉树的概念及基础知识；理解二叉树的遍历方法和算法；理解树、森林与二叉树的转换方法；理解哈夫曼树和哈夫曼编码的构造方法和算法；能应用二叉树的相关算法求解实际问题。树立爱国情怀、文化自信；获取奋发向上、探索创新的精神动力。12讲授式启发式探究式讨论式练习式课程目标1课程目标26图结构：图的基本概念与术语；图的存储结构；图的遍历；最小生成树；最短路径；拓扑排序。理解图的基本概念与术语；理解图的邻接矩阵与邻接表；理解最小生成树、最短路径和拓扑排序的方法和算法；能应用图的遍历算法、最小生成树和最短路径的算法求解实际问题。体会勤奋学习、洞察研究的价值；获取奋发向上、探索创新的精神动力。12讲授式启发式探究式讨论式练习式课程目标1课程目标27查找：查找基础知识；顺序查找；二分查找；二叉排序树；平衡二叉树；哈希查找；STL之set、map。理解查找的有关概念及性能分析方法；理解各种查找的基础知识和相关算法的方法；理解顺序查找、二分查找、二叉排序树和哈希查找的算法；能简单分析各种查找算法的时间复杂度；能应用常用查找算法及set、map求解实际问题。坚定家国情怀和助力中国梦的信念；获取奋发向上、探索创新的精神动力。8讲授式启发式探究式讨论式练习式课程目标1课程目标28排序：排序基础知识；插入排序；冒泡排序；选择排序；快速排序；堆排序；归并排序；STL之sort、nth_element。理解排序的概念、分类、稳定性等知识；理解插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序等排序的方法和算法；能简单分析各种排序方法的时间/空间复杂度；能应用常用排序算法及sort、nth_element求解实际问题。树立正确的世界观、价值观、人生观；获取奋发向上、探索创新的精神动力。10讲授式启发式探究式讨论式练习式课程目标1课程目标2合计64序号实验项目实验内容与要求学时类型对应课程目标1大整数加法及其应用实验内容：（1）单链表的实现；（2）采用链表实现大整数加法；（3）在线相关题目求解。实验要求：必修。8设计课程目标1课程目标22栈序列匹配及其应用实验内容：（1）栈的实现；（2）栈序列匹配算法；（3）在线相关题目求解。实验要求：必修。8设计课程目标1课程目标23二叉排序树及其应用实验内容：（1）建立二叉排序树；（2）二叉排序树的查找；（3）二叉排序树的遍历；（4）在线相关题目求解。实验要求：必修。8设计课程目标1课程目标24最小生成树及其应用实验内容：（1）建立图的存储结构；（2）最小生成树算法；（3）在线相关题目求解。实验要求：必修。8设计课程目标1课程目标2合计32注：实验要求包括必修、选修；实验类型包括演示、验证、综合、设计等，后两类占比大于80%。四、课程教学方法线上教学与线下教学相结合；集中讲授与探究式教学及翻转课堂相结合；采用讲授式、启发式、探究式、讨论式和练习式等教学方式。五、学业评价和课程考核（一）考核方式及具体要求序号考核方式课程目标1（分值）课程目标2（分值）合计1平时作业55102课程实验55103平时表现1010204期中考试73105期末考试351550课程目标对应分值6238100（二）考核与评价标准1.平时作业考核与评价标准观测点分值90-100分70-89分60-69分0-59分平时作业按时完成，90%以上的作业内容齐全，基本知识点理解、掌握到位。能够利用理论知识编程求解具体问题。按时完成，70%以上的作业内容齐全，基本知识点理解、掌握得较为到位。能够较好地利用理论知识编程求解具体问题。延时完成，60%以上的作业内容齐全，基本知识点理解、掌握得基本到位。基本能够利用理论知识编程求解具体问题。不交和补交，50%以下的作业内容齐全，基本知识点理解、掌握有偏差。基本不能利用理论知识编程求解具体问题。2.课程实验考核与评价标准观测点分值90-100分70-89分60-69分0-59分课程实验能根据实验要求自主设计实验方案，有自己的设计理念，实验完成度高，效果好。实验报告内容完整。能根据实验要求自主设计实验方案，有自己的设计理念，实验完成度较高，效果较好。实验报告比较完整。能根据实验要求自主设计实验方案，实验完成度一般，效果一般。实验报告基本完整。基本能根据实验要求自主设计实验方案，实验完成度较差，效果较差。实验报告不完整。3.平时表现与评价标准根据回答问题、课堂表现、团队合作及课程网站的微课学习、测验、测试及讨论等完成情况及评分标准评分（百分制）。4.期中考试与评价标准根据期中考试及评分标准评分（百分制）。5.期末考试与评价标准根据期末考试及评分标准评分（百分制）。六、教材与参考书（一）推荐教材《数据结构与算法》，黄龙军主编，上海交通大学出版社，2022年7月版。（二）参考资料1．《数据结构（C语言版）（第2版）》，严蔚敏主编，人民邮电出版社，2015年2月版；2．《数据结构（第2版）》，陈越主编，高等教育出版社，2016年6月版；3