安徽师范大学自动化本科专业《数据结构与算法》课程大纲本科教学大纲

理论类课程大纲
课程名称:数据结构
一、课程概况
所属专业: 自动化 开课单位： 物理与电子信息学院
课程类型: 专业基础课程 课程代码: 0845140
开课学期: 2 学分： 2
学时： 34 核心课程: 是
拟使用教材：
邓文华，《数据结构》，电子工业出版社，2011 年
国内(外)现有教材：
邓文华，《数据结构》，电子工业出版社，2011 年
学习参考资料
[1] 严蔚敏，吴伟民 著，《数据结构(C 语言版) 》，清华大学出版社，2012
年
[2] William Ford，William Topp《数据结构 C++语言描述》，清华大学出版
社，1997 年
[3] Thomas H.Cormen 等著，殷建平 等译《算法导论》，机械工业出版社，
2012 年
二、课程描述（300 字以内）
数据结构与算法是电子信息、自动化等专业的专业基础课，也是程序设计方
面的一门综合性基础课程。学习本课程也是进行复杂程序设计的训练过程，因此
要求学生能用算法语言书写结构清晰正确的算法。并通过上机实验，使学生受到
严格的基本技术训练，以便为今后的工作实践打好坚实基础。课程的主要内容包
括栈、队列、二叉树、图以及相关的算法。
三、课程目标
通过该课程的学习，学生将基本掌握数据结构和算法的设计分析技术，
提高程序设计的质量；根据所求解问题的性质选择合理的数据结构并对时间空间
复杂性进行必要的控制。初步具备利用所学数据结构知识解决工程实际问题的能
力。
四、教学要求
授课教师将按照学校本科教学工作有关要求做好课程教学各项工作，严格按
照课表规定的时间、地点上课，不迟到、不早退，将根据本大纲要求，认真备课
完成教案与讲稿编写等各项课前准备工作；授课过程力求内容充实、概念准确、
思路清晰、详略得当、逻辑性强、重难点突出，力戒平铺直叙、照本宣科，同时
重视对学生的学习方法指导和课堂教学效果信息的反馈，实现教与学的双向互
动；同时将结合课程目标要求，做好考核内容设计，并严格按照本大纲要求做好
出勤率统计、作业评价等各项工作。
学习是大学生自己的责任和义务，学生应根据课程大纲要求制定本门课程学
习计划，加强学业管理，严格自我要求，提升自主学习能力，主动适应课程学习
要求。参与课堂教学活动不迟到、不早退，无正当理由不请假，上课认真听讲，
不做任何与课堂教学无关事宜，不使用手机，积极与授课教师进行教学互动，同
时利用课余时间做好预习、复习、课外书籍阅读等工作，主动与同学开展合作学
习，认真完成任课教师布置的课程作业。
五、考核方式及要求
为实现课程教学目标，本门课程考核方式及要求为：出勤率及课程作业占
10%，点到不少于 3 次，其中缺席 1 次，按无成绩计算；随堂测验 1 次，测验成
绩按 10%折算后计入总成绩；实验成绩按 20%折算后计入总成绩；期末考试为
卷面考试，占总成绩的 60%。
六、课程内容
第一章：绪论
（授课时间：第二学期第 1 周）
教学目标：掌握数据结构的基本概念、算法时间复杂度以空间复杂度的分析方法。
教学重点：数据结构的定义；逻辑结构和存储结构的概念；算法的概念。
教学难点：算法复杂度的表示方法；算法时间复杂度及空间复杂度分析。
学 时：课堂教学 2 学时，课外自主学习时间不少于 2 学时
教学方法：讲授法、演示法
主要内容：(1)从问题到程序
(2)有关概念和术语
(3)算法及算法分析
(4)关于数据结构的学习
学习方法：小组讨论、实验操作
课后作业：
1. 什么是算法？一个好的算法要符合哪些要求？
2. 数据结构和算法的关系是什么？
第二章：线性表
（授课时间：第二学期第 2,3,4 周）
教学目标：通过本章教学，使学生理解顺序表的定义、特点及主要操作，掌握基
本操作的实现算法。
教学重点：单链表的成员函数及其实现算法。
教学难点：单链表及双链表的插入及删除操作的指针移动方法。
学 时：课堂教学 6 学时，课外自主学习时间不少于 6 学时
教学方法：讲授法、演示法
主要内容：
(1) 线性表的逻辑结构
一、线性表的定义 二、线性表的基本操作
(2) 线性表顺序存储及其操作的实现
一、顺序表 二、顺序表基本操作的实现 三、顺序表的其他操作
举例
(3) 线性表的链式存储及其操作的实现
一、单链表 二、单链表基本操作的实现 三、循环链表 四、双
向链表
(4) 典型例题
学习方法：小组讨论、实验操作
课后作业：
1.编写一算法输出已知顺序表 A 中元素的最大值和次大值。用非形
式算法描述，并编写 c 语言程序。试分析所编程序的时间和空间复杂度。
第三章：栈和队列
（授课时间：第二学期第 5,6,7 周）
教学目标：通过本章教学，使学生了解栈和队列的存储结构、基本运算和实现方
法，初步掌握栈和队列的应用。
教学重点：栈与队列的概念及实现。
教学难点：栈与递归；栈与队列的实现及应用。
学 时：课堂教学 6 学时，课外自主学习时间不少于 6 学时
教学方法：讲授法、演示法
主要内容：
(1) 栈
一、栈的定义及其基本运算 二、栈的存储结构和基本运算实现
三、栈的应用举例 四、栈与递归的实现
(2) 队列
一、队列的定义及其基本运算 二、队列的存储结构和基本运算
实现 三、队列的应用举例
(3) 典型例题
学习方法：小组讨论、实验操作
课后作业：
1.利用栈，编写一算法将已知数组中元素倒序排列，用非形式算法描
述，并编写 c 语言程序。试分析所编程序的时间和空间复杂度。
第四章：串和数组
（授课时间：第二学期第 8,19 周）
教学目标：通过本章教学，使学生了解串和数组的基本概念，了解串的存储结构
及其基本运算的实现，了解数组的逻辑结构和基本操作。
教学重点：串和数组的概念及应用。
教学难点：串基本运算的实现；多维数组。
学 时：课堂教学 4 学时，课外自主学习时间不少于 4 学时
教学方法：讲授法、演示法
主要内容：
(1) 串
一、串的基本概念 二、串的基本运算 三、串的存储结构及其基本
运算的实现
(2) 数组
一、数组的逻辑结构和基本操作 二、数组的存储结构 三、稀疏矩
阵
(3) 典型例题
学习方法：小组讨论、实验操作
第五章：树与二叉树
（授课时间：第二学期第 10,11,12 周）
教学目标：通过本章教学，使学生了解树与二叉树的概念，掌握树与二叉树的基
本操作及其实现。
教学重点：树与二叉树的概念、遍历及应用。
教学难点：二叉树的遍历；最优二叉树。
学 时：课堂教学 6 学时，课外自主学习时间不少于 6 学时
教学方法：讲授法、演示法
主要内容：
(1) 树的概念与基本操作
(2) 二叉树
一、二叉树的基本概念 二、二叉树的主要性质 三、二叉树的存储
结构与基本操作 四、二叉树的遍历
(3) 树与森林
(4) 最优二叉树
(5) 典型例题
学习方法：小组讨论、实验操作
第六章：图
（授课时间：第二学期第 13,14,15 周）
教学目标：通过本章教学，使学生掌握图的基本概念，掌握图的存储结构和图的
遍历，初步掌握图的应用。
教学重点：图的概念、遍历及应用。
教学难点：邻接矩阵和邻接表；图广度优先和深度优先遍历；最小生成树；最短
路径算法。
学 时：课堂教学 6 学时，课外自主学习时间不少于 6 学时
教学方法：讲授法、演示法
主要内容：
(1) 图的基本概念
(2) 图的存储结构
一、邻接矩阵 二、邻接表
(3) 图的遍历
一、深度优先遍历 二、广度优先遍历
(4) 图的应用
一、最小生成树 二、最短路径 三、拓扑排序
学习方法：小组讨论、实验操作
第七章：查找
（授课时间：第二学期第 16 周）
教学目标：通过本章教学，使学生了解查找的基本概念与术语，掌握常用查找算
法，了解哈希表与哈希方法。
教学重点：常用查找算法的比较，折半查找和二叉排序树的查找。
教学难点：二叉排序树的表示、查找、插入、删除算法及其性能分析方法。
学 时：课堂教学 2 学时，课外自主学习时间不少于 2 学时
教学方法：讲授法、演示法
主要内容：
(1) 基本概念与术语
(2) 静态查找表
一、静态查找表结构 二、顺序查找 三、有序表的折半查找 四、分
块查找
(3) 动态查找表
(4) 哈希表
(5) 典型例题
学习方法：小组讨论、实验操作
第八章：排序
（授课时间：第二学期第 17 周）
教学目标：通过本章教学，使学生掌握排序的基本概念，掌握三种简单的排序方
法。
教学重点：常用排序算法的分析、特点及比较。
教学难点：插入排序、冒泡排序和选择排序等各种排序算法及其性能分析方法。
学 时：课堂教学 2 学时，课外自主学习时间不少于 2 学时
教学方法：讲授法、演示法
主要内容：
(1) 基本概念
(2) 三种简单的排序方法
一、直接插入排序 二、冒泡排序 三、简单选择排序
(3) 希尔排序
(4) 快速排序
(5) 堆排序
(6) 归并排序
(7) 各种排序方法的比较与讨论
学习方法：小组讨论、实验操作