《数据结构与算法（Java）》课程教学大纲
一、课程基本信息
课程编号：12157
课程名称：数据结构与算法(Java)
英文名称：Data Structure and Algorithm(Java)
课程类型：学科基础课
课程要求：必修
学时/学分：56/3.5（讲授学时：48  实验学时：8）
先修课程：面向对象程序设计（Java）、离散数学
后续课程：数据库系统原理、Spark大数据处理
适用专业：数据科学与大数据技术
二、课程描述
“数据结构与算法”是数据科学与大数据专业的一门专业基础课。课程主要研究数据的各种逻辑结构和数据在计算机中的存储表示，以及各种非数值运算的算法的实现，充分描述了各种数据结构的特点。内容包括：线性表、栈、队列、数组、树、图等常用的数据结构及常用算法的设计；常用的各种查方法和排序算法的实现；算法的时间空间复杂性的分析方法等。 通过对基本数据结构及存储结构的深刻理解，掌握解决工程应用中的复杂数据的定义、组织及具体问题的算法设计方案。通过对综合选择数据结构和算法，以及结合性能要求、存储限制等因素，设计优化的解决方案。通过对时间复杂度和空间复杂度的概念的理解，对算法和整个算法设计方案进行评价，比较优劣，得出有效算法设计方案。通过课程的学习，使学生能够应用基本数据结构的定义和常用算法设计方法，表达和解决实际工程问题。提高学生分析问题能力、建立合适模型和设计有效解决方案具有重要作用。
三、课程教学目标
1. 能建立基本的线性表、树和二叉树、图、查表等数据结构的数学描述和组织形式，能选择和运用与结构对应的算法进行有效的数据访问。（支持毕业能力要求1）
2. 能运用数据结构的相关概念和术语识别、表达工程问题中的需求，形成适当的问题解决方案。（支持毕业能力要求1）
3. 能基于线性结构、树和图等主要数据结构实现查、排序等操作，以及与特定需求相关的算法设计，解决复杂软件工程问题中与之相关的关键技术环节，并运用数学方法分析算法的时间复杂度和空间复杂度。（支持毕业能力要求2）
4．能对较大型工程问题进行有效分解，合理选择、使用多种数据结构和算法确定解决方案，设计软件得到结果，并撰写出解决方案报告和算法设计文档。（支持毕业能力要求4）
四、教学内容、基本要求与学时分配
单元
教学内容
单元教学目标
学时
教学
方式
对应课程教学目标
1
一、绪论
1.1 数据结构的概念
1.2 数据结构中的术语
1.3 算法与算法分析
1.4 Java提供的泛型方法
(1)能正确解释数据结构的基本概念和重要术语；(2)能用Java语言表示抽象数据类型；(3)能列举一些数据结构的工程应用示例；(4)能说明算法的主要特性及算法分析过程，能用符号描述复杂度的高低。
2
讲授
1、2
2
二、线性表
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 线性表的应用举例
(1)能定义线性表的逻辑结构；
(2)能定义线性表顺序存储和链式存储结构，并设计其主要访问算法；(3)能运用数学方法分析线性表访问算法的时间复杂度。
6
讲授
1、2、3
实验1：线性表的应用举例
能用Java语言设计基于单链表表示的一元多项式定义和求和算法程序，并用数据校验算法的有效性，撰写实验文档。
2
实验
4
3
三、栈和队列
3.1 栈
3.2 队列
3.3 栈与队列的应用举例
(1)能正确解释栈、队列的概念和访问特性；(2)能完成栈和队列的数据结构定义；(3)能设计针对栈和队列访问的有效算法和程序。(4)能列举工程问题实例，并利用栈和队列作为解决软件系统设计方案予以解决。
6
讲授
2、3
4
四、数组和广义表
4.1 数组的定义
4.2 数组的顺序表示和实现
4.3 矩阵的压缩存储
(1)能熟练使用数组组织数据并快速访问；(2)能运用数组实现矩阵的压缩存储；(3)能查阅文献，了解工程计算应用存在的稀疏矩阵，依据特点设计有效的压缩存储算法。
4
讲授
2
5
五、树和二叉树
5.1 树的定义和基本术语
5.2 二叉树
5.3 遍历二叉树和线索二叉树
5.4 树和森林
5.5 赫夫曼树及其应用
(1)能用数学语言准确定义树和二叉树；(2)能分析并得出二叉树的基本性质，并说明性质间的等价性；(3)能依据哈夫曼树定义写出构造算法，并用哈夫曼树设计哈夫曼编码；(4)能构造算法实现二叉树遍历；(5)能通过查阅文献，出3个以上工程应用案例，给出解决方案，并用二叉树相关算法处理局部问题。
8
讲授
1、2、3
实验2：二叉树遍历算法验证
(1)能定义二叉树的数据结构；
(2)能设计三种递归算法和两种非递归算法遍历（创建）二叉树；(3)能用有效数据序列设计实验，验证先根遍历和中根遍历生成二叉树算法的正确性。
2
实验
4
6
六、图
6.1 图的定义和术语
6.2 图的存储结构
6.3 图的遍历
6.4 图的连通性问题
6.5 有向无环图及其应用
6.6 最短路径
(1)能说明图的定义和常见词汇的含义；(2)能分析得出并解释图的基本性质；(3)能构造图的遍历算法、最小生成树算法、关键路径算法和最短路径算法；(4)能通过查阅文献，出4个以上工程应用案例，并结合上述算法给出解决方案。
8
讲授
1、2、3
实验3：图的存储和图的遍历算法设计
(1)能定义图的邻接表存储结构；(2)能设计程序运用迪杰斯特拉算法计算图的最短路径；(3)能用城市交通图构建实验，验证算法的有效性。
2
实验
4
7
七、内部排序
7.1 概述
7.2 插入排序
7.3 快速排序
7.4 选择排序
7.5 归并排序
7.6 基数排序
(1)能正确区分并准确说明各排序算法的核心特征；(2)能用程序实现种排序算法；(3)能分析各算法的效率；(4)能设计一个适用于不同数据类型的快速排序算法程序。
8
讲授
2、3
实验4：排序算法设计
能用Java语言实现各种排序算法，并利用适当的输入数据构造实验，验证算法的正确性。
2
实验
4
8
八、查
8.1 静态查表
8.2 动态查表
8.3 哈希表
(1)能准确叙述静态查表、动态查表和哈希表的定义；(2)能用程序实现静态查表、动态查表和哈希表查算法；(3)能分析算法的效率。
6
讲授
2、3
五、其他教学环节（课外教学环节、要求、目标）
1. 自学
Java语言的泛型和集合框架要在授课前自学授课内容，达到能运用实例解释基本概念的要求。
2. 运用
在线性表、二叉树和图单元学习后，自行收集资料，阅读文献，分别针对某个有实际工程背景的应用问题设计解决方案，综合运用Java语言描述、建立数据结构模型，设计解决方案，并撰写Java程序进行验证和总结。
六、教学方法
本课程以课堂教学为主，辅助以上机验证实验，结合作业、撰写设计文档和报告等教学手段和形式完成课程教学任务。
在课堂教学中，通过讲授、提问、讨论、演示等教学方法和手段，吸引学生的注意力，提高
学生的学习兴趣，促进学生之间的沟通与交流；引入实际工程应用问题，引导学生出课程内容的适用点，进而得到解决方案，锻炼学生解决工程问题的能力；安排学生课外观看教学视频，对课堂内容进行扩展，培养其自我学习和不断学习的习惯。
在部分重要章节后期，安排学生自己查阅文献，发现工程应用案例，通过分组、讨论等方式，综合运用数据结构知识、数学、计算机语言等工程知识分析问题，设计解决方案，撰写研究报告，以此提高解决问题和沟通协作能力，获取和整理信息、准确运用语言文字的表达能力，激发学生的创新思维。
七、学习评量
学习成绩由平时成绩（含作业成绩、实验与报告）和期末考试成绩组成。各部分所占比例和评价内容、方法如下：
1. 平时成绩（30%）
(1)作业成绩：15%。主要考核对课堂学习的知识点的复习、理解和掌握程度；以答题数量和正确率为评价标准。
(2)实验成绩：15%。
1）实验过程。主要考核单链表、二叉树、常用排序方法中，数据结构的定义及常用算法设计和解决方案进行评价。共9分，分3次，每次3分。
2）实验报告。主要考核单链表和二叉树遍历实验报告，对报告撰写规范及算法设计方案合理性为评分标准，共6分，分2次，每次3分。
2. 期末考试成绩：70%。主要考核综合应用基本概念分析和解决问题的能力和程度；书面考试形式，题型以综合应用和算法设计为主，按正确性评分。
3. 说明
(1)作业、实验报告中有雷同时，所有雷同回答均不得分。
(2)可参加辽宁省跨校修学分学习方式，利用指定“八、教学资源”中指定的MOOC的合格证书+评价作为课程学习成绩，参加其他MOOC并计划代替学习成绩者须在课前向任课教师提出申请，由课程组教师讨论决定。
八、教学资源
1．教材
二叉树的遍历及应用实验报告[1] 刘小晶，杜选，朱蓉，等．数据结构--Java语言表述（第二版）．清华大学出版社，2018．
2．参考教材
[1] 叶小平，陈瑛．数据结构与算法简明教程（Java语言版）.  清华大学出版社，2016.
[2] 雷军环，吴名星．数据结构（Java语言版）. 清华大学出版社， 2018.
[3] 严蔚敏，吴伟民．数据结构题集（C语言版）．清华大学出版社，2009．

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。