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

1、PAGE 10PAGE 9数据结构与算法（C#）课程教学大纲课程英文名称：Data Structures and Algorithms （C#）课程编号：HZ162480课程类别：学科（大类）教育平台课程性质：必修学 分：2学 时：32（其中：讲课学时：24， 实验学时：8）适用专业：地理信息科学开课部门：环境与资源学院先修课程：C#程序设计语言A、地理信息系统基础A等后续课程：GIS二次开发、GIS软件工程等一、课程目标本课程的教学任务是针对大量的信息处理对象，介绍对象信息与数据表示的各种抽象的、基本的逻辑结构及其上的基本运算操作。通过研究各种基本数据结构内在的逻辑关系和它们在计算机中的存储

2、表示方式，初步建立数据结构上基本运算操作的正确性概念，同时，结合各种典型问题讨论其上的各种基本运算操作及其基本算法，讲授各种数据结构的特点、适用范围，以及对一些基本算法效率的定性和定量分析方法，为后续课程提供必要的数据结构基础。此外，配合实验课程的教学中，学生应理论联系实际，理论指导实践，通过规范地完成一系列数据结构实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高。通过该课程理论教学与上机实验，达到以下的教学目标：通过学习本门课程，提高学生的逻辑思维能力、数学运算能力以及应用数据结构方法解决实际当中遇到的编程问题，从而提高学生的数学建模能力与编程能力。能够应用数据结构的概

3、念和方法，将现实物理世界中的抽象问题转为地理信息世界中的数学问题，从而具备应用数学模型的解决问题的能力与一定的地理信息问题重构思维。二、课程目标与毕业要求的对应关系课程目标指标点毕业要求课程目标11.1通过学习数学提高抽象思维能力、逻辑推理能力、数学运算能力以及应用掌握数学建模方法解决实际问题的能力。1掌握数学、自然科学、地理信息基础和专业知识，具备地球空间数据采集、获取与应用能力、地球空间信息数据处理与建库能力。课程目标22.1能够应用数学和自然科学基本方法，将地理信息工程问题转化、表述为数学问题进行分析。2能够应用数学、自然科学和地理信息科学的基本原理，识别、表达、并通过文献研究分析地理信

4、息专业问题，具备地理信息系统的架构能力。课程目标34.2能够利用新技术和计算机技术，进行创新性实验设计，并通过分析解释和改进，得到合理有效的结论 4 能够基于科学原理并采用科学方法对复杂工程实践问题进行研究，通过实验设计与实施，对结果进行分析、解释，综合多源信息得到合理有效的结论，具备科学研究的初步能力。三、课程目标与教学内容和教学方法的对应关系数据结构理论数据结构实验教学内容教学方法课程目标实验项目课程目标教学环节训练环节1数据结构和算法简介授课2学时 12解决线性表的编程问题授课2学时作业111. 线性表的操作（2个学时）13解决堆栈的编程问题授课2学时作业224解决队列编程问题授课3学时

5、作业31、22 栈与队列的程序编制（2个学时）1、25解决串的编程问题授课3学时作业41、36解决数组的编程问题授课2学时作业51、2、37解决二叉树的问题授课3学时作业62/38解决树的编程问题授课3学时作业71、2、33二叉树的基本操作（2个学时）1、2、39解决图的编程问题授课2学时作业81、2、310执行排序算法授课2学时作业91、2、34图与排序的编程实现（2个学时）1、2、3合计24学时8学时四、课程的主要内容及基本要求（一）理论学时部分第一章 数据结构和算法简介（2学时）（支撑课程目标1）知 识 点 本章要求学生了解数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结

6、构、数据类型、算法等，掌握并熟悉运用抽象数据类型，描述算法所用的C#语言中的一些有关问题，算法时间复杂度和空间复杂度的分析。重 点 数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法，抽象数据类型。难 点 算法时间复杂度和空间复杂度的分析。基本要求识 记：数据结构的研究内容。领 会:（1）抽象数据类型的表示和实现。（2）算法的定义和特性。（3）评价算法优劣的基本标准。简单应用:（1）简单数据结构的程序设计。（2）简单数据结构程序的时间复杂度和空间复杂度分析。综合应用:（1）数据结构的一些基本概念。（2）算法的时间复杂度分析。第二章 解决线性表的编程问题（2学时）（支撑课程目标1）知 识

