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

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

课程英文名称：DataStructure

课程编号：133991750

课程类别：专业课

课程性质：选修课

学分：3

学时：48（其中：讲课学时：32实验学时：上机学时:16）

适用专业：地理信息科学

开课部门：环境与斐源学院

一、课程教学目的和课程性质

本课程是地理信息科学专业选修课之一。通过该课程的学习，使学生掌握数

据结构领域的基础知识，特别将数据结构算法融与专业软件中。

本课程系统地介绍线性表、栈、队列、字符串'数组、广义表、树、二叉树、

图'查找表等几种数据结构的基本概念，操作及其典型应用的例子，通过课堂教

学'课外练习和上机实习，使学生了解数据对象的特性，数据组织的基本方法，

并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培

养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。

二、本课程与相关课程的关系

先修课程：C#程序设计语言

可为程序开发提供算法基础，同时包含空间分析原理部分知识。

三、课程的主要内容及基本要求

（-）理论学时部分

第1单元名称数据结构和算法简介（2学时）

［知识点］数据结构的基本知识

［重点］数据逻辑结构、数据存储结构、数据类型的分类。

［难点］算法时间复杂度和空间复杂度的分析。

［基本要求］

1、识记：数据、数据元素、数据逻辑结构、数据存储结构'数据类

型、算法，抽象数据类型。

2、领会：算法与程序的区别。

3、简单应用：掌握并熟悉运用抽象数据类型，描述算法所用的C++语言中

的一些有关问题。

4、综合应用：算法时间复杂度的计算和空间复杂度的分析。

第2单元名称解决线性表的编程问题（4学时）

［知识点］线性表的顺序存储结构、单链存储结构、双向链存储结构。

［重点］线性表的存储方式。

［难点］单链表的查找、插入和删除，循环链表，双向链表。

［基本要求］

1、识记：线性表的顺序存储结构，线性表的链接存储结构，单链表的

查找、插入和删除，循环链表，双向链表。

2、领会：了解线性表的基本概念和类型定义，熟悉掌握线性表的顺

序存储结构以及线性表的链接存储结构。

3、简单应用：读懂程序，利用线性表存储数据。

4、综合应用：运用单链表的查找、插入和删除，循环链表，双向链表实现

数据的存储与应用。

第3单元名称解决堆栈的编程问题（2学时）

［知识点］栈的顺序存储和链接存储。

［重点］堆栈的程序实现，循环队列判满和判空的2种判断方法。

［难点］栈的线性表示与链表表示犯法。

「基本要求］

1、识记：堆栈的特点'堆栈的定义、操作。

2、领会：使用堆栈解决编程中的问题。

3、简单应用：使用栈存储整形数据。

4、综合应用：应用栈的顺序存储和链接存储进行游戏求解的算法。

第4单元名称解决队列的编程问题（4学时）

［知识点］队列的类型定义，掌握队列的顺序存储（循环队）和链接存储表示。

［重点］队列的顺序存储（循环队）和链接存储。

［难点］队列的顺序和链接存储的程序实现。

［基本要求］

1、识记：队列的顺序存储、和链接存储实现。

2、领会：队列的入队、出队操作。

3、简单应用：应用队列实现数字型数据的存储与操作。

4、综合应用：应用队列的顺序存储和链接存储，包括插入与删除功能，

进行火车游戏求解的编程；用队列解决图的遍历问题。

第5单元名称解决串的编程问题（4学时）

［知识点］串的定义，串的插入、删除和查找。

［重点］串的顺序存储和链接存储。

［难点］串的KMP匹配算法。

［基本要求］

1、识记：串的定义，串的顺序存储和链接存储的表示。

2、领会：串的查找算法与匹配算法。

3、简单应用：编程实现串的简单查找算法。

4、综合应用：给定一个字符串，编程实现串的简单匹配算法与快速匹配算

法，

第6单元名称解决数组的编程问题（4学时）

［知识点］数组的定义，数组的顺序存储和数组的插入和删除。

［重点］数组的存储和压缩存储。

［难点］三角、对称等特殊矩阵的数组表示和存储。

［基本要求］

1、识记：特殊矩阵的分类。

2、领会：矩阵的转置与压缩算法。

3、简单应用：编程实现矩阵的简单转置算法。

4、综合应用：编程实现矩阵的快速转置算法，实现数组的查找与匹配。

第7单元名称解决二叉树的问题（2学时）

［知识点］二叉树树的定义、分类、遍历。

［重点］二叉树的性质和存储结构以及二叉树的各种遍历方法。

［难点］二叉树的三种常见遍历算法：先序、中序和后序。

［基本要求］

1、识记：二叉树、树的度、结点的度、深度、根结点。

2、领会：二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、

