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

数据结构与算法(C#)课程教学大纲课程英文名称：Data Structures and Algor ithms (C#)课程编号：HZ 162480课程类别：学科(大类)教育平台课程性质：必修学 分：2学 时：32 (其中：讲课学时：24,实验学时：8)适用专业：地理信息科学开课部门：环境与资源学院先修课程：C#程序设计语言A、地理信息系统基础A等后续课程：GIS二次开发、GIS软件工程等一、课程目标本课程的教学任务是针对大量的信息处理对象，介绍对象信息与数据表示的 各种抽象的、基本的逻辑结构及其上的基本运算操作。通过研究各种基本数据结 构内在的逻辑关系和它们在计算机中的存储表示方式，初步建立数据结构上基本 运算操作的正确性概念，同时，结合各种典型问题讨论其上的各种基本运算操作 及其基本算法，讲授各种数据结构的特点、适用范围，以及对一些基本算法效率 的定性和定量分析方法，为后续课程提供必要的数据结构基础。此外，配合实验 课程的教学中，学生应理论联系实际，理论指导实践，通过规范地完成一系列数 据结构实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步 的提高。通过该课程理论教学与上机实验，到达以下的教学目标：1 .通过学习本门课程，提高学生的逻辑思维能力、数学运算能力以及应用 数据结构方法解决实际当中遇到的编程问题，从而提高学生的数学建模能力与编 程能力。2 .能够应用数据结构的概念和方法，将现实物理世界中的抽象问题转为地 理信息世界中的数学问题，从而具备应用数学模型的解决问题的能力与一定的地 理信息问题重构思维。二、课程目标与毕业要求的对应关系课程目标指标点毕业要求课程目标11.1通过学习数学提 高抽象思维能力、逻 辑推理能力、数学运 算能力以及应用掌握 数学建模方法解决实 际问题的能力。1掌握数学、自然科学、地理信息基础和专业知识， 具备地球空间数据采集、获取与应用能力、地球空 间信息数据处理与建库能力。2,本课程为学生编程开发打下一定的基础，要到达用人单位实际需要编程 能力，还有待于课后多做练习，并不断学习。103 .本大纲的编写，是课程组集体智慧的结晶。课程目标22. 1能够应用数学和 自然科学基本方法， 将地理信息工程问题 转化、表述为数学问 题进行分析。2能够应用数学、自然科学和地理信息科学的基本 原理，识别、表达、并通过文献研究分析地理信息 专业问题，具备地理信息系统的架构能力。课程目标34.2能够利用新技术 和计算机技术，进行 创新性实验设计，并 通过分析解释和改 进，得到合理有效的 结论4能够基于科学原理并采用科学方法对复杂工程实 践问题进行研究，通过实验设计与实施，对结果进 行分析、解释，综合多源信息得到合理有效的结论， 具备科学研究的初步能力。三、课程目标与教学内容和教学方法的对应关系数据结构理论数据结构实验教学内容教学方法课程目标实验工程课程目标教学环节训练环节1数据结构和算 法简介授课2学 时12解决线性表的 编程问题授课2学 时作业111.线性表的操 作（2个学时）13解决堆栈的编 程问题授课2学 时作业224解决队列编程 问题授课3学 时作业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）知识点本章要求学生了解数据结构的一些基本概念：数据、数据元素、数 据逻辑结构、数据存储结构、数据类型、算法等，掌握并熟悉运用抽象数据类型, 描述算法所用的C#语言中的一些有关问题，算法时间复杂度和空间复杂度的分 析。重 点数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法, 抽象数据类型。难点1算法时间复杂度和空间复杂度的分析。基本要求识 记：数据结构的研究内容。1. 领 会：(1)抽象数据类型的表示和实现。(2)算法的定义和特性。(3)评价算法优劣的基本标准。2. 简单应用：(1)简单数据结构的程序设计。(2)简单数据结构程序的时间复杂度和空间复杂度分析。4.综合应用：(1)数据结构的一些基本概念。(2)算法的时间复杂度分析。第二章 解决线性表的编程问题(2学时)(支撑课程目标1) 知识点1本章要求学生了解线性表的基本概念和类型定义，熟悉掌握线性表 的顺序存储结构以及线性表的链接存储结构，能够熟练的运用单链表的查找、插 入和删除，掌握并熟练运用循环链表，双向链表。重 点线性表的顺序存储结构，线性表的链接存储结构，单链表的查找、插入和删除，循环链表，双向链表。难点1单链表的查找、插入和删除，循环链表，双向链表。基本要求识记：(1)线性表的定义。(2)线性表的特点。1. 领会：(1)线性表的抽象数据类型定义。2. 简单应用：(1)线性表的顺序存储和基本操作实现。(2)单链表的存储和基本实现。（3）双链表的存储和基本实现。4.综合应用：（1） 一般线性表的合并。（2）有序表的合并第三章 解决堆栈的编程问题（2学时）（支撑课程目标2）知识点本章要求学生了解栈的类型定义，栈的顺序存储和链接存储的表示, 掌握在栈的顺序存储和链接存储上进行常见栈操作的算法。重 点栈的顺序存储。难 点栈的链接存储。基本要求识记：栈的类型定义。1. 领会：栈的存储结构表示和实现。2. 简单应用：中缀与后缀表达式转换及求值。3. 综合应用：利用栈实现迷宫求解问题。第四章 解决队列的编程问题（3学时）（支撑课程目标1、2）知 识 点本章要求学生了解队列的类型定义，掌握队列的顺序存储和链接存 储表示及各种操作的实现算法。重点队列的顺序存储和链接存储。难 点1队列的顺序存储和链接存储。基本要求识记：识记队列的类型定义。1. 领会：队列的存储结构标识和实现。2. 简单应用：队列的顺序表实现及链表实现方式。3. 综合应用：利用队列模拟汽车加油站问题。第五章解决串的编程问题（3学时）（支撑课程目标1、3）知 识 点本章要求学生了解串的定义，串的顺序存储和链接存储的表示，掌 握在串的查找算法与匹配算法。重 点串的顺序存储和链接存储。难点串的查找与匹配。基本要求识记：串的表示和实现方式。1. 领会：串的插入与查找。2. 简单应用：串的简单匹配算法实现。3. 综合应用：快速模式匹配算法。第六章 解决数组的编程问题（2学时）（支撑课程目标1、2、3）知 识 点.本章要求学生了解数组的定义，数组的顺序存储和数组的插入和删 除，掌握转置矩阵的三元表示方法。重点J数组的顺序存储。难点.数组的查找与匹配。基本要求识记：数组的存储方法、特殊存储结构。1. 领会：特殊矩阵的压缩存储。2. 简单应用：二维矩阵的一维数组三元表示方法。3. 综合应用：根据矩阵的特点，选用合适的数组压缩算法，实现转置矩阵的快速转置。第七章解决二叉树的问题（3学时）（支撑课程目标2、3）知识点本章要求学生了解树的定义、性质和表示方法，重点掌握二叉树的 定义、性质和存储结构以及二叉树的各种遍历方法及实现，建立二叉树、输出二 叉树、求二叉树深度等的操作方法及实现，熟悉掌握树的存储结构，进行先根遍 历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法。重. 点二叉树的定义、性质和存储结构，建立二叉树、输出二叉树、求二 叉树深度等的操作方法及实现。难 点1 树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现。基本要求识记：二叉树的定义。1. 领会：（1）二叉树的术语。（2）特殊的二叉树。2. 简单应用：二叉树的三种表示方法及存储结构。3. 综合应用：（1）二叉树的性质。（2）二叉树的遍历方法：先序、中序与后序。第八章 解决树和森林的问题（3学时）（支撑课程目标1、2、3）知识点本章要求学生了解树和森林的定义、性质和表示方法，重点掌握熟 悉掌握树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行 树、森林与二叉树的转换方法。重 点树和森林的定义、性质和存储结构。难 点树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现, 进行树与二叉树的转换方法。基本要求识记：树和森林的定义。1. 领会：树的遍历方式。2. 简单应用：树、森林和二叉树的转换。3. 综合应用：实现树的哈夫曼编码。第九章 解决图的问题（2学时）（支撑课程目标1、2、3）知 识 点本章要求学生了解图的定义和术语，熟练掌握图的邻接矩阵、邻接 表和边集数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树, 了解拓扑排序。重点图的邻接矩阵、邻接表和边集；数组表示，图的深度和广度优先搜索,图的生成树和最小生成树。难 点图的深度和广度优先搜索遍历，图的生成树和最小生成树。基本要求识记：图的定义和术语。1. 领会：（1）图的邻接矩阵表示法。（2）图的邻接表表示法。2. 简单应用：图的遍历方法：深度优先遍历、广度优先遍历。3. 综合应用：（1）拓扑排序和关键路径。（2）最短路径问题算法：迪杰斯特拉算法。第十章 实现排序算法（2学时）（支撑课程目标1、2、3）知 识 点本章要求学生了解排序的概念，掌握直接插入排序，冒泡排序和快 排序，直接选择排序和堆排序，归并排序等排序算法。重点直接插入排序，冒泡排序和快排序，直接选择排序。难 点冒泡排序和快排序，直接选择排序，堆排序，归并排序。基本要求识记：排序的基本概念。1. 领会：常见的排序算法及各算法的优劣。2. 简单应用：简单项选择择排序、堆排序、2-路归并排序的编程实现。3. 综合应用：直接插入排序、折半插入排序、希尔排序、快速排序、 冒泡排序的编程实现；排序算法分析。学时分配序号课程内容讲课1数据结构和算法简介22解决线性表的编程问题23解决堆栈的编程问题24解决队列编程问题35解决串的编程问题36解决数组的编程问题27解决二叉树的问题38解决树的编程问题39解决图的编程问题210执行排序算法2合计24（二）实验学时局部实验总共8学时:1线性表的操作22栈与队列的程序编制23二叉树的基本操作24图与排序算法的实现2合计8实验教学环节作用及目的这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题 选取合适的存储方案设计出简洁、高效、实用的算法，为后续课程的学习及软件 开发打下良好的基础。通过实验课程更好的训练学生算法分析及算法设计的能 力。实验教学环节培养学生能力标准本实验主要通过程序编制开展实验，在实验教学过程中培养学生的思维分析 能力和程序开发能力，从而使学生运用程序的方式检验所学的理论知识，根据每 次实验内容，按照不同的实验目的和数据组织方式，设计程序，完成不同的实验 任务，使学生能够真正的做到理论与实践相结合。实验工程、内容、学时分配及实验类型1、必开实验序号实验工程实验内容学时实验类型（演示、 验证、综合、设计 研究）组数每组学生 人数1线性表的 操作根据线性表的概念，实现 顺序表与链表的程序2设计12栈与队列 的程序编 制利用C#语言实现栈和队 列两大概念，每个概念实 现方式通过顺序表与链 表实现。2验证13二叉树的 基本操作通过构建二叉树，实现二 叉树的先序，中序与后序 访问与排序。2验证14图与排序 算法的实 现利用程序实现图的存储 与访问，实现常见的3种 排序算法。2综合设计12、主要仪器设备计算机、VS2010以上开发程序包。五、教学方法与手段1,坚持教师理论讲解与学生实践相结合，不断地吸收先进理论知识和 最新管理学研究动态。理论教学要结合学生的编程大赛、课堂讨论、案例分 析等展开，努力降低学生接受知识的难度，不断提高学生发现、分析和解决 问题的能力。2 .坚持传统教学手段与现代教学手段相结合，教学内容安排要突出重 点和难点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的案 例、视频，使复杂的理论变得简单、直观，力求化难为易，努力提高学生的 学习兴趣。3 .注重应用启发式教学、开展课堂讨论等教学方法，引导学生积极思 考问题、分析问题，拓展学生的思维。六、考核要求、方式与成绩评定期末考试统一命题，统一评分标准，统一考试时间。考试范围不超过大纲的 内容。笔试考试，考试时间为100分钟。成绩定为百分制。实行结构评分，平时 成绩占40%,期末考试成绩占60%。评价环节评估课程目标对应毕业要求平时成绩（40分）平时作业课程目标1、2、31、2、3上机实验课程目标1、2、31、2、3期末考试（60分）选择题 简答题 综合题课程目标1、2、31、2、3平时成绩评定标准环节评定工程内容分值总分值平时 作业课程目标1、2、 3方法运用基本正确，结论不明确， 理论阐述不够完整；5-6分10分方法运用正确，结论正确，但理 由不够充分；68分方法运用正确，理由充分，结论 正确；8-10 分上机 实验课程目标1、2、 3程序框架设计基本合理，但程序 结果有问题，实验报告内容撰写 基本完整；510分30分能够根据实验步骤，完成实验内 容，实险报告内容撰写完整，逻 辑清晰，语句通顺，实脸结果基 本满足要求；10-20 分实验内容完成效果较好，程序设 计合理，实验报告内容撰写完整， 逻辑清晰，语句通顺，实验结果 正确且完善；20-30 分七、选用教材、讲义和主要参考书1 .推荐教材：数据结构（C#语言版），雷军环编著，清华大学出版社，2019。数据结构（C#语言描述）（第2版）,陈广编者，北京大学出版社，2014。2 .推荐参考书：图解数据结构-使用C#，吴灿铭、胡昭民编著，清华大学出版社，2019。数据结构（C+语言版）,秦锋、汤亚玲编著，人民邮电出版社，2014。八、大纲说明1.本课程宜按小班上课，如要合班，建议不要超过70人。