数据结构（Java语言描述） 教学大纲.docx

《数据结构（Java语言描述） 教学大纲.docx》由会员分享，可在线阅读，更多相关《数据结构（Java语言描述） 教学大纲.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程教学大纲一、课程基本信息课程名称：数据结构，Data Structure课程编码：总学时：56学分：3. 5适应专业：电子信息类专业、计算机类专业课程性质：专业基础课教材：罗福强，数据结构（Java版）第2版，人民邮电出版社，2022年教材特色：（1）内容定位为应用型本科，适合本、专科相关课程教学。（2） 以面向对象思想描述各类数据结构和算法。（3）强调应用和实践，突出新技术， 介绍了适合大数据和人工智能的新的数据结构。二、本课程与相关课程的关系在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序 设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程

2、 序和大型应用程序的重要基础。数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的 经验及能力，本课程的全部实例均是用Java语言实现的，因此，学习本课程必 须具备计算机基础、Java程序设计等前导课程的基础知识和基本技能。本课程将为以下后续课程的学习奠定基础：计算机操作系统、TCP/IP网络 编程、软件工程、JSP程序设计、Android应用开发、大数据原理与应用等。三、课程目标及要求：（-）本课程目标本课程的设计目标遵循“一基两轴、三阶递进”的基础上，“一基”即以知识 为基础，“两轴”指以提升技能和思维为目标，“三阶递进”指的是实现低阶到中 阶再到高阶的提高。在基础方面，使学生

3、掌握常用数据结构的基本概念及其不同 的实现方法 在技能方面,通过系统学习能够在不同存储结构上实现不同的运算， 并增强学生的面向对象程序设计能力和数据结构应用能力的培养和提高。本课程采用高阶教学方式，使学生掌握数据结构及其基本算法，实现初阶学 习目的；使掌握将数据结构知识应用到实际项目中的能力，实现中阶学习目的； 最后能在应用中能应用所学知识和技能实现一定的创新并解决实际项目问题，实 现高阶学习目的，提高学生深度学习能力及解决实际问题的能力，从而为新兴的 技术应用提供更多的支持。（-）本课程要求以项目驱动，主要教学方式为初阶和中阶思维和技能教学。内部排序部分主 要教学方式为高阶思维和技能教学，让

4、学生掌握不同的内部排序在实际项目中是 如何应用的。五、课程实践的要求：课堂实践，要求学生每人独立完成实验报告要求的内容，达到实验的目的。 本课程所需要的实践环节的形式：课堂上机实验。课堂实验（24个学时的实践学时），要求学生熟悉数据结构课程中的有关算 法，并用Java语言实现，在Eclipse环境下调试运行；独立完成课后的实训项 目。本课程待选的实验项目如下表所示。序号实验项目名称学时数类型1线性表的实现；单链表和双链表的实现3验证型2栈和队列的实现;双栈共享存储空间相关算法的实 现，包括初始化、入栈、出栈、取栈顶元素、置栈 空、判栈空;利用已有数据结构模拟舞伴配对问题。3验证型3串和矩阵的实

5、现；日志分析程序，根据给定的网站 日志文件，统计访问本网站的用户数、访问频率最 高的用户、网站哪个时间段访问频率最高、哪些网 页用户访问频率最高；利用矩阵运算完成给定任 务。2验证型-1二叉树的实现；利用已有算法，统计某二叉树的结 点总数、输出所有叶子结点、删除某个结点、交换 子树等。3设计型5图的实现；利用已有算法完成图的创建、对图进行 深度优先遍历和广度优先遍历、求最小生成树及两 点之间的最短路径。3验证型6查找：二又平衡树的构建和查找的实现及应用3设计型7各种排序查找算法的实现及应用3综合型8项目驱动:完成布置的校企合作项目以及纵向项目 业务逻辑中数据结构相关的编程，并能根据项目需 求进

6、行一定的创新4综合型合计24注：实验类型包括：验证型、设计型、综合型和创新型。六、主要教学方法：为了方便考勤和学生讨论，将学生为学习小组，每组3至5人。有组长负责 组织、督促本组学生按时出勤，报告考勤，组织小组学习讨论。课堂讲授：教师通过口头语言以讲演、分析等方式，向学生讲解课程内容。 帮助学生理解知识点。多媒体课件：将大量的文本、图像、动画、声音和视频等资源按照教学大纲、 每章知识点进行整合，将知识点变得更加容易理解。问题导向法：课堂上提出与知识点相关的问题，让学生作答，回答后进行点 评。激发学生的思考能力与发散思维。案例分析法：新的理论知识开始时，使用问题导向法引入新知识，生活实例 来讲解

