《数据结构与算法（C++）》课程教学大纲.docx

数据结构与算法（C+）课程教学大纲课程英文名称：Data Structures and Algorithms （C+）课程编号：HZ192120课程类别：学科（大类）教育平台课程性质：必修课学分：2学时：32 （其中：讲课学时：32实验学时：。上机学时：0）适用专业：测绘工程开课部门：环境与资源学院测绘与地理信息工程系先修课程：程序设计基础（C+）、程序设计基础（C+）实验后续课程：测量程序设计一、课程目标通过本课程的学习，使学生具备以下能力：1 .掌握常用数据结构的基本概念及其在不同存储结构上的实现方法，具备分 析算法的优缺点和改进算法设计的能力；.掌握线性表、栈和队列、树等数据结构的运算原理，具备能编写程序对测绘工程问题进行预测与模拟的能力。二、课程目标与毕业要求的对应关系课程目标指标点毕业要求课程目标14.2能够基于专业理论知识对研究方案进 行设计、论证与预测。4.研究：能够基于科学原理并采用科学方法 对复杂测绘工程实践问题进行研究，通过实 验设计与实施，对结果进行分析、验证、解 释，综合多源信息得到合理有效的结论。课程目标25.3能够开发或选择相应的测绘仪器及软 件，对复杂测绘工程问题进行预测与模 拟，并能够理解其局限性。5.使用现代工具：能够针对复杂的测绘工程 问题，合理地选择、开发与使用现代测绘工 具、技术与资源，包括对工程问题的模拟与 预测，并能够理解其局限性。三、课程目标与教学内容和教学方法的对应关系单元数据结构与算法（C+）教学内容教学方法课程目标教学环节训练环节1绪论授课2学时课堂作业、课外作业12线性表授课4学时课堂作业、课外作业1、23栈和队列授课5学时课堂作业、课外作业1、24串和数组授课3学时1、25树授课6学时课堂作业、课外作业1、26图授课2学时课外作业1、27排序授课2学时课堂作业、课外作业1、2Ui、课程内容(一)理论学时局部第一单元 绪论(2学时，支撑课程目标1)知识点本章要求学生了解数据结构的一些基本概念：数据、数据元素、数据逻辑结 构、数据存储结构、数据类型、算法等，掌握并熟悉运用抽象数据类型，描述算 法所用的C#语言中的一些有关问题，算法时间复杂度和空间复杂度的分析。重 点数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法，抽象数 据类型。难 点算法时间复杂度和空间复杂度的分析。基本要求1,识. . 记：数据结构的研究内容。2.领会:3 .简单应用：4 .综合应用：第二单元线性表 知识点(1)抽象数据类型的表示和实现；(2)算法的定义和特性；(3)评价算法优劣的基本标准。(1)简单数据结构的程序设计；(2)简单数据结构程序的时间复杂度和空间复杂度分析。(1)数据结构的一些基本概念；(2)算法的时间复杂度分析。(4学时，支撑课程目标1、2)本章要求学生了解线性表的基本概念和类型定义，熟悉掌握线性表的顺序存 储结构以及线性表的链接存储结构，能够熟练的运用单链表的查找、插入和删除, 掌握并熟练运用循环链表，双向链表。重 点线性表的顺序存储结构，线性表的链接存储结构，单链表的查找、插入和删 除，循环链表，双向链表。难 点单链表的查找、插入和删除，循环链表，双向链表。基本要求1 .识 记:1 .识 记:(1)线性表的定义;(2)线性表的特点。2.领.会：(1)线性表的抽象数据类型定义。3简单应用：(1)线性表的顺序存储和基本操作实现;(2)单链表的存储和基本实现;(3)双链表的存储和基本实现。4.综合应用：（1） 一般线性表的合并；（2）有序表的合并。第三单元 栈和队列（5学时，支撑课程目标1、2）知识点本章要求学生了解栈和队列的类型定义，栈和队列的顺序存储和链接存储的 表示，掌握栈和队列的顺序存储和链接存储上进行常见栈操作的算法。重 点栈的顺序存储；队列的顺序存储和链接存储。难 点栈的链接存储；队列的顺序存储和链接存储。基本要求1 .识.记：栈和队列的类型定义。2 .领.会：栈和队列的存储结构表示和实现。3 简单应用：中缀与后缀表达式转换及求值；队列的顺序表实现及链表实现 方式。4 .综合应用：利用栈实现迷宫求解问题；利用队列模拟汽车加油站问题。第四单元 串和数组（3学时，支撑课程目标1、2）知识点本章要求学生了解串的定义，串的顺序存储和链接存储的表示，掌握在串的 查找算法与匹配算法；了解数组的定义，数组的顺序存储和数组的插入和删除， 掌握转置矩阵的三元表示方法。重 点串的顺序存储和链接存储；数组的顺序存储。难 点串的查找与匹配；数组的查找与匹配。基本要求1 .识.记：串的表示和实现方式；数组的存储方法、特殊存储结构。2 .领.会：串的插入与查找；特殊矩阵的压缩存储。3简单应用：串的简单匹配算法实现；二维矩阵的一维数组三元表示方法。4.综合应用：快速模式匹配算法；根据矩阵的特点，选用合适的数组压缩算 法，实现转置矩阵的快速转置。第五单元树（6学时，支撑课程目标1、2）知识点本章要求学生了解树的定义、性质和表示方法，重点掌握二叉树的定义、性 质和存储结构以及二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求 二叉树深度等的操作方法及实现，熟悉掌握树的存储结构，进行先根遍历、后根 遍历和按层遍历的方法及实现，进行树与二叉树的转换方法；了解树和森林的定 义、性质和表示方法，重点掌握熟悉掌握树的存储结构，进行先根遍历、后根遍 历和按层遍历的方法及实现，进行树、森林与二叉树的转换方法。重 点二叉树的定义、性质和存储结构，建立二叉树、输出二叉树、求二叉树深度 等的操作方法及实现；树和森林的定义、性质和存储结构。难 点树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现。基本栗求1.识记：二叉树的定义；树和森林的定义。2,领会：(1)二叉树的术语；(2)特殊的二叉树；(3)树的遍历方式。3 .简单应用：二叉树的三种表示方法及存储结构；树、森林和二叉树的转换。4 .综合应用：(1)二叉树的性质；(2)二叉树的遍历方法：先序、中序与后序；(3)实现树的哈夫曼编码。第六单元 图(2学时，支撑课程目标1、2)知识点本章要求学生了解图的定义和术语，熟练掌握图的邻接矩阵、邻接表和边集 数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树，了解拓扑 排序。重 点图的邻接矩阵、邻接表和边集；数组表示，图的深度和广度优先搜索历，图 的生成树和最小生成树。难 点图的深度和广度优先搜索遍历，图的生成树和最小生成树。基本要求1 ,识 . .记：图的定义和术语。2 .领.会：(1)图的邻接矩阵表示法；(2)图的邻接表表示法。3 .简单应用：图的遍历方法：深度优先遍历、广度优先遍历。4 .综合应用：(1)拓扑排序和关键路径；(2)最短路径问题算法：迪杰斯特拉算法。第七单元 排序(2学时，支撑课程目标1、2)知识点本章要求学生了解排序的概念，掌握直接插入排序，冒泡排序和快排序，直 接选择排序和堆排序，归并排序等排序算法。重 点直接插入排序，冒泡排序和快排序，直接选择排序。难 点冒泡排序和快排序，直接选择排序，堆排序，归并排序。基本要求1 .识. . .记：排序的基本概念。2 .领 会：常见的排序算法及各算法的优劣。3 .简单应用：简单项选择择排序、堆排序、二路归并排序的编程实现。4 .综合应用：直接插入排序、折半插入排序、希尔排序、快速排序、冒泡 排序的编程实现；排序算法分析。【学时分配】五、教学方法与手段知识单元理论学时第1单元绪论2第2单元线性表2第3单元栈和队列5第4单元串和数组5第5单元树6第6单元图2第7单元排序2合计241 .坚持传统教学手段与现代教学手段相结合，教学内容安排要突出重点和难 点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的案例、图表， 使复杂的理论变得简单、直观，力求化难为易，努力提高学生的学习兴趣。2 .注重应用启发式教学、开展课堂讨论等教学方法，引导学生积极思考问题、 分析问题，拓展学生的思维。3、注重课后编程练习，大力培养学生动脑、动手、独立解决问题的能力。 六、考核要求、方式与成绩评定考核要求：需覆盖大纲中各知识单元全部教学内容，主要是教材中重要的基 本原理和基本方法的应用，亦会少量涉及到补充的内容或布置的参考资料内容。 考试范围不超过大纲的内容。考核形式：考试+考查。成绩评定：课程考核选择百分制模式，期末考试与实验考查相结合。课程考 核总评成绩由三局部构成，具体包括期末考试成绩（60%）、课堂作业和课堂表 现（20%）、课外作业成绩（20%） o评价环节评估课程目标对应毕业要求期末考试名词解释、填空题、选择题、简答题、算法 题等题型课程目标1、24. 1, 4.2课堂作业和课外会随教学进度屡次提交评分，每次评分在作业总成绩中所占 比重由授课教师根据作业量和难度确定，评分标准参考下表。作业成绩评定标准七、选用教材、讲义和主要参考书序号评定工程内容分值总分值1作业未完成作业0-30 分100分虽完成作业，但答案错误较多30-65 分独立完成作业，答案有错误65-85 分独立完成作业，答案有个别错误85-100 分1、推荐教材：(1)数据结构与算法分析(C+语言版)，张琨、张宏、朱保平，人 民邮电出版社，2016年2月 2、推荐参考书：(1)数据结构(C+语言版)(第3版)，邓俊辉，清华大学出版社， 2020年3月(2)数据结构与算法教程(C+版)，唐宁九，清华大学出版社，2012 年12月(3)数据结构与算法(C+版)实验和课程设计教程，唐宁九，清华 大学出版社，2008年11月(4)大话数据结构，程杰，清华大学出版社，2011年6月1日 八、大纲说明本大纲根据【西南科技大学本科人才培养方案2019版】中测绘工程专 业培养方案制订。