附件9: 《数据结构》教学大纲 课程编号:1309114000 课程名称(中文):数据结构 课程名称(英文): Data structure 开课单位:信息技术学院,管理科学与工程学科 学分:4 总学时:72 理论学时:54 实验学时:18 先开课程:《程序设计基础》 授课对象:信息管理与信息系统本科专业 考核方式:考试 、课程的教学目标与任务 本课程介绍如何组织各种数据在计算机中的存储和处理技术。重点学习内容包括:顺序 表、链表、栈和队列、数组、树与森林、图、查找、排序等。通过本课程的学习,使学生深 透地理解数据结构的基本概念以及有关算法,培养良好的程序设计技能,锻炼通过编程解决 实际问题的能力。为后续计算机专业课程的学习打下坚实的基础,为从事计算机技术的研究 和开发打下理论和实践的基础 、课程内容及基本要求 ()绪论(总学时4学时,理论4学时) 主要讲述数据结构的基本术语、基本数据结构类型的概念、以及算法时间复杂度、空间 复杂度的估算方法 1.基本要求 (1)掌握数据结构中各种基本术语的含义、区别与联系 (2)掌握基本的数据结构类型和它们的主要特点,并能举例 (3)了解估算算法时间复杂度、空间复杂度的方法。 2.重点、难点 重点:数据结构的定义及这门课的知识体系、四种基本的数据结构类型 难点:四种基本的数据结构类型和时间复杂度的分析 3.说明:本部分是数据结构课程的入门,讲授数据结构课程中进行问题求解的基本思 路,后面章节将以此思路讲解不同的数据结构类型
附件 9： 《数据结构》教学大纲 课程编号：13091140009 课程名称（中文）：数据结构 课程名称（英文）： Data Structure 开课单位：信息技术学院，管理科学与工程学科 学分： 4 总学时： 72 理论学时： 54 实验学时： 18 先开课程：《程序设计基础》 授课对象：信息管理与信息系统本科专业 考核方式：考试 一、课程的教学目标与任务 本课程介绍如何组织各种数据在计算机中的存储和处理技术。重点学习内容包括：顺序 表、链表、栈和队列、数组、树与森林、图、查找、排序等。通过本课程的学习，使学生深 透地理解数据结构的基本概念以及有关算法，培养良好的程序设计技能，锻炼通过编程解决 实际问题的能力。为后续计算机专业课程的学习打下坚实的基础，为从事计算机技术的研究 和开发打下理论和实践的基础。 二、课程内容及基本要求 (一) 绪论(总学时 4 学时，理论 4 学时) 主要讲述数据结构的基本术语、基本数据结构类型的概念、以及算法时间复杂度、空间 复杂度的估算方法。 1.基本要求 （1）掌握数据结构中各种基本术语的含义、区别与联系； （2）掌握基本的数据结构类型和它们的主要特点，并能举例； （3）了解估算算法时间复杂度、空间复杂度的方法。 2.重点、难点 重点：数据结构的定义及这门课的知识体系、四种基本的数据结构类型 难点：四种基本的数据结构类型和时间复杂度的分析 3.说明： 本部分是数据结构课程的入门，讲授数据结构课程中进行问题求解的基本思 路，后面章节将以此思路讲解不同的数据结构类型
(二)线性表(总学时12学时,理论8学时,实验4学时) 主要讲述线性数据结构的存储和处理以及应用。 1.基本要求 (1)掌握线性表的逻辑结构特性 (2)熟练掌握线性表的两种不同存储结构(顺序存储结构和链式存储结构)的描述方 法和各种基本操作的算法; (3)掌握单链表和循环链表。 重点、难点 重点:线性数据结构的存储和处理 难点:单链表的结点结构定义、循环链表的几种基本操作 3.说明 三)栈和队列(总学时12学时,理论8学时,实验4学时) 主要讲述栈和队列的存储和处理以及应用。 1.基本要求 (1)了解栈和队列的结构特点及其两种存储结构 (2)掌握栈和队列在两种存储结构下实现基本操作的算法。 (3)熟练掌握栈的链式存储结构和循环队列。 2.重点、难点 重点:栈和队列在两种存储结构下实现基本操作的算法 难点:栈的链式存储结构和循环队列 3.说明 (四)串(总学时4学时,理论4学时) 主要讲述串的存储和处理以及应用。 1.基本要求 (1)了解串的概念及其基本操作; (2)了解串的两种存储结构并掌握实现串的各种基本操作; (3)理解串的模式匹配算法 2.重点、难点 重点:串的各种基本操作 难点:串的模式匹配算法 3.说明: 五)数组(总学时4学时,理论4学时) 主要讲述数组的存储和处理以及应用。 1.基本要求 (1)了解数组的定义及其基本操作。 (2)掌握数组的存储结构。 (3)掌握特殊矩阵的压缩存储 (4)了解稀疏矩阵的压缩存储。 2.重点、难点 重点:数组的存储结构
（二）线性表(总学时 12 学时，理论 8 学时，实验 4 学时) 主要讲述线性数据结构的存储和处理以及应用。 1. 基本要求 （1）掌握线性表的逻辑结构特性； （2）熟练掌握线性表的两种不同存储结构（顺序存储结构和链式存储结构）的描述方 法和各种基本操作的算法； （3）掌握单链表和循环链表。 2.重点、难点 重点：线性数据结构的存储和处理 难点：单链表的结点结构定义、循环链表的几种基本操作 3.说明： （三）栈和队列(总学时 12 学时，理论 8 学时，实验 4 学时) 主要讲述栈和队列的存储和处理以及应用。 1.基本要求 （1）了解栈和队列的结构特点及其两种存储结构。 （2）掌握栈和队列在两种存储结构下实现基本操作的算法。 （3）熟练掌握栈的链式存储结构和循环队列。 2.重点、难点 重点：栈和队列在两种存储结构下实现基本操作的算法 难点：栈的链式存储结构和循环队列 3.说明： （四）串(总学时 4 学时，理论 4 学时) 主要讲述串的存储和处理以及应用。 1.基本要求 （1）了解串的概念及其基本操作； （2）了解串的两种存储结构并掌握实现串的各种基本操作； （3）理解串的模式匹配算法。 2.重点、难点 重点：串的各种基本操作 难点：串的模式匹配算法 3.说明： （五）数组(总学时 4 学时，理论 4 学时) 主要讲述数组的存储和处理以及应用。 1.基本要求 （1）了解数组的定义及其基本操作。 （2）掌握数组的存储结构。 （3）掌握特殊矩阵的压缩存储。 （4）了解稀疏矩阵的压缩存储。 2.重点、难点 重点：数组的存储结构
难点:稀疏矩阵的压缩存储 3.说明: (六)树(总学时12学时,理论8学时,实验4学时) 主要讲述二叉树、树、森林的存储和处理以及应用。 1.基本要求 (1)掌握树的定义、各个基本术语以及树的各种存储结构。 (2)掌握二叉树的基本概念、性质、各种存储结构的特点及其基本操作的实现。 (3)熟练掌握二叉树各种遍历算法及其应用。 (4)了解线索二叉树的实现方法 5)掌握如何建立哈夫曼树,了解哈夫曼树在编码、判定问题中的应用 (6)了解树、森林与二叉树的转换方法。 (7)了解树和森林的遍历。 2.重点、难点 重点:二叉树的存储、二叉树的遍历算法 难点:树和森林的遍历 3.说明 (七)图(总学时10学时,理论8学时,实验2学时) 主要讲述图的存储和处理以及应用 1.基本要求 (1)了解图的基本术语。 (2)掌握图的各种存储结构及使用原则 (3)掌握图的深度优先搜索和广度优先搜索算法。 (4)掌握图生成最小生成树的方法,求最短路径的方法。 (5)拓扑排序的应用实例和排序过程中栈的变化 (6)了解网络中的关键路径及其求解。 (7)了解图的若干应用算法。 2.重点、难点 重点:图的存储结构、搜索算法、最短路径 难点:最小生成树的生成方法、最短路径的求解方法 3.说明 (八)查找(总学时6学时,理论4学时,实验2学时) 主要讲述各种査找方法和算法实现。 1.基本要求 (1)了解查找的基本概念。 (2)熟练掌握顺序査找、二分查找和分块查找的特点及算法。 (3)掌握二叉排序树的构造,査找及删除算法。 (4)了解哈希表的构造方法和处理冲突的基本方法 (5)掌握查找成功时平均查找长度的计算方法 2.重点、难点 重点:顺序查査找、二分查找的特点及算法
难点：稀疏矩阵的压缩存储 3.说明： （六）树(总学时 12 学时，理论 8 学时，实验 4 学时) 主要讲述二叉树、树、森林的存储和处理以及应用。 1.基本要求 （1）掌握树的定义、各个基本术语以及树的各种存储结构。 （2）掌握二叉树的基本概念、性质、各种存储结构的特点及其基本操作的实现。 （3）熟练掌握二叉树各种遍历算法及其应用。 （4）了解线索二叉树的实现方法 （5）掌握如何建立哈夫曼树，了解哈夫曼树在编码、判定问题中的应用。 （6）了解树、森林与二叉树的转换方法。 （7）了解树和森林的遍历。 2.重点、难点 重点：二叉树的存储、二叉树的遍历算法 难点：树和森林的遍历 3.说明： （七） 图(总学时 10 学时，理论 8 学时，实验 2 学时) 主要讲述图的存储和处理以及应用。 1.基本要求 （1）了解图的基本术语。 （2）掌握图的各种存储结构及使用原则 （3）掌握图的深度优先搜索和广度优先搜索算法。 （4）掌握图生成最小生成树的方法，求最短路径的方法。 （5）拓扑排序的应用实例和排序过程中栈的变化 （6）了解网络中的关键路径及其求解。 （7）了解图的若干应用算法。 2.重点、难点 重点：图的存储结构、搜索算法、最短路径 难点：最小生成树的生成方法、最短路径的求解方法 3.说明： （八）查找(总学时 6 学时，理论 4 学时，实验 2 学时) 主要讲述各种查找方法和算法实现。 1.基本要求 （1）了解查找的基本概念。 （2）熟练掌握顺序查找、二分查找和分块查找的特点及算法。 （3）掌握二叉排序树的构造，查找及删除算法。 （4）了解哈希表的构造方法和处理冲突的基本方法。 （5）掌握查找成功时平均查找长度的计算方法。 2.重点、难点 重点：顺序查找、二分查找的特点及算法
难点:二叉排序树的构造、查找及删除算法 3.说明: (九)排序(总学时8学时,理论6学时,实验2学时) 主要讲述各种排序方法和算法实现。 1.基本要求 (1)了解排序的基本概念 (2)熟练掌握各种内部排序方法的算法。 (3)熟悉各种内部排序方法的特点、性能,能根据不同的实际情况比较、分析、选用 不同的内部排序方法 (4)了解外部排序的概念和特点 2.重点、难点 重点:各种内部排序方法的算法 难点:排序方法的性能分析 3.说明 教学安排及方式 总学时:72学时,其中理论教学时数54学时,实验教学时数为18学时 学环节 教学时数 讲授 实验上机小计 备注 (践 课程内容 一)数据结构概念、术语 一)基本数据结构类型简介、举例 (二)线性表的类型定义 22222 (二)线性表的顺序表示和算法实现2 (二)单链表的表示和算法实现 (二)循环链表和双向链表的表示和2 算法实现 22244224 (三)栈的定义 (三)栈的表示和实现 (三)队列的定义 (三)队列的表示和实现 (四)串的定义 (四)串的表示和算法实现2 五)数组的顺序表示和算法实现2 (五)数组的压缩存储 (六)二叉树的定义和存储结构 (六)遍历二叉树 (六)树和森林的存储结构 哈夫曼树及其应用 (七)图的定义和存储结构 22224224422 (七)图的遍历 (七)有向无环图及其应用
难点：二叉排序树的构造、查找及删除算法 3.说明： （九）排序 ( 总学时 8 学时，理论 6 学时，实验 2 学时) 主要讲述各种排序方法和算法实现。 1.基本要求 （1）了解排序的基本概念。 （2）熟练掌握各种内部排序方法的算法。 （3）熟悉各种内部排序方法的特点、性能，能根据不同的实际情况比较、分析、选用 不同的内部排序方法。 （4）了解外部排序的概念和特点。 2.重点、难点 重点：各种内部排序方法的算法 难点：排序方法的性能分析 3.说明： 三、教学安排及方式 总学时：72 学时，其中理论教学时数 54 学时，实验教学时数为 18 学时。 教学环节 教学时数 课程内容 讲授 实 验 (实践) 上机 小计 备注 （一）数据结构概念、术语 2 2 （一）基本数据结构类型简介、举例 2 2 （二）线性表的类型定义 2 2 （二）线性表的顺序表示和算法实现 2 2 4 （二）单链表的表示和算法实现 2 2 4 （二）循环链表和双向链表的表示和 算法实现 2 2 （三）栈的定义 2 2 （三）栈的表示和实现 2 2 4 （三）队列的定义 2 2 （三）队列的表示和实现 2 2 4 （四）串的定义 2 2 （四）串的表示和算法实现 2 2 （五）数组的顺序表示和算法实现 2 2 （五）数组的压缩存储 2 2 （六）二叉树的定义和存储结构 2 2 4 （六）遍历二叉树 2 2 （六）树和森林的存储结构 2 2 （六）哈夫曼树及其应用 2 2 4 （七）图的定义和存储结构 2 2 4 （七）图的遍历 2 2 （七）有向无环图及其应用 2 2
(七)最短路径 (八)顺序查找、二分查找 2 (八)动态查找表、哈希表 (九)插入排序、快速排序 (九)选择排序、归并排序 242422 (九)基数排序、排序方法的比较2 四、考核方式 1.考核方式 笔试(闭卷)。 成绩评定 各教学环节占总分的比例:平时测验及作业:20%,实验:10%,考勤:10%,期末 考试:60%。 五、推荐教材与参考资料 1.推荐教材: 李春葆主编《数据结构教程(C#语言描述)》,(北京):清华大学出版社,(2013年 严蔚敏等主编《数据结构(C语言版)》(第2版),(北京):清华大学出版社,(200 雷军环等主编《数据结构(C#语言版)》(第1版),(北京):清华大学出版社,(2009 年2月) 2.参考资料 (1)《计算机算法基础(第三版)》,余祥宣等主编,华中科技大学出版社 (2)《算法导论》, Thomas I. Cormen等著,殷建平等翻译,机械工业出版社。 执笔人:吕雅丽 审核人 014年4月28日
（七）最短路径 2 2 （八）顺序查找、二分查找 2 2 4 （八）动态查找表、哈希表 2 2 （九）插入排序、快速排序 2 2 4 （九）选择排序、归并排序 2 2 （九）基数排序、排序方法的比较 2 2 四、考核方式 1.考核方式： 笔试（闭卷）。 2.成绩评定： 各教学环节占总分的比例:平时测验及作业：20%，实验：10%，考勤：10%，期末 考试：60%。 五、推荐教材与参考资料 1.推荐教材： 李春葆主编《数据结构教程（C#语言描述）》，（北京）：清华大学出版社，（2013 年 2 月） 严蔚敏等主编《数据结构（C 语言版）》（第 2 版），（北京）：清华大学出版社，（2007 年 3 月） 雷军环等主编《数据结构（C#语言版）》（第 1 版），（北京）：清华大学出版社，（2009 年 2 月） 2.参考资料： （1）《计算机算法基础（第三版）》，余祥宣等主编，华中科技大学出版社； （2）《算法导论》，Thomas H.Cormen 等著，殷建平等翻译，机械工业出版社。 执笔人：吕雅丽 审核人： 2014 年 4 月 28 日