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

《数据结构与算法（C++）》课程教学大纲
课程英文名称：Data Structures and Algorithms （C++）
课程编号：HZ192120
课程类别：学科（大类）教育平台
课程性质：必修课
学分：2
学时：32 （其中：讲课学时：32实验学时：。上机学时：0）
适用专业：测绘工程
开课部门：环境与资源学院测绘与地理信息工程系
先修课程：程序设计基础（C++）、程序设计基础（C++）实验
后续课程：测量程序设计
一、课程目标通过本课程的学习，使学生具备以下能力：
1 .掌握常用数据结构的基本概念及其在不同存储结构上的实现方法，具备分 析算法的优缺点和改进算法设计的能力；.掌握线性表、栈和队列、树等数据结构的运算原理，具备能编写程序对测
绘工程问题进行预测与模拟的能力。
二、课程目标与毕业要求的对应关系
课程目标
指标点
毕业要求
课程目标1
4.2能够基于专业理论知识对研究方案进 行设计、论证与预测。
4.研究：能够基于科学原理并采用科学方法 对复杂测绘工程实践问题进行研究，通过实 验设计与实施，对结果进行分析、验证、解 释，综合多源信息得到合理有效的结论。
课程目标2
5.3能够开发或选择相应的测绘仪器及软 件，对复杂测绘工程问题进行预测与模 拟，并能够理解其局限性。
5.使用现代工具：能够针对复杂的测绘工程 问题，合理地选择、开发与使用现代测绘工 具、技术与资源，包括对工程问题的模拟与 预测，并能够理解其局限性。
三、课程目标与教学内容和教学方法的对应关系
单元
数据结构与算法（C++）
教学内容
教学方法
课程目标
教学环节
训练环节
1
绪论
授课2学时
课堂作业、课外作业
1
2
线性表
授课4学时
课堂作业、课外作业
1、2
3
栈和队列
授课5学时
课堂作业、课外作业
1、2
4
串和数组
授课3学时

1、2
5
树
授课6学时
课堂作业、课外作业
1、2
6
图
授课2学时
课外作业
1、2
7
排序
授课2学时
课堂作业、课外作业
1、2
Ui
、课程内容

(一)理论学时局部第一单元 绪论(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
合计
24
1 .坚持传统教学手段与现代教学手段相结合，教学内容安排要突出重点和难 点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的案例、图表， 使复杂的理论变得简单、直观，力求化难为易，努力提高学生的学习兴趣。
2 .注重应用启发式教学、开展课堂讨论等教学方法，引导学生积极思考问题、 分析问题，拓展学生的思维。
3、注重课后编程练习，大力培养学生动脑、动手、独立解决问题的能力。 六、考核要求、方式与成绩评定
考核要求：需覆盖大纲中各知识单元全部教学内容，主要是教材中重要的基 本原理和基本方法的应用，亦会少量涉及到补充的内容或布置的参考资料内容。 考试范围不超过大纲的内容。
考核形式：考试+考查。
成绩评定：课程考核选择百分制模式，期末考试与实验考查相结合。课程考 核总评成绩由三局部构成，具体包括期末考试成绩（60%）、课堂作业和课堂表 现（20%）、课外作业成绩（20%） o

评价环节
评估课程目标
对应毕业要求
期末考试
名词解释、填空题、选择题、简答题、算法 题等题型
课程目标1、2
4. 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版】中测绘工程专 业培养方案制订。