数据结构（Java语言实现） 教学大纲 陈锐

《数据结构》教学大纲一、课程基本信息课程名称：数据结构学时/学分：64/4课程类型：□通识教育√学科基础□专业教育□自主发展课程性质：√必修□选修考核方式：√考试□考查适用专业：软件工程先修课程：Java程序设计后续课程：算法分析与设计二、课程简介三、课程目标（1）理解数据结构与算法的基本概念，掌握常用基本数据结构的逻辑结构、存储结构及其操作的实现，掌握算法时间复杂性、空间复杂性分析方法；具有精益求精、追求卓越的工匠精神。（2）掌握常用查找和排序算法，并能够理解不同算法的适用场景，理解认识规律、把握规律的重要性；（3）能够在工程实践中选择、构建合适的数据结构，描述复杂软件工程问题中的数据及数据之间的关系，体现科学思维能力；（4）能够在软件开发过程中，针对特定需求综合应用数据结构、算法分析与设计等知识解决实际问题，具有积极进取、追求卓越的创新意识。课程目标毕业要求指标点(1)(2)(3)(4)1.3能够在对复杂软件工程问题的分析、推演中综合运用相关知识和数学模型方法。√2.1能够运用软件工程相关科学原理，识别、判断复杂软件工程问题的关键环节。√2.2能够运用软件工程相关科学原理和数学模型方法，准确描述复杂软件工程问题。√3.2能够针对特定需求，完成软件系统模块的详细设计。√四、教学内容、基本要求与学时分配1．理论部分标题教学内容与要求学时教学方式对应课程目标知识要素能力要素思政要素（一）基本理论（1）数据结构的研究内容（2）基本概念和术语（3）抽象数据类型的表示与实现（4）算法和算法分析了解数据结构的发展历程、研究内容；掌握数据结构的基本概念和术语；掌握算法分析基本技术。（1）积极思考、严谨治学、实事求是的科学态度；（2）事物都具有两面性，要学会辩证的看待事物。4案例引入讲授练习自主学习讨论(1)（二）线性表（1）线性表的类型定义（2）线性表的顺序表示和实现（3）线性表的链式表示和实现了解线性表的特点，掌握线性表的顺序和链式存储结构及其基本操作的实现；掌握线性表的应用。千里之行始于足下。树立时代责任和历史使命。6讲授案例分析演示(1)(4)（三）栈和队列（1）栈（2）栈与递归（3）队列了解栈和队列的特点与异同；掌握栈和队列的顺序和链式存储结构及其基本操作的实现；理解递归算法的工作过程，掌握用栈实现递归的方法；掌握栈和队列的应用。（1）遵守秩序，树立良好的规范意识，养成良好的行为习惯。（2）善于抓住事物的主要矛盾。6讲授案例分析演示(1)(4)（四）串、数组和广义表（1）串（2）数组（3）广义表了解字符串、数组的线性特点，掌握字符串、数组的顺序和链式存储结构及其基本操作的实现；掌握字符串的模式匹配算法；理解广义表的特点及其与线性表的关系；掌握广义表的常用存储结构及其基本操作的实现。培养积极探索，用于钻研，追求卓越的创新意识。6讲授案例分析演示(1)(4)（五）树和二叉树（1）树的定义和基本术语（2）二叉树（3）遍历二叉树和线索二叉树（4）树和森林（5）赫夫曼树及其应用了解树、二叉树的特点和基本概念；掌握树、二叉树的常用存储结构及其基本操作的实现；掌握遍历二叉树的不同方法；理解线索二叉树及其基本操作的实（1）弘扬中华优良传统和优良家风。（2）树立勤俭节约的传统美德。（3）事物之间的普遍联系性。8讲授案例分析演示(1)(3)(4)（六）图（1）图的定义和基本术语（2）图的存储结构（3）图的遍历（4）图的应用了解图的特点和基本概念；掌握图的常用存储结构及其基本操作的实现；掌握图的遍历操作；掌握图的应用。（1）学会全方位、多角度考虑问题，不同情况下利弊权衡与分析。（2）求真务实，懂得取与舍的辩证关系。（3）勤俭节约。6讲授案例分析演示(1)(3)(4)（七）查找（1）查找的基本概念（2）线性表的查找（3）树表的查找（4）散列表的查找了解查找及查找表的基本概念；掌握线性表、树表、散列表的常用查找方法；掌握不同查找算法的性能分析方法；掌握查找算法的选择应用。（1）发现认识规律、掌握规律的重要性。（2）动态与静止、特殊与一般的辩证关系。6讲授案例分析演示(2)(4)（八）排序（1）基本概念和排序方法概述（2）插入排序（3）交换排序（4）选择排序（5）归并排序（6）基数排序了解排序的基本概念；掌握不同种类排序方法的典型实现；掌握不同排序算法的性能分析方法；掌握排序算法的选择应用。（1）合理安排事情的优先顺序，有助于目标达成。（2）整体和部分的辩证关系。（3）事物发展是前进性和曲折性的辩证统一。6讲授案例分析演示(2)(4)2．实验部分实验名称(实验类型)实验内容实验目的基本要求实验设备学时安排方式对应课程目标实验一线性表（设计型）利用线性表的基本操作设计实现一个信息管理系统。（1）掌握线性表的定义和实现；（2）掌握线性表的基本操作。1、课前设计解决方案；2、课上实现并验证解决方案；3、课后提交实验报告和源代码。PC机Java编译环境2集中实验(3)实验二栈与队列（设计型）（1）掌握栈的定义及实现；（2（1）课前设计解决方案；（2）课上实现并验证解决方案；（3）课后提交实验报告和源代码。PC机Java编译环境2集中实验(3)实验三二叉树（验证型）利用二叉树的先序、中序、后序、层次遍历思想解决实际问题。（1）掌握二叉树的定义；（2）掌握二叉树的基本操作，如（1）课前设计解决方案；（2）课上实现并验证解决方案；（3）课后提交实验报告和源代码。PC机Java编译环境4集中实验（3）实验四图（综合型）利用图结构表示并存储现实世界（1）掌握图的存储结构；（2）掌握图的最短路径算法的实现。（1）课前设计解决方案；（2）课上实现并验证解决方案；（3）课后提交实验报告和源代码。PC机Java编译环境4集中实验(3)实验五信息管理系统的设计与实现（综合型）（1）综合运用所学数据结构、查（1）课前设计解决方案；（2）课上实现并验证解决方案；（3）课后提交实验报告和源代码。PC机Java编译环境4集中实验（4）五、课程考核内容及方式单项课程目标考试平均分 单项课程目标实验平均分单项课程目标达成值= 权重+ 权重单项课程目标考试总分 单项课程目标实验总分单项课程目标其他平均分+ 权重单项课程目标其他总分序号课程目标支撑毕业要求观测点考核评价方式及权重（%）期末考试形成性考核合计实验作业测验课堂互动1求精、追求卓越的工匠精神。1.350\20201010022.160\25151003（3）能够在工程实践中选择、构建合适的数据结构描述复杂软件工程问题中的数据及数据之间的关系，体现科学思维能力；，2.2602020\\1004有积极进取、追求卓越的创新意识。3.2602020\\100成绩评定方法考核方式期末考试形成性考核合计实验作业测验考核方式期末考试形成性考核合计实验作业测验课堂互动成绩比例60%20%8%4%8%100%评价标准以课程目标为考核标准。（1）课程考试考核标准依据课程目标拟定试题、制订试卷评分标准，详见试卷评分标准与参考答案。（2）实验、作业考核标准分值课程目标评价标准90-10080-9070-8060-700-59数据结构与算法数据结构与算法数据结构与算法数据结构与算法数据结构与算法基本概念的理解基本概念的理解基本概念的理解基本概念的理解基本概念的理解较好，常用数据结正确，正确掌握常基本正确，基本基本正确，基本基本正确，常用构的掌握较好，能用数据结构，算法掌握常用数据结掌握常用数据结数据结构未能掌对算法的时间和的时间和空间效构，算法的时间构，能进行简单握，算法的时间目标（1）空间效率进行深率分析正确，具有和空间效率分析的算法时间和空和空间效率分析入分析，具有很强较强的综合分析基本正确，具有间效率分析，具错误较多。规范的综合分析问题问题能力。规范意较好的综合分析有一定的综合分意识和社会责任能力。规范意识识强，在工程活动问题能力。具有析能力。正确理差。强，在工程活动中中落实科技人才规范意识，科技解规范意识和社落实科技人才的的社会责任。人才的社会责会责任。社会责任。任。应用常用查找、排应用常用查找、应用常用查找、排序算法对复杂问题的分析基本正确，问题解决基本正确。能利用规律解决实际问题。应用常用查找、排序算法对复杂问题的分析错误较多，问题未能正确解决。不能掌握利用规律解决实际问题。应用常用查找、排序算法对复杂问排序算法对复杂序算法对复杂问题的分析基本全问题的分析正题的分析全面、正面、正确，选用的确，选用的算法目标（2）确，选用的算法恰算法基本恰当，问基本恰当，问题当，问题解决正题解决基本正确。解决基本正确。确。能发现认识规能发现认识规律，能发现认识事物律，熟练掌握利用较好地掌握利用的基本规律，利规律。规律解决实际问用规律解决实际题。问题。应用栈、串、特殊图等数据结构对复杂问题的数据对象分析、抽象、归方法及数据结构基本操作描述复杂问题的解决强的辩证分析问题能力。应用栈、串、特能应用栈、串、应用栈、串、特特殊矩阵、广义图等数据结构对树、图等数据结表、树、图等数树、图等数据结复杂问题的数据构对复杂问题的据结构对复杂问构对复杂问题的对象分析、抽象、数据对象分析、题的数据对象进数据对象分析、建模较好，应用递抽象、建模基本行简单分析、抽抽象、建模错误目标（3）归方法及数据结正确，应用递归象、建模，应用较多，应用递归构基本操作描述方法及数据结构递归方法及数据方法及数据结构复杂问题的解决基本操作描述复结构基本操作描基本操作描述复方法较好。能全方杂问题的解决方述复杂问题的解杂问题的解决方位、多角度考虑问法正确。具有一决方法基本正法错误较多，不题，辩证分析问题定的辩证分析问确。辩证分析问具备辩证分析问的能力强。题能力。题的能力较弱。题的能力。目标（4）综合应用线性表、二叉树、图、经典算法及其他专业知识处理数据较好，算法的设计和分析较好，具有较强的创新意识和综合应用线性表、二叉树、图、经典算法及其他专业知识处理数据较好，算法的设计和分析正确，具有一定的钻研精神和创新意识。综合应用线性表、二叉树、图、经典算法及其他专业知识处理数据正确，算法的设计和分析基本正确，有创新意识。综合应用线性表、二叉树、图、经典算法及其他专业知识处理数据基本正确，算法的设计和分析基本正确，具有创新意识。综合应用线性新意识。（3）测验、期中考试、课堂练习考核标准分值课程目标评价标准90-10080-9070-8060-700-59能够熟练编写数能够熟练编写数能够正确编写数能够在他人的帮不能正确编写据结构中各种数据结构中各种数据结构中各种数助下编写数据结数据结构中各据类型的基本操据类型的基本操据类型的基本操构中各种数据类种数据类型的作，灵活应用数作，熟练应用数据作，应用数据结型的基本操作，基本操作，不能据结构基本运算结构基本运算解构基本运算解决应用数据结构基应用数据结构解决一些实际问决一些实际问题，一些实际问题，本运算解决一些基本运算解决目标（1）题，并充分利用并充分利用测验并充分利用测验实际问题，并充一些实际问题，测验的重复提交的重复提交功能，分利用测验的重不能完成考核强化练习，匠心精能，强化练习，复提交功能，强任务。匠心精技，提升技，提升相关知识匠心精技，提升化练习，匠心精相关知识的掌握的掌握水平，体现相关知识的掌握技，提升相关知水平，匠心精技水平，体现匠心识的掌握水平，意识强。精神。体现匠心精神。能熟练掌握查找、能掌握查找、排能掌握查找、排不能掌握查找、找、排序算法，排序算法，设计高序算法，设计高序算法，在他人排序算法，不能灵活设计高效的效的查找、排序算效的查找、排序的帮助下设计高设计高效的查查找、排序算法法解决复杂问题。算法解决复杂问效的查找、排序找、排序算法解目标（2）解决复杂问题。能发现认识规律，题。能发现认识算法解决复杂问决复杂问题。较熟练掌握利用规律，掌握利用题。能发现认识律，熟练掌握利规律。规律。规律，掌握利用用规律。规律。六、教材和参考书[1]陈锐,马军霞.数据结构（Java语言实现）(第2版)[M].北京:清华大学出版社.2023.[2]严蔚敏,吴伟民.数据结构C语言版[M].北京:清华大学出版社.2012.[3]MarkAllen.C(2版).:.2019.[4]陈越.数据结构(第2版)[M].北京:高等教育出版社.2016.[5]王争.数据结构与算法之美[M].北京:人民邮电出版社.