《数据结构与算法》课程教学大纲

1、数据结构与算法课程教学大纲课程英文名称：Data Structure课程编号： 133991750课程类别：专业课课程性质：选修课学 分： 3学 时：48（其中：讲课学时：32 实验学时： 上机学时:16 ）适用专业： 地理信息科学开课部门： 环境与资源学院一、课程教学目的和课程性质本课程是地理信息科学专业选修课之一。通过该课程的学习，使学生掌握数据结构领域的基础知识，特别将数据结构算法融与专业软件中。本课程系统地介绍线性表、栈、队列、字符串、数组、广义表、树、二叉树、图、查找表等几种数据结构的基本概念，操作及其典型应用的例子，通过课堂教学、课外练习和上机实习，使学生了解数据对象的特性，数据组

2、织的基本方法，并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。二、本课程与相关课程的关系先修课程：C#程序设计语言可为程序开发提供算法基础，同时包含空间分析原理部分知识。三、课程的主要内容及基本要求（一）理论学时部分第1单元 名称 数据结构和算法简介 （ 2 学时）知 识 点数据结构的基本知识重 点 数据逻辑结构、数据存储结构、数据类型的分类。难 点 算法时间复杂度和空间复杂度的分析。基本要求 1、识 记： 数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法，抽象数据类型。2、领 会： 算法与程序

3、的区别。3、简单应用：掌握并熟悉运用抽象数据类型，描述算法所用的C+语言中的一些有关问题。4、综合应用：算法时间复杂度的计算和空间复杂度的分析。第2单元 名称 解决线性表的编程问题 （ 4 学时）知 识 点 线性表的顺序存储结构、单链存储结构、双向链存储结构。重 点 线性表的存储方式。难 点 单链表的查找、插入和删除，循环链表，双向链表。基本要求1、识 记：线性表的顺序存储结构，线性表的链接存储结构，单链表的查找、插入和删除，循环链表，双向链表。2、领 会： 了解线性表的基本概念和类型定义，熟悉掌握线性表的顺序存储结构以及线性表的链接存储结构。3、简单应用：读懂程序，利用线性表存储数据。4、综

4、合应用：运用单链表的查找、插入和删除，循环链表，双向链表实现数据的存储与应用。第3单元 名称 解决堆栈的编程问题 （ 2 学时）知 识 点 栈的顺序存储和链接存储。重 点 堆栈的程序实现，循环队列判满和判空的2种判断方法。难 点 栈的线性表示与链表表示犯法。基本要求1、识 记：堆栈的特点、堆栈的定义、操作。2、领 会：使用堆栈解决编程中的问题。3、简单应用：使用栈存储整形数据。4、综合应用：应用栈的顺序存储和链接存储进行游戏求解的算法。第4单元 名称 解决队列的编程问题 （ 4 学时）知 识 点 队列的类型定义，掌握队列的顺序存储(循环队)和链接存储表示。重 点 队列的顺序存储(循环队)和链接

5、存储。难 点 队列的顺序和链接存储的程序实现。基本要求1、识 记： 队列的顺序存储、和链接存储实现。2、领 会： 队列的入队、出队操作。3、简单应用： 应用队列实现数字型数据的存储与操作。4、综合应用： 应用队列的顺序存储和链接存储，包括插入与删除功能，进行火车游戏求解的编程；用队列解决图的遍历问题。第5单元 名称 解决串的编程问题 （ 4 学时）知 识 点 串的定义，串的插入、删除和查找。重 点 串的顺序存储和链接存储。难 点 串的KMP匹配算法。基本要求1、识 记：串的定义，串的顺序存储和链接存储的表示。2、领 会：串的查找算法与匹配算法。3、简单应用：编程实现串的简单查找算法。4、综合应

6、用：给定一个字符串，编程实现串的简单匹配算法与快速匹配算法，第6单元 名称 解决数组的编程问题 （ 4 学时）知 识 点 数组的定义，数组的顺序存储和数组的插入和删除。重 点数组的存储和压缩存储。难 点三角、对称等特殊矩阵的数组表示和存储。基本要求1、识 记： 特殊矩阵的分类。2、领 会： 矩阵的转置与压缩算法。3、简单应用： 编程实现矩阵的简单转置算法。4、综合应用：编程实现矩阵的快速转置算法，实现数组的查找与匹配。第7单元 名称 解决二叉树的问题 （ 2 学时）知 识 点 二叉树树的定义、分类、遍历。重 点 二叉树的性质和存储结构以及二叉树的各种遍历方法。难 点 二叉树的三种常见遍历算法：

7、先序、中序和后序。基本要求1、识 记： 二叉树、树的度、结点的度、深度、根结点。2、领 会： 二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现。3、简单应用：根据输入数据、建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现。4、综合应用：树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法。第8单元 名称 解决树和森林的问题 （ 4 学时）知 识 点 树和森林的定义、性质和表示方法。重 点 树和森林的存储结构与遍历算法。难 点 树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与森林的转换方法。基本要求1、识