7、 点 本章要求学生了解线性表的基本概念和类型定义，熟悉掌握线性表的顺序存储结构以及线性表的链接存储结构，能够熟练的运用单链表的查找、插入和删除，掌握并熟练运用循环链表，双向链表。重 点 线性表的顺序存储结构，线性表的链接存储结构，单链表的查找、插入和删除，循环链表，双向链表。难 点 单链表的查找、插入和删除，循环链表，双向链表。基本要求识 记:（1）线性表的定义。 (2）线性表的特点。领 会:（1）线性表的抽象数据类型定义。简单应用:（1）线性表的顺序存储和基本操作实现。（2）单链表的存储和基本实现。（3）双链表的存储和基本实现。综合应用:（1）一般线性表的合并。（2）有序表的合并第三章 解决

8、堆栈的编程问题（2学时）（支撑课程目标2）知 识 点 本章要求学生了解栈的类型定义，栈的顺序存储和链接存储的表示，掌握在栈的顺序存储和链接存储上进行常见栈操作的算法。重 点 栈的顺序存储。难 点 栈的链接存储。基本要求识 记：栈的类型定义。领 会：栈的存储结构表示和实现。简单应用：中缀与后缀表达式转换及求值。综合应用：利用栈实现迷宫求解问题。第四章 解决队列的编程问题（3学时）（支撑课程目标1、2）知 识 点 本章要求学生了解队列的类型定义，掌握队列的顺序存储和链接存储表示及各种操作的实现算法。重 点队列的顺序存储和链接存储。难 点 队列的顺序存储和链接存储。基本要求识 记：识记队列的类型定义

9、。领 会：队列的存储结构标识和实现。简单应用：队列的顺序表实现及链表实现方式。综合应用：利用队列模拟汽车加油站问题。第五章 解决串的编程问题（3学时）（支撑课程目标1、3）知 识 点 本章要求学生了解串的定义，串的顺序存储和链接存储的表示，掌握在串的查找算法与匹配算法。重 点串的顺序存储和链接存储。难 点串的查找与匹配。基本要求识 记：串的表示和实现方式。领 会：串的插入与查找。简单应用：串的简单匹配算法实现。综合应用：快速模式匹配算法。第六章 解决数组的编程问题（2学时）（支撑课程目标1、2、3）知 识 点 本章要求学生了解数组的定义，数组的顺序存储和数组的插入和删除，掌握转置矩阵的三元表示

10、方法。重 点数组的顺序存储。难 点 数组的查找与匹配。基本要求识 记：数组的存储方法、特殊存储结构。领 会：特殊矩阵的压缩存储。简单应用：二维矩阵的一维数组三元表示方法。综合应用：根据矩阵的特点，选用合适的数组压缩算法，实现转置矩阵的快速转置。第七章 解决二叉树的问题（3学时）（支撑课程目标2、3）知 识 点 本章要求学生了解树的定义、性质和表示方法，重点掌握二叉树的定义、性质和存储结构以及二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现，熟悉掌握树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法。重 点 二叉树的定义、性质和

11、存储结构，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现。难 点 树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现。基本要求识 记:二叉树的定义。领 会:（1）二叉树的术语。（2）特殊的二叉树。简单应用:二叉树的三种表示方法及存储结构。综合应用:（1）二叉树的性质。（2）二叉树的遍历方法：先序、中序与后序。第八章 解决树和森林的问题（3学时）（支撑课程目标1、2、3）知 识 点 本章要求学生了解树和森林的定义、性质和表示方法，重点掌握熟悉掌握树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树、森林与二叉树的转换方法。重 点 树和森林的定义、性质和存储结构。难

12、点 树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法。基本要求识 记：树和森林的定义。领 会：树的遍历方式。简单应用：树、森林和二叉树的转换。综合应用：实现树的哈夫曼编码。第九章 解决图的问题（2学时）（支撑课程目标1、2、3）知 识 点 本章要求学生了解图的定义和术语，熟练掌握图的邻接矩阵、邻接表和边集数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树，了解拓扑排序。重 点图的邻接矩阵、邻接表和边集；数组表示，图的深度和广度优先搜索，图的生成树和最小生成树。难 点 图的深度和广度优先搜索遍历，图的生成树和最小生成树。基本要求识 记: 图的定义和术

13、语。领 会:（1）图的邻接矩阵表示法。（2）图的邻接表表示法。简单应用：图的遍历方法：深度优先遍历、广度优先遍历。综合应用:（1）拓扑排序和关键路径。（2）最短路径问题算法：迪杰斯特拉算法。第十章 实现排序算法（2学时）（支撑课程目标1、2、3）知 识 点 本章要求学生了解排序的概念，掌握直接插入排序，冒泡排序和快排序，直 接选择排序和堆排序，归并排序等排序算法。重 点直接插入排序，冒泡排序和快排序，直接选择排序。难 点 冒泡排序和快排序，直接选择排序，堆排序，归并排序。基本要求识 记：排序的基本概念。领 会：常见的排序算法及各算法的优劣。简单应用：简单选择排序、堆排序、2-路归并排序的编程实

14、现。综合应用：直接插入排序、折半插入排序、希尔排序、 快速排序、冒泡排序的编程实现；排序算法分析。学时分配序号课程内容讲课1数据结构和算法简介22解决线性表的编程问题23解决堆栈的编程问题24解决队列编程问题35解决串的编程问题36解决数组的编程问题27解决二叉树的问题38解决树的编程问题39解决图的编程问题210执行排序算法2合计24（二）实验学时部分实验总共8学时：1 线性表的操作22 栈与队列的程序编制23 二叉树的基本操作24 图与排序算法的实现2合计8实验教学环节作用及目的这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程

15、序实现，能够根据实际问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。通过实验课程更好的训练学生算法分析及算法设计的能力。实验教学环节培养学生能力标准 本实验主要通过程序编制开展实验，在实验教学过程中培养学生的思维分析能力和程序开发能力，从而使学生运用程序的方式检验所学的理论知识，根据每次实验内容，按照不同的实验目的和数据组织方式，设计程序，完成不同的实验任务，使学生能够真正的做到理论与实践相结合。 实验项目、内容、学时分配及实验类型1、必开实验序号实验项目实验内容学时实验类型(演示、验证、综合、设计研究)组数每组学生人数1线性表的操作根据线性表的概

16、念，实现顺序表与链表的程序2设计12栈与队列的程序编制利用C#语言实现栈和队列两大概念，每个概念实现方式通过顺序表与链表实现。2验证13二叉树的基本操作通过构建二叉树，实现二叉树的先序，中序与后序访问与排序。2验证14图与排序算法的实现利用程序实现图的存储与访问，实现常见的3种排序算法。2综合设计12、主要仪器设备计算机、VS2010以上开发程序包。五、教学方法与手段坚持教师理论讲解与学生实践相结合，不断地吸收先进理论知识和最新管理学研究动态。理论教学要结合学生的编程大赛、课堂讨论、案例分析等展开，努力降低学生接受知识的难度，不断提高学生发现、分析和解决问题的能力。坚持传统教学手段与现代教学手

17、段相结合，教学内容安排要突出重点和难点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的案例、视频，使复杂的理论变得简单、直观，力求化难为易，努力提高学生的学习兴趣。注重应用启发式教学、开展课堂讨论等教学方法，引导学生积极思考问题、分析问题，拓展学生的思维。六、考核要求、方式与成绩评定期末考试统一命题，统一评分标准，统一考试时间。考试范围不超过大纲的内容。笔试考试，考试时间为100分钟。成绩定为百分制。实行结构评分，平时成绩占40%，期末考试成绩占60%。评价环节评估课程目标对应毕业要求平时成绩（40分）平时作业课程目标1、2、31、2、3上机实验课程目标1、2、31、2、3期末考试（6

18、0分）选择题简答题综合题课程目标1、2、31、2、3平时成绩评定标准环节评定项目内容分值总分值平时作业课程目标1、2、3方法运用基本正确，结论不明确，理论阐述不够完整;5-6分10分方法运用正确，结论正确，但理由不够充分;6-8分方法运用正确，理由充分，结论正确;8-10分上机实验课程目标1、2、3程序框架设计基本合理，但程序结果有问题，实验报告内容撰写基本完整；5-10分30分能够根据实验步骤，完成实验内容，实验报告内容撰写完整，逻辑清晰，语句通顺，实验结果基本满足要求;10-20分实验内容完成效果较好，程序设计合理，实验报告内容撰写完整，逻辑清晰，语句通顺，实验结果正确且完善;20-30分七、选用教材、讲义和主要参考书推荐教材：数据结构（C#语言版），雷军环编著，清华大学出版社，2019。 数据结构(C#语言描述) (第2版)， HYPERLINK /?key2=%B3%C2%B9%E3&medium=01&category_path=01.00.00.00.00.00 t /_blank 陈广编者，北京大学出版社，2014。推荐参考书：图解数据结构-使用C#， HYPERLINK /?key2=%CE%E2%B2%D3%C3%FA&medium=01&category_path=01.00.00.00.00.00 t /_blank 吴灿铭、 HYPERLIN