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

1、数据结构与算法（C+）课程教学大纲课程英文名称：Data Structures and Algorithms（C+）课程编号：HZ192120课程类别：学科（大类）教育平台课程性质：必修课学分：2学时：32（其中：讲课学时：32实验学时：0上机学时：0）适用专业：测绘工程开课部门：环境与资源学院测绘与地理信息工程系先修课程：程序设计基础（C+）、程序设计基础（C+）实验后续课程：测量程序设计一、课程目标通过本课程的学习，使学生具备以下能力：1.掌握常用数据结构的基本概念及其在不同存储结构上的实现方法，具备分析算法的优缺点和改进算法设计的能力；2.掌握线性表、栈和队列、树等数据结构的运算原理，具

2、备能编写程序对测绘工程问题进行预测与模拟的能力。二、课程目标与毕业要求的对应关系课程目标指标点毕业要求课程目标14.2能够基于专业理论知识对研究方案进行设计、论证与预测。4.研究：能够基于科学原理并采用科学方法对复杂测绘工程实践问题进行研究，通过实验设计与实施，对结果进行分析、验证、解释，综合多源信息得到合理有效的结论。课程目标25.3能够开发或选择相应的测绘仪器及软件，对复杂测绘工程问题进行预测与模拟，并能够理解其局限性。5.使用现代工具：能够针对复杂的测绘工程问题，合理地选择、开发与使用现代测绘工具、技术与资源,包括对工程问题的模拟与预测，并能够理解其局限性。课程目标与教学内容和教学方法的

3、对应关系单元数据结构与算法（C+）教学内容教学方法课程目标教学环节训练环节1绪论授课2学时课堂作业、课外作业12线性表授课4学时课堂作业、课外作业1、23栈和队列授课5学时课堂作业、课外作业1、24串和数组授课3学时1、25树授课6学时课堂作业、课外作业1、26图授课2学时课外作业1、27排序授课2学时课堂作业、课外作业1、2四、课程内容（一）理论学时部分第一单元 绪论（2学时，支撑课程目标1）知 识 点本章要求学生了解数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等，掌握并熟悉运用抽象数据类型，描述算法所用的C#语言中的一些有关问题，算法时间复杂度和空间复

4、杂度的分析。重 点数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法，抽象数据类型。难 点算法时间复杂度和空间复杂度的分析。基本要求1.识 记：数据结构的研究内容。2.领 会：（1）抽象数据类型的表示和实现;（2）算法的定义和特性;（3）评价算法优劣的基本标准。3.简单应用：（1）简单数据结构的程序设计;（2）简单数据结构程序的时间复杂度和空间复杂度分析。4.综合应用：（1）数据结构的一些基本概念;（2）算法的时间复杂度分析。第二单元 线性表（4学时，支撑课程目标1、2）知 识 点本章要求学生了解线性表的基本概念和类型定义，熟悉掌握线性表的顺序存储结构以及线性表的链接存储结构，能够熟练

5、的运用单链表的查找、插入和删除，掌握并熟练运用循环链表，双向链表。重 点线性表的顺序存储结构，线性表的链接存储结构，单链表的查找、插入和删除，循环链表，双向链表。难 点单链表的查找、插入和删除，循环链表，双向链表。基本要求1.识 记：（1）线性表的定义;（2）线性表的特点。2.领 会：（1）线性表的抽象数据类型定义。3.简单应用：（1）线性表的顺序存储和基本操作实现;（2）单链表的存储和基本实现;（3）双链表的存储和基本实现。4.综合应用：（1）一般线性表的合并;（2）有序表的合并。第三单元 栈和队列（5学时，支撑课程目标1、2）知 识 点本章要求学生了解栈和队列的类型定义，栈和队列的顺序存储

6、和链接存储的表示，掌握栈和队列的顺序存储和链接存储上进行常见栈操作的算法。重 点栈的顺序存储；队列的顺序存储和链接存储。难 点栈的链接存储；队列的顺序存储和链接存储。基本要求1.识 记：栈和队列的类型定义。2.领 会：栈和队列的存储结构表示和实现。3.简单应用：中缀与后缀表达式转换及求值；队列的顺序表实现及链表实现方式。4.综合应用：利用栈实现迷宫求解问题；利用队列模拟汽车加油站问题。第四单元 串和数组（3学时，支撑课程目标1、2）知 识 点本章要求学生了解串的定义，串的顺序存储和链接存储的表示，掌握在串的查找算法与匹配算法；了解数组的定义，数组的顺序存储和数组的插入和删除，掌握转置矩阵的三元