8、 记： 树、森林的遍历及与二叉树的转换。2、领 会： 树与森林的转换。3、简单应用： 森林、树以及二叉树的前中后三种遍历方式。 4、综合应用：在遍历基础上针对树的一些统计和操作(比如结点数统计、左右子树对换等等)，判断某棵树是否排序树，特别要重视非递归的算法，线索化后树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。第9单元 名称 解决图的问题 （ 2 学时）知 识 点 图的定义和术语，图的组成。重 点 图的邻接矩阵、邻接表和边集数组表示。难 点 图的遍历及最短路径算法。基本要求1、识 记：边、结点、无向图、有向图、入度、出度。2、领 会：图的邻接矩阵、邻

9、接表和边集；数组表示。 3、简单应用：图的深度和广度优先搜索历。4、综合应用：根据输入的城市间距离矩阵数据，实现最短路径算法；拓扑排序问题，关键路径问题。 第10单元 名称 实现排序算法 （ 4 学时）知 识 点 排序的概念，排序的分类及时间复杂度。 重 点 直接插入，冒泡排序和快排序，直接选择排序和堆排序，归并排序的实现。难 点 几种排序算法的时间复杂度计算及比较。基本要求1、识 记：直接插入，冒泡排序和快排序，直接选择排序和堆排序，归并排序。2、领 会：灵活选择各种排序方法对无序的数据记录进行排序。3、简单应用：给定一组数据，实现快速排序算法。4、综合应用：给定数列要求给出某种特定排序方法

10、运行一轮后的排序结果，或者给出初始数列和一轮排序结果要求选择采用的排序算法，给定时间、空间复杂度要求以及数列特征要求选择合适的排序算法等。学时分配 知识单元理论学时1数据结构和算法简介22 解决线性表的编程问题43 解决堆栈的编程问题24 解决队列编程问题45 解决串的编程问题46 解决数组的编程问题47解决二叉树的问题28 解决树的编程问题49 解决图的编程问题210执行排序算法4合计32（二）实验学时部分实验教学环节作用及目的通过上机程序的编制，达到更好地掌握理论课所学内容，锻炼逻辑思维能力之目的。实验教学环节培养学生能力标准 根据自身掌握的程度及查阅资料，在老师指定的侯选题目完成程序的补

11、充或者程序的设计，要求学生独立完成，或与同学合作完成（复杂题目）。实验项目、内容、学时分配及实验类型1、必开实验序号实验项目实验内容学时实验类型(演示、验证、综合、设计研究)组数每组学生人数1数据结构编程基础1.面向对象程序设计基础2设计研究5012线性表2.线性表的操作2设计研究5013单链表3.单链表及其基本操作2设计研究5014栈4.栈的操作2设计研究5015队列5.队列的基本操作2设计研究5016树的操作6.二叉树和二叉树排序树2设计研究5017图7.图的运算2设计研究5018排序8.排序算法，实现5种排序算法2设计研究501四、教学方法与手段采用计算机多媒体教学的方法，课堂演示利用f

12、lash演示算法的实现过程，结合范例程序讲解。1、坚持理论联系实际的教学方法，不断地吸收计算机科学先进理论知识和最新的信息技术实践动态，以重构教学流程和创新教学方式为路径，以情境创设为手段，以整合教学资源和拓展教学空间为保障，通过反复探索和实践，不断提高学生发现、分析和解决问题的能力。2、坚持传统教学手段与现代教学手段相结合，教学内容安排要突出重点和难点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的图像，使复杂的理论变得简单、直观，力求化难为易，努力提高学生的学习兴趣。3、注重应用启发式教学、开展课堂讨论等教学方法，引导学生积极思考问题、分析问题，拓展学生的思维。4、注重课后练习，大

13、力培养学生动脑、动手、独立解决问题的能力。五、考核要求、方式与成绩评定课程考核选择百分制模式，平时考查与期末考试相结合。课程考核总评成绩由四部分构成，具体包括期末考试成绩（70%）、作业成绩（20%）、课堂讨论（5%）和考勤（5%）四个部分。期末考试采取闭卷考试方式，主要考试内容为教材中重要的基本原理和基本概念，亦会少量涉及到布置的参考资料内容。考核要求：考试内容为教材中重要的基本原理和基本方法 考核形式：考试成绩评定： 按照闭卷考试方式为主，结构评定成绩，其中：期末考试成绩占70%，课后作业占25%，平时上课提问占5%。六、选用教材、讲义和主要参考书 1、教材 数据结构（C#语言版）， 雷军环、邓文达、刘震， HYPERLINK /publisher/302 t