7、概念，采用典型的案例分析知识点。并在每部分知识点的讲解过后，设计 课堂提问环节，有效地保障授课质量。课堂讨论：将具有讨论性的知识点让学生分组讨论，讨论后每组阐述观点, 教师最后进行评论。提高学生的批判性思维与团队协作能力。上机实验：实验课要求学生独立完成相应任务，并检查。培养学生的动手实 践能力。头脑风暴法：课堂上提出开放性问题，让学生进行头脑风暴，提出所有可能 的答案或解决方法，提高学生的辩证思维能力。项目驱动法：以35人的学生团队形式，共同完成一个自选数据库项目的分 析与设计，提交设计方案，最后安排项目答辩，以培养学生团队协作、组织管理、 语言表达等非认知能力，培养创新思维。翻转课堂法：为

8、相关知识点制作视频或资料，并提前发给学生，作为学生预 习和复习的资料，并通过课堂提问、课堂测验、课后作业、课后思考题等多种形 式保障学生学习课程视频。培养学生的自学能力和思考能力。七、典型作业（报告、设计、习题）练习及要求：（1）布置一课一文（包含课程论文），并要求学生按时提交。（2）对重点内容布置作业，学生按时完成并提交。（3）课堂练习目的明确，并逐一检查，检查后方可得分。（4）针对翻转课堂的知识点，布置课堂练习（或课堂实践）。课堂上随机选 择学生回答或检查，课后均要上交、批改。八、课程考核和成绩评定：1 .考核方式：闭卷考试2 .主要考核内容：针对各章节的教学要求中理解、掌握的部分来重点考

9、核。其中初级知识、能 力、思维占45%,中级知识、能力、思维占35%,高级知识、能力、思维占20机3 .成绩评定构成：学科成绩总分100分：期末考试占50%,平时成绩占50%。注意：平时成绩与期末成绩都必须高于50分才会记为有效成绩。4 .平时成绩组成：考勤（20分）+作业（20分）+随堂测验（30分）+课程论文（设计）（30分）+ 课堂表现。同时，根据学生课堂内外表现平时成绩可以有额外加分。（1）考勤：20分旷课1次扣5分，3次取消考试资格。迟到或早退1次扣2分。必须提前 请假，否则按旷课处理。（2）作业：20分包括课前翻转任务、课后作.业和基础算法上机练习完成情况评价；主要评价 学生完成作

10、业或任务时的态度、知识或技能的掌握程度以及完成情况，态度良好、 掌握情况好和全部完成评价为优，给满分评分。作业任务发布到锦城在线，计算 平均分。（3）随堂测验：30分对于重点知识进行随堂测验，每次测验进行批改打分。以锦城在线上考试的 平均分计算。（4）课程论文（设计）：30分包括课程的设计和课程论文。本课程要求学生以小组形式完成一个数据结构 应用项目的综合设计，具体项目可由学生自主申报，也可以选做教材中的项目。（5）课堂表现课堂上回答问题的同学可以加分。对于上课不认真，玩手机，玩游戏的同学 予以扣分，发现一次扣2分。从数据的逻辑结构、存储结构和操作运算三个维度掌握线性表、栈、队列、 串、数组、

11、广义表、树和图等常用的数据结构。理解在各种数据结构之上实现的 插入、删除、排序和查找等运算，对算法的时间和空间复杂度有一定的分析能力。 针对不同的应用问题，能选择合适的数据结构及设计有效的算法解决之，并能通 过高阶思维能力训练使学生能具备创新能力，课程要求培养以下能力。知识要求(1)熟悉数据结构的 概念和应用场景。【低 阶】(2)掌握线性关系的概念和基本算法。【中 阶】(3)掌握树，特别是 二叉树的概念和基本 算法。【中阶】(4)掌握图的概念和 基本算法，以及树与图 的相互转换。【中阶】(5)掌握常见的查找 算法。【中阶】(6)掌握常见的内部 排序算法。【中阶】能力要求(1)掌握算法的评估 标

12、准，理解时间复杂度 度和空间复杂度的计 算方法。【中阶】(2)能编程实现顺序 表、链表、树与图的基 本功能，并在此基础上 进行变通解决一些比 较简单的实际问题，完 成布置的项目。【中阶】(3)能灵活使用学习 的知识完成布置的实 际项目和面试题中遇 到的算法，完成布置的 项目。对于不熟悉的知 识学生需要能够主动 学习。【高阶】思维培养(1)中阶学习：能根 据实际情况使用学习 的知识解决实际问题。(2)高阶学习：能在 课堂教学中的项目、参 与的校企合作项目以 及纵向项目中灵活地 实现业务逻辑的编程, 并能根据项目需求进 行一定的创新。(3)各种思维方式的 锻炼：如算法思维、面 向对象思维、数据结构