7、表示方法。重 点串的顺序存储和链接存储；数组的顺序存储。难 点串的查找与匹配；数组的查找与匹配。基本要求1.识 记：串的表示和实现方式；数组的存储方法、特殊存储结构。2.领 会：串的插入与查找；特殊矩阵的压缩存储。3.简单应用：串的简单匹配算法实现；二维矩阵的一维数组三元表示方法。4.综合应用：快速模式匹配算法；根据矩阵的特点，选用合适的数组压缩算法，实现转置矩阵的快速转置。第五单元 树（6学时，支撑课程目标1、2）知 识 点 本章要求学生了解树的定义、性质和表示方法，重点掌握二叉树的定义、性质和存储结构以及二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现，熟

8、悉掌握树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法；了解树和森林的定义、性质和表示方法，重点掌握熟悉掌握树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树、森林与二叉树的转换方法。重 点二叉树的定义、性质和存储结构，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现；树和森林的定义、性质和存储结构。难 点 树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现。基本要求1.识 记：二叉树的定义；树和森林的定义。2.领 会：（1）二叉树的术语；（2）特殊的二叉树；（3）树的遍历方式。3.简单应用：二叉树的三种表示方法及存储结构；树、

9、森林和二叉树的转换。4.综合应用：（1）二叉树的性质；（2）二叉树的遍历方法：先序、中序与后序；（3）实现树的哈夫曼编码。第六单元 图（2学时，支撑课程目标1、2）知 识 点 本章要求学生了解图的定义和术语，熟练掌握图的邻接矩阵、邻接表和边集数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树，了解拓扑排序。重 点图的邻接矩阵、邻接表和边集；数组表示，图的深度和广度优先搜索历，图的生成树和最小生成树。难 点 图的深度和广度优先搜索遍历，图的生成树和最小生成树。基本要求1.识 记：图的定义和术语。2.领 会：（1）图的邻接矩阵表示法；（2）图的邻接表表示法。3.简单应用：图的遍历方法：深

10、度优先遍历、广度优先遍历。4.综合应用：（1）拓扑排序和关键路径；（2）最短路径问题算法：迪杰斯特拉算法。第七单元 排序（2学时，支撑课程目标1、2）知 识 点 本章要求学生了解排序的概念，掌握直接插入排序，冒泡排序和快排序，直接选择排序和堆排序，归并排序等排序算法。重 点直接插入排序，冒泡排序和快排序，直接选择排序。难 点 冒泡排序和快排序，直接选择排序，堆排序，归并排序。基本要求1.识 记：排序的基本概念。2.领 会：常见的排序算法及各算法的优劣。3.简单应用：简单选择排序、堆排序、二路归并排序的编程实现。4.综合应用：直接插入排序、折半插入排序、希尔排序、 快速排序、冒泡排序的编程实现；

11、排序算法分析。【学时分配】知识单元理论学时第1单元 绪论2第2单元 线性表2第3单元 栈和队列5第4单元 串和数组5第5单元 树6第6单元 图2第7单元 排序2合计24五、教学方法与手段1.坚持传统教学手段与现代教学手段相结合，教学内容安排要突出重点和难点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的案例、图表，使复杂的理论变得简单、直观，力求化难为易，努力提高学生的学习兴趣。2.注重应用启发式教学、开展课堂讨论等教学方法，引导学生积极思考问题、分析问题，拓展学生的思维。3、注重课后编程练习，大力培养学生动脑、动手、独立解决问题的能力。六、考核要求、方式与成绩评定考核要求：需覆盖大纲

12、中各知识单元全部教学内容，主要是教材中重要的基本原理和基本方法的应用，亦会少量涉及到补充的内容或布置的参考资料内容。考试范围不超过大纲的内容。考核形式：考试+考查。成绩评定：课程考核选择百分制模式，期末考试与实验考查相结合。课程考核总评成绩由三部分构成，具体包括期末考试成绩（60%）、课堂作业和课堂表现（20%）、课外作业成绩（20%）。评价环节评估课程目标对应毕业要求期末考试名词解释、填空题、选择题、简答题、算法题等题型课程目标1、24.1，4.2课堂作业和课外会随教学进度多次提交评分，每次评分在作业总成绩中所占比重由授课教师根据作业量和难度确定，评分标准参考下表。作业成绩评定标准序号评定项

13、目内容分值总分值1作业未完成作业0-30分100分虽完成作业，但答案错误较多30-65分独立完成作业，答案有错误65-85分独立完成作业，答案有个别错误85-100分七、选用教材、讲义和主要参考书1、推荐教材：（1）数据结构与算法分析（C+语言版）， HYPERLINK /?key2=%D5%C5%E7%FB&medium=01&category_path=01.00.00.00.00.00 t _blank 张琨、 HYPERLINK /?key2=%D5%C5%BA%EA&medium=01&category_path=01.00.00.00.00.00 t _blank 张宏、 HYPERLINK /?key2=%D6%EC%B1%A3%C6%BD&medium=01&category_path=01.00.00.00.00.00 t _blank 朱保平，人民邮