安徽师范大学数据结构本科教学大纲

安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页1
《数据结构》教学大纲
课程性质：专业基础课程 先修课程：离散数学，C 语言
总学时：41 学分：2
理论学时：32 实验学时：9
开课学院：皖江学院 适用专业：电子信息工程
大纲执笔人： 教学院长审定：
教研室主任审核：
一、说明
1、课程性质、地位和任务
《数据结构》在计算机科学中是一门综合性的专业主干课，专业基础课，主要介绍如何
合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过
本课程的学习，使学生深入透彻地理解数据结构的逻辑结构和物理结构的基本概念以及有关
算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为电子信息工程专业学生
今后学习操作系统、编译原理等其它相关专业课程奠定基础。
2、课程教学的基本要求
（1）了解数据结构及其分类、数据结构与算法的密切关系。
（2）熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。
（3）掌握设计算法的步骤和算法分析方法。
（4）掌握线性表、栈与队列的基本算法及应用。
（5）掌握二维数组、特殊矩阵、稀疏矩阵的表示、实现算法及应用。
（6）熟练掌握树和二叉树的各种性质和算法，二叉排序树、哈夫曼树的应用。
（7）熟练掌握图的表示及其实现，图的遍历算法，拓扑排序、求取关键路径和单源最
短路径的算法。
（8）熟练掌握常用的查找、排序算法，学会分析数据表示对各种查找、排序效率的影
响。
3、本课程的重点与难点
重点：本课程的重点内容是分析各种类型数据结构的特点，数据的表示及实现的算法。
如何合理地组织数据、有效地存储和处理数据，正确地设计编写算法以及对算法的分析和评
价，如何应用所学知识解决实际问题。教学过程中主要采用讲授方式，配合多媒体，形象的
比喻，引导、启发学生掌握教学内容。
安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页2
难点：本课程的难点包括线性链表的基本运算、带行（列）辅助向量的稀疏矩阵的应用、
哈夫曼树及其应用、单源最短路径、拓扑排序、哈希表、堆排序以及如何将伪代码编写的算
法映射为某一高级语言的描述。
二、课堂教学时数及课后作业题型分配
章 目 教 学 内 容
教 学
时 数
教学方式
或 手 段
课 后 作 业
思 考 题 练 习 题
一 绪论 2 讲授（多媒体） √
二 线性表及其顺序存储结构 4 讲授（多媒体） √ √
三 线性链表 3 讲授（多媒体） √ √
四 数组 5 讲授（多媒体） √ √
五 树与二叉树 5 讲授（多媒体） √ √
六 图 5 讲授（多媒体） √ √
七 查找技术 3 讲授（多媒体） √ √
八 Hash 表技术 2 讲授（多媒体） √ √
九 排序技术 3 讲授（多媒体） √ √
合 计 32
三、正文
第一章 绪论
【教学目的】
通过本章教学，使学生掌握数据和数据结构的基本术语，理解算法描述与算法的评价方
法。
【重点难点】
数据结构的基本概念和术语，算法描述与算法分析。
第一节 数据结构的基本概念
一、数据结构的定义
二、数据结构的图形表示
三、线性数据结构与非线性数据结构
第二节 算法方面的考虑
一、算法的定义
二、算法的时间复杂度和算法的空间复杂度
三、算法描述语言
第二章 线性表及其顺序存储结构
【教学目的】
安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页3
通过本章教学，使学生掌握线性表、栈和队列的逻辑结构和顺序存储结构的描述方法，
熟练掌握线性表、栈和队列在顺序存储结构下的主要运算，掌握栈与队列的主要应用，了解
字符串匹配的方法。
【重点难点】
线性表、栈和队列的逻辑结构和顺序存储结构的描述，线性表、栈和队列的顺序存储结
构上的插入删除算法。
第一节 线性表的基本概念
一、线性表的定义
二、线性表的顺序存储结构
三、线性表在顺序存储下的插入运算
四、线性表在顺序存储下的删除运算
第二节 栈及其应用
一、栈的定义
二、栈的顺序存储及其运算
三、表达式的计算
四、递归
第三节 队列及其应用
一、队列的定义
二、循环队列及其运算
三、队列的应用
第四节 字符串
一、字符串的基本概念
二、字符串匹配
第三章 线性链表
【教学目的】
通过本章教学，使学生掌握线性表的链式存储结构及其运算，掌握线性链表在多项式运
算中的应用，深刻理解指针与指针所指结点的关系，了解头指针、头结点和开始结点之间的
区别。。
【重点难点】
线性表、栈和队列链式存储结构的描述，线性表、栈和队列的链式存储结构上的插入删
除算法，多项式的表示与运算。
第一节 线性链表的基本概念
一、线性表顺序存储的问题
二、线性链表
三、带链的栈
安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页4
四、带链的队列
第二节 线性链表的基本运算
一、在线性链表中查找指定元素
二、线性链表的插入
三、线性链表的删除
第三节 循环链表
第四节 多项式的表示与运算
第四章 数组
【教学目的】
通过本章教学，使学生掌握二维数组的顺序存储结构，规则矩阵（对称矩阵、上（下）
三角矩阵、三对角矩阵）的表示与实现，掌握稀疏矩阵的带行（列）辅助向量的三元组表示、
实现及其应用，了解十字链表的结构。
【重点难点】
二维数组的存储结构，存储地址的计算方式，规则矩阵的压缩存储，稀疏矩阵的三元组
表示。
第一节 数组的顺序存储结构
一、按行优先存储
二、按列优先存储
第二节 规则矩阵的压缩
一、对称矩阵的压缩
二、三角矩阵的压缩
三、三对角矩阵的压缩
第三节 稀疏矩阵的表示
一、稀疏矩阵的三元组表示
二、十字链表
第五章 树与二叉树
【教学目的】
通过本章教学，使学生熟悉树、二叉树的基本概念，掌握二叉树的性质、二叉树的存储
结构及其遍历，掌握最优二叉树、哈夫曼编码的方法，了解树和森林的相互转换、穿线二叉
树的概念、表达式线性化的过程等问题。
【重点难点】
二叉树的性质，二叉树的存储结构，最优二叉树，哈夫曼编码，二叉树的生成算法，二
叉树的遍历及其上的一些应用。
第一节 树
安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页5
一、树的定义
二、基本术语
第二节 二叉树及其基本性质
一、二叉树的定义
二、二叉树的基本性质
三、满二叉树与完全二叉树
第三节 二叉树的存储结构
一、二叉链表
二、二叉链表的生成
三、树和森林及其相互之间的转换
第四节 二叉树的遍历
一、二叉树的先序遍历
二、二叉树的中序遍历
三、二叉树的后序遍历
第五节 表达式的线性化
一、有序树的二叉树表示
二、表达式的线性化
第六节 最优二叉树及其应用
一、么是最优二叉树
二、最优二叉树的构造
三、哈夫曼编码
第六章 图
【教学目的】
通过本章教学，使学生理解图的基本概念、图的存储方式、图的遍历方法，掌握图的应
用。
【重点难点】
图的存储方式、图的遍历方法，单源最短路径，拓扑排序，关键路径。
第一节 图的基本概念
一、图的定义
二、图的基本术语
第二节 图的存储结构
一、关联矩阵
二、求值矩阵
三、邻接表
安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页6
四、邻接多重表
第三节 图的遍历
一、纵向优先搜索法
二、横向优先搜索法
第四节 图的应用
一、单源最短路径
二、拓扑排序
三、关键路径
第七章 查找技术
【教学目的】
通过本章教学，使学生理解查找的概念，掌握常用的查找方法，熟练掌握二叉排序树的
构造方法及平均查找长度的计算。
【重点难点】
顺序查找，对分查找，分块查找，二叉排序树查找以及多层索引树查找，二叉排序树的
构造。
第一节 顺序查找
一、查找的基本概念
二、顺序查找算法
第二节 有序表的对分查找
一、对分查找的概念
二、对分查找的算法
第三节 分块查找
一、分块查找的概念
二、分块查找的算法
第四节 二叉排序树查找
一、二叉排序树及其构造
二、二叉排序树查找算法
第五节 多层索引树查找
一、B
-
树 二、B
+
树
第八章 Hash 表技术
【教学目的】
通过本章教学，使学生理解 Hash 表的基本概念，掌握哈希函数的构造方法，掌握 Hash
表技术的应用。
【重点难点】
安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页7
哈希表技术，散列函数的构造方法及冲突的处理。
第一节 Hash 表的基本概念
一、直接查找技术
二、Hash 表
三、Hash 表的构造
第二节 几种常用的 Hash 表
一、线性 Hash 表
二、随机 Hash 表
三、溢出 Hash 表
四、拉链 Hash 表
五、指标 Hash 表
第九章 排序技术
【教学目的】
通过本章教学，使学生熟练掌握五种基本内部排序方法的基本思想，掌握排序过程和实
现算法，能熟练写出各趟结果，掌握排序算法的时间复杂度的分析。
【重点难点】
冒泡排序，快速排序，简单插入排序，希尔排序，简单选择排序，堆排序，拓扑分类。
第一节 互换类排序
一、冒泡排序
二、快速排序
第二节 插入类排序
一、简单插入排序
二、希尔排序
第三 选择类排序
一、简单选择排序
二、堆排序
【课程考试】
本课程采用“闭卷”方式进行考试，考试成绩以 60%的比例记入课程总评成绩，课外作
业和平时测验占 20％，实验占 20％。重点考查学生对各种数据结构的基本概念、基本原理
的理解，测试学生对各种数据结构的表示和算法设计水平，对查找和排序的基本概念及其实
现算法的掌握情况，对知识的应用能力。考试题型包括填空题、选择题、简答题和综合应用
题等类型。
四、使用教材与教学参考书目
【使用教材】
安徽师范大学皖江学院电子信息系 数据结构教学大纲
第 页8
徐士良：《实用数据结构》，清华大学出版社，2000 年 1 月
【教学参考书目】
1、严蔚敏，吴伟民，《数据结构》（C 语言版），清华大学出版社，1997 年 12 月
2、徐孝凯等，《数据结构》（C 语言描述），清华大学出版社，2004 年 9 月
3、[美]Yedidyah Langsam 等著，李华，瀟东译，《数据结构 C 和 C++语言描述》（第 2
版），清华大学出版社，2004 年 3 月