13、 思维、程序结构思维、 创新思维等。四、课程内容及学时分配:1.总体课时安排辅导答疑课讲授课24学时实验实训课20学时习题(含课程论文)课学时讨论课6学时学时阶段性测验2学时课程设计（大型作业）（不含课外）4学时课程拓展4学时机动学时2 .章节课时安二徘（不含课外）章节理论实验小计第1章404第2章7310第3章235第4章224第5章7310第6章538第7章235第8章336课程设计044合计312456第1章 数据结构简介（低阶思维和技能教学）1 .主要内容1.1 数据结构的作用和意义1.2 基本概念和术语L3数据结构的表示L4泛型类和泛型接口1.5 算法和算法分析2 .教学要求了解数据

14、结构的意义，数据结构在计算机领域的地位和作用；掌握数据结构各名词、术语的含义和有关的基本概念；数据的逻辑结构和存 储结构之间的关系；了解使用JAVA语言对数据结构进行抽象数据类型的表示和实现的方法；了解算法的五要素；掌握计算语句频度估算算法时间复杂度的方法；主要教学方式为初阶思维和技能教学。泛型类和泛型接口主要教学方式为高 阶思维和技能教学，让学生掌握泛型类和泛型接口应用的能力。3 .教学重点与难点相关知识点：相关术语：数据、数据元素、数据对象、数据结构数据逻辑结构：集合、线性结构、树和图数据的物理结构：顺序和非顺序结构算法的五要素和时间复杂度及空间复杂度学习重点：数据的逻辑结构和存储结构及其

15、之间的关系算法时间复杂度的计算学习难点：算法时间复杂度的计算4 .翻转教学（课外拓展）Java泛型类和泛型接口5 2章线性表高阶思维和技能教学）1 .主要内容1 .1线性表的逻辑结构2 . 2线性表的顺序表示和实现3 .3线性表的链式表示和实现4 .4链表的应用示例5 .教学要求掌握线性表的逻辑结构及两种不同的存储结构；掌握两类存储结构（顺序和链式存储结构）的表示方法，以及单链表、循环 链表、双向链表的特点；掌握线性表在顺序存储结构及链式存储结构上实现基本操作（查找、插入、 删除等）的算法及分析；能够针对具体应用问题的要求和性质，选择合适的存储结构设计出有效算法, 解决与线性表相关的实际问题；

16、6 .教学重点与难点相关知识点：相关概念：线性表、顺序表、链表（单链表、循环链表、双向链表）、头指 针、头结点顺序表的表示及基本操作链表的表示及基本操作学习重点：线性表的逻辑结构及两种不同的存储结构链表的表示和实现学习难点：链表的表示和实现7 .翻转教学一单链表的特征与操作以项目驱动，主要教学方式为中阶和高阶思维和技能教学。顺序表、各种链 表部分主要教学方式为高阶思维和技能教学，让学生掌握顺序表、各种链表在实 际应用中解决问题的能力。8 3章栈和队列（低阶、中阶、高阶思维和技能教学）1 .主要内容3.1栈3. 2顺序队列3. 3链式队列（翻转教学）3.4栈和队列的应用举例2.教学要求掌握栈的特

17、点、表示和实现；熟悉栈的典型应用并编程实现（如：语法检查、回朔算法、递归算法、表达 式求值）；掌握队列的特点、表示和实现；3.教学重点与难点相关知识点：相关术语：栈、队列物理结构：顺序栈、链栈、顺序队列、链队列学习重点：栈的逻辑结构、存储结构及其相关算法队列的逻辑结构、存储结构及其相关算法学习难点：栈的定义和应用算法：递归以项目驱动，主要教学方式为初阶和中阶思维和技能教学。循环队列部分主 要教学方式为高阶思维和技能教学，让学生掌握循环队列在实际应用中是如何应 用的。第4章串、矩阵和广义表（低阶、中阶、高阶思维和技能教学）1 .主要内容（翻转教学）4.1 串及其运算4.2 串的顺序存储与实现4.

18、 3矩阵1 .4广义表2 .5串的应用：文本编辑3 .6矩阵的应用：矩阵运算与实现4 .教学要求掌握串的特点、表示和实现；熟悉串的类型和作用；掌握稀疏矩阵；了解广义表的概念和相关操作；5 .教学重点与难点相关知识点：相关术语：串串的类型：子串，空串，空格串稀疏矩阵广义表的表头，表尾学习重点：串的逻辑结构、存储结构及其相关算法串的操作应用对广义表的操作学习难点：串的基本操作实现6 .翻转教学一串与矩阵（课外拓展）主要教学方式为初阶和中阶思维和技能教学。主要教学方式为高阶思维和技 能教学，让学生掌握串和矩阵在实际应用中解决问题的能力。第5章 树和二叉树（高阶思维和技能教学）1 .主要内容1.1 树