求二叉树深度等的操作方法及实现。

3、简单应用：根据输入数据、建立二叉树、输出二叉树'求二叉树深度等

的操作方法及实现。

4、综合应用：树的存储结构，进行先根遍历、后根遍历和按层遍历的方法

及实现，进行树与二叉树的转换方法。

第8单元名称解决树和森林的问题（4学时）

［知识点］树和森林的定义、性质和表示方法。

［重点］树和森林的存储结构与遍历算法。

［难点］树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现,

进行树与森林的转换方法。

［基本要求］

1、识记：树、森林的遍历及与二叉树的转换。

2、领会：树与森林的转换。

3、简单应用：森林、树以及二叉树的前中后三种遍历方式。

4、综合应用：在遍历基础上针对树的一些统计和操作（比如结点数统计、

左右子树对换等等），判断某棵树是否排序树，特别要重视非递归的算法，线索

化后树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出

Huffman编码等等。

第9单元名称解决图的问题（2学时）

［知识点］图的定义和术语，图的组成。

［重点］图的邻接矩阵、邻接表和边集数组表示。

［难点］图的遍历及最短路径算法。

［基本要求］

1、识记：边'结点、无向图'有向图'入度、出度。

2、领会：图的邻接矩阵、邻接表和边集；数组表示。

3、简单应用：图的深度和广度优先搜索历。

4、综合应用：根据输入的城市间距离矩阵数据，实现最短路径算法；拓扑

排序问题，关键路径问题。

第10单元名称实现排序算法（4学时）

［知识点］排序的概念，排序的分类及时间复杂度。

［重点］直接插入，冒泡排序和快排序，直接选择排序和堆排序，归并排序

的实现。

［难点］几种排序算法的时间复杂度计算及比较。

［基本要求］

1、识记：直接插入，冒泡排序和快排序，直接选择排序和堆排序，归

并排序。

2、领会：灵活选择各种排序方法对无序的数据记录进行排序。

3、简单应用：给定一组数据，实现快速排序算法。

4、综合应用：给定数列要求给出某种特定排序方法运行一轮后的排序结果,

或者给出初始数列和一轮排序结果要求选择采用的排序算法，给定时间、空间复

杂度要求以及数列特征要求选择合适的排序算法等。

［学时分配］

知识单元理论学时

1数据结构和算法简介2

2解决线性表的编程问题4

3解决堆栈的编程问题2

4解决队列编程问题4

5解决串的编程问题4

6解决数组的编程问题4

7解决二叉树的问题2

8解决树的编程问题4

9解决图的编程问题2

10执行排序算法4

合计32

（-）实验学时部分

［实验教学环节作用及目的］

通过上机程序的编制，达到更好地掌握理论课所学内容，锻炼逻辑思维能力

之目的。

［实验教学环节培养学生能力标准］

根据自身掌握的程度及查阅资料,在老师指定的侯选题目完成程序的补充或

者程序的设计，，要求学生独立完成，或与同学合作完成（复杂题目）。

［实验项目、内容、学时分配及实验类型］

1、必开实验

序学实验类型组每组学

实验项目实验内容

号时（演示、验证、综合、设计研究）数生人数

数据结构1.面向对象程

12设计研究501

编程基础序设计基础

2.线性表的操

2线性表2设计研究501

作

3.单链表及其

3单链表2设计研究501

基本操作

4栈4.栈的操作2设计研究501

5.队列的基本

5队列2设计研究501

操作

6.二叉树和二

6树的操作2设计研究501

叉树排序树

7图7.图的运算2设计研究501

8.排序算法，

8排序实现5种排序2设计研究501

算法

四、教学方法与手段

采用计算机多媒体教学的方法，课堂演示利用flash演示算法的实现过程，

结合范例程序讲解。

1、坚持理论联系实际的教学方法，不断地吸收计算机科学先进理论知识和

最新的信息技术实践动态，以重构教学流程和创新教学方式为路径，以情境创设

为手段，以整合教学资源和拓展教学空间为保障，通过反复探索和实践，不断提

高学生发现'分析和解决问题的能力。

2、坚持传统教学手段与现代教学手段相结合，教学内容安排要突出重点和

难点，积极应用多媒体教学技术，尽可能把抽象的理论转化为具体的图像，使复

杂的理论变得简单、直观，力求化难为易，努力提高学生的学习兴趣。

3、注重应用启发式教学'开展课堂讨论等教学方法，引导学生积极思考问

题'分析问题，拓展学生的思维。

4、注重课后练习，大力培养学生动脑、动手、独立解决问题的能力。

五、考核要求'方式与成绩评定

课程考核选择百分制模式，平时考查与期末考试相结合。课程考核总评成

绩由四部分构成，具体包括期