《数据结构与算法》课程教学大纲
《数据结构与算法》课程教学大纲
课程名称：数据结构与算法
英文名称：Data structures and algorithms
课程类型：专业平台课
总学时及学分： 64学时/4学分
授课形式：理论授课
适应对象：软件工程专业
主要先修课程： 《高级语言程序设计》 《离散数学》
执行日期：2017年9月
一、 课程的性质与任务
性质：《数据结构与算法》是软件工程及相关专业的一门综合性的专业基础课。
任务：是介于数学、计算机硬件和计算机软件之间的一门软件工程专业的核心课程，同时数据结构技术也被广泛应用于物联网、信息科学、系统工程、应用数学以及各种工程技术领域。本课程主要介绍如何合理的组织和表示数据、如何有效的存储和处理数据、如何正确的设计算法以及对算法的优劣作出分析和评价。
二、 课程的教学目标
通过本课程学习，要求学生掌握数据结构和算法的基本概念和技术，并设计相应的操作算法。掌握线性表、栈和队列、串、广义表、树和二叉树、图等典型数据结构及相关算法，以及排序、查找等重要技术。
该课程的学习目的是：提高学生的算法设计能力，使学生能够对于给定问题选择合适的数据结构，设计高质量算法，能够编写解决复杂问题的程序。该课程为一些后续的计算机专业课程打下扎实深厚的基础，提供知识准备。
三、 教学内容及其基本要求
第一章 绪论
（一）教学内容
主要内容：
1、数据结构的概念；
2、抽象数据类型；
3、算法和算法分析。
主要教学环节的组织：课堂讲授。
思考：
1、试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这三方面的内容。
2、比较逻辑结构和存储结构的关系。
3、比较数据结构的概念与程序设计语言中数据类型的概念的区别与联系。
教学重点：了解数据结构的逻辑结构、存储结构及数据运算等三方面的概念及相互关系，算法的性能评价。
教学难点：抽象数据类型的概念的理解，算法时间复杂度的分析方法。
教学基本要求： 本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。
第二章 线性表
主要内容：
1、线性表的逻辑结构；
2、线性表的顺序存储及运算实现；
3、线性表的链式存储及运算实现；
4、顺序表和链表的比较。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、请比较顺序表与链表的优缺点。
2、单链表具有随机存取的性质吗？顺序表呢？为什么？
教学重点：顺序表和单链表上实现的各种基本算法及相关的时间性能分析。
教学难点：用本章所学到的基本知识设计算法解决与线性表相关的实际应用问题。
教学基本要求：本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算在相应的存储结构上的实现。要求在熟悉这些内容的基础上，能够针对具体的应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。
第三章 栈和队列
主要内容：
1、栈及其性质；
2、栈的应用举例；
3、队列及其性质；
4、队列的应用举例。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、栈和队列各有什么特点，什么情况下用到栈，什么情况下用到队列？
2、循环队列是如何实现“循环”的？
教学重点：栈和队列在两种存储结构上基本操作的实现。
教学难点：循环队列中对边界条件的处理及栈和队列的应用。
教学基本要求：本章的目的是介绍栈和队列的逻辑结构定义及其在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下使用栈或队列，掌握在不同的存储结构上实现栈和队列的方法。
第四章 串
主要内容：
1、串及其基本运算；
2、串的定长顺序存储及基本运算；
3、串的堆存储结构。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、KMP算法与朴素的模式匹配算法相比有何优越性？
2、求模式串的next函数值有什么意义？
教学重点：串的存储结构及基本运算。
教学难点：模式匹配。
教学基本要求：本章目的是介绍串的逻辑结构、存储结构及其字符串上的基本运算，要求掌握串的各种存储结构、串的常用运算及模式匹配算法。
第五章 数组、特殊矩阵和广义表
主要内容：
1、多维数组；
2、特殊矩阵的压缩存储；
3、稀疏矩阵；
4、广义表。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、如何用一维的空间表示多维的数组？
2、为什么要对矩阵进行压缩存储？
3、广义表和一般的线性表有和异同？
教学重点：多维数组的存储方式、矩阵的压缩存储方法、广义表的定义及基本运算。
教学难点：特殊矩阵的压缩方法，稀疏矩阵的压缩存储及其运算的实现。
教学基本要求：本章的目的是介绍多维数组的逻辑结构特征及存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念及存储实现方法。
第六章 二叉树
主要内容：
1、二叉树的定义与性质；
2、二叉树的存储实现基本操作的实现；
3、二叉树的遍历；
4、线索二叉树；
5、二叉树的应用。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？
2、在结点数多于1的哈夫曼树中存在度为1的结点吗？
3、遍历二叉树的方法有哪些？遍历二叉树的实质是什么？
教学重点：二叉树的性质，二叉树的遍历算法及其应用，哈夫曼树。
教学难点：二叉树性质的证明，基于二叉树遍历解决实际问题，哈夫曼编码。
教学基本要求：本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化及二叉树的应用等内容，要求掌握二叉树的性质、存储结构，掌握二叉树的各种遍历算法及其应用，哈夫曼树等。
第七章 树和森林
主要内容：
1、树的概念与表示；
2、树的基本操作与存储；
3、树、森林与二叉树的转换；
4、树或森林的遍历；
5、树的应用。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、树、森林和二叉树之间有什么关系？
2、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？
教学重点：树和森林的存储结构、遍历，树、森林和二叉树之间的转换。
教学难点：树和森林的遍历及由遍历序列恢复树或森林，用相关知识解决与树的实际应用问题。
教学基本要求：本章介绍树和森林的定义、存储结构、和二叉树之间的转换、遍历及树的应用等内容，要求掌握树与二叉树之间的转换及其树的应用等。
第八章 图
主要内容：
1、图的基本概念 ；
2、图的存储表示；
3、图的遍历；
4、生成树与最小生成树；
5、最短路径；
6、有向无环图及其应用。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、比较Prim算法和Kruskal算法，当边数较少时用哪一个方法较好？
2、用哪些方法可以判断有向图中有环路存在？
3、加快一个关键活动，一定能缩短工期吗？
教学重点：图的存储结构，图的遍历算法，图的几种应用算法。
教学难点：最小生成树，最短路径，拓扑排序，关键路径。
教学基本要求：本章的目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法。
第九章 查找
主要内容：
1、基本概念；
2、静态查找表；
3、动态查找表；
4、哈希表查找(杂凑法) 。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。
2、含有9个叶子结点的3阶B–树中至少有多少个非叶子结点？含有10个叶子结点的3阶B–树中至少有多少个非叶子结点？
3、比较哈希查找方法与其他查找方法的区别。
教学重点：顺序查找、二分查找、二叉树排序树、平衡二叉树，B-树以及哈希表上的查找思想、算法实现及查找性能的分析。
教学难点：二叉排序树的删除，平衡二叉树的调整，B-树的插入和删除，哈希表中处理冲突的方法。
教学基本要求：本章目的是介绍各种存储方式下的查找表的查找方法，以及各种查找方法的时间性能分析。
第十章 排序
主要内容：
1、基本概念；
2、插入排序；
3、交换排序；
4、选择排序；
5、二路归并排序；
6、基数排序；
7、外排序。
主要教学环节的组织：
课堂教学与实践。
思考题：
1、如果只想得到一个序列中第k小元素前的部分排序序列，最好采用什么排序方法？为什么？
2、有n个不同的英文单词，它们的长度相等，均为m，若n>>50,m<5，试问采用什么排序方法时间复杂度最佳？为什么？
教学重点：各种排序的思想、算法实现、稳定性、适用情况、时间空间复杂度分析。
教学难点：希尔排序，快速排序，堆排序。
教学基本要求：本章目的介绍5类内部排序方法的基本思想、排序过程、算法事现、时间和空间性能的分析以及各种排序方法的比较和选择。
四、 各教学环节学时分配
五、 教学建议
完成每章的讲解之后，要进行习题的布置，注重精而不要求多。结合每章节重点内容，多进行案例分析和专题研讨。
六、 考核评价方法及要求
考核方式：考试
总评成绩=平时成绩+期末考试成绩
平时成绩占30%
期末成绩占70%
七、 教材与主要教学参考资源
教 材：
严蔚敏：《数据结构》，人民邮电出版社，2017
教学参考资源：
1、刘振鹏：《数据结构》，中国铁道出版社，2015
2、张晓莉：《数据结构与算法》，机械工业出版社，2012
3、严蔚敏:《数据结构（C语言版）》，清华大学出版社，2015
制定者：（李爱超、2017年8月）
审核者：（刘晓星、2017年8月）
批准者：（张景、2017年8月）