19、的定义和基本术语1.2 二叉树（翻转教学）5. 3二叉树遍历5. 4树和森林5. 5二叉树的应用：Huffman树与Huffman编码5.6二叉树的应用：二叉排序树与查找2 .教学要求了解树的定义和基本术语；了解树及二叉树的存储结构；重点掌握二叉树的结构特性及相应的证明方法；掌握二叉树的各种遍历算法；掌握树和二叉树之间的转换；了解最优树的特性；了解Huffman树、编码的实现及应用；了解二叉排序树及其应用与实现；3 .教学重点与难点相关知识点：树的常用术语：树、二叉树、完全二叉树、满二叉树、结点、结点的度、树 的高度、有序树、无序树、Huffman树、二叉排序树等学习重点：树及二叉树的存储结构

20、二叉树的遍历与线索化Huffman树和二叉排序树学习难点：树和二叉树之间的转换、二叉树的遍历与线索化、哈夫曼树的构造4 .翻转教学一二叉树的遍历操作以项目驱动，主要教学方式为高阶思维和技能教学。二叉树表部分主要教学 方式为高阶思维和技能教学，让学生掌握二叉树在实际项目中解决问题的能力。5 6章图（低阶、中阶思维和技能教学）1 .主要内容1.1 图的定义及其常用术语1.2 图的存储结构6. 3图的遍历6. 4生成树和最小生成树（翻转教学）6. 5图的应用2 .教学要求了解图的定义和术语掌握图的两种存储结构极其构造算法；重点掌握图的两种遍历算法；了解图的连通性问题极其判断；了解有向无环图极其应用（

21、拓扑排序和关键路径）了解最短路径问题的解决方法。3.教学重点与难点相关知识点：图的常用术语：有向图、无向图、完全图、有向完全图、稀疏图、稠密图、 网、邻接点、路径、简单路径、回路或环、简单回路、连通、连通图、强连通图、 生成树。图的邻接矩阵存储表示和邻接表存储表示、图的深度优先和广度优先遍历、 最小生成树、拓扑排序和关键路径、最短路径等学习重点：图的存储结构、图的遍历算法学习难点：图的应用算法：最小生成树、拓扑排序、关键路径和最短路径以项目驱动，主要教学方式为初阶和中阶思维和技能教学。最小生成树部分 主要教学方式为高阶思维和技能教学，让学生掌握最小生成树在实际应用中是如 何应用的。第7章查找（

22、中阶、高阶思维和技能教学）1 .主要内容1. 1基本概念7. 2静态查找表8. 3动态查找表9. 4哈希表2 .教学要求掌握顺序查找、折半查找的实现方法；掌握动态查找表（包括：二叉平衡树、B-和B+树）的构造和查找方法； 掌握哈希表、哈希函数冲突的基本概念和解决冲突的方法；3.教学重点与难点相关知识点：查找在数据处理中的重要性查找算法效率的评判标准顺序查找、折半查找的基本思想、算法实现和查找效率分析二叉排序树的插入、删除、建树和查找算法及时间性能B-树的插入、删除及查找方法的基本思想哈希表、哈希函数、哈希地址和装填因子等有关概念哈希函数的选取原则及产生冲突的原因采用线性探测法和链地址法解决冲突

23、时，哈希表的建表方法、查找过程以及 算法实现和时间分析学习重点：掌握顺序查找、折半查找、二叉排序树上查找以及哈希表上查找的基本思想 和算法实现。学习难点:B-树的插入、删除及查找方法的基本思想哈希函数冲突的基本概念和解决冲突的方法主要教学方式为初阶和中阶思维和技能教学，在二叉排序树等查找中采用高 阶思维和技能教学，让学生掌握查找方法在实际项目中的使用。第8章排序（低阶、中阶阶思维和技能教学）1 .主要内容8. 1基本概念8. 2插入排序（翻转教学）8. 3交换排序-冒泡排序（翻转教学）8. 4选择排序10. 5各种排序方法的比较11. 学要求了解排序的定义和基本术语；掌握各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间复 杂度分析；了解稳定排序方法和不稳定排序方法的定义及判断。12. 学重点与难点相关知识点：排序的定义和基本术语各种内部排序方法的基本思想、算法特点、排序过程和它们的时间复杂度分 析方法。稳定排序方法和不稳定排序方法的定义及判断学习重点：各种简单排序、快速排序、堆排序、归并排序的排序方法、算法描述和性能 分析；各种排序方法的比较学习难点：针对实际问题如何选择合适的排序方法