《数据结构》课程教学大纲

《数据结构》教学大纲课程名称：数据结构英文名称：Datastructure课程编号：2131学分：3总学时/课内实践学时：56/8课程性质：必修课程开课单位：信息与电气工程学院软件工程系适应对象：数据科学与大数据技术课程简介“数据结构”是数据科学与大数据专业的核心必修课，是学生进一步深入学习和开展高层次研究的基础。通过本课程的讲授，使学生掌握数据结构的基本理论知识和几种常用的数据结构算法的设计与分析，培养学生分析和解决复杂问题的能力，并为其开展科学研究奠定数据结构与算法方面的基础。本课程采用课堂讲授与项目驱动相结合的教学模式。将过程性评价和终结性评价相结合，构建按（知识点）分阶段、多元化课程考核体系。课程教学过程中将通过项目引导、课堂导向式教学，递进式算法教学等教学方式，同时构建课程的思政体系，以“提高素质、培养能力”的人才原则，达到培养具有能够运用所学知识分析和解决实际复杂工程问题，具备职业竞争力的高素质复合型应用人才目标。课程目标目标1：结合具体算法应用项目，能够选择合适的数据结构并设计出结构清晰、正确高效的算法，注重科学思维方法训练，培养严谨的科学态度和精益求精的工匠精神。目标2：能通过几种基本数据结构的算法分析能发现问题解决过程中的影响因素，能够借助文献研究针对具体问题获得有效结论。目标3：能够综合运用所学的数据结构、算法分析等知识，针对实际工程中的具体问题设计合理的技术路线或实验方案。三、课程目标与毕业要求对应关系本课程的课程目标对数据科学与大数据专业毕业要求指标点的支撑情况如表1所示：表1课程目标与毕业要求对应关系毕业要求指标点课程目标2.问题分析能力：掌握统计与机器学习的基本方法，能够综合运用数学、自然科学和数据科学的基本原理，对复杂的工程系统，识别问题、描述问题并通过文献研究分析与大数据相关的工程问题，以获得有效结论。2-2能够基于数据科学相关科学原理和数学模型方法正确表达大数据应用领域的复杂工程问题；教学目标12-4能运用数据科学与大数据技术的基本原理，借助文献研究，分析过程的影响因素，获得有效结论。教学目标24.工程技术研究能力：能够基于数据科学与大数据技术原理并采用科学方法对大数据应用领域的复杂工程问题进行研究，包括设计实验、分析与解释数据、并通过信息综合得到合理有效的结论。4-3能够对采集到的实验数据进行整理、分析和解释，并能通过信息综合、算法设计得出有效结论。教学目标3课程教学安排逻辑结构逻辑结构线性结构(线性表、栈、队列、串、数组)运算存储结构树型结构(二叉树、树、森林)图型结构(有向图、无向图、有向网、无向网)集合结构(文件)插入与删除操作排序操作(希尔、快速、堆、基数排序)查找操作(顺序、二叉树、查找树、哈希查找)索引操作(二叉树、B+树)顺序存储链式存储索引存储散列存储抽象数据类型ADT算法分析、性能优化课程共有9项教学内容，具体安排如下。表2：课程教学安排表序号教学内容思政元素课堂教学学时实验教学学时学时小计1绪论建设世界科技强国的时代使命感222线性表82103数组和字符串444栈和队列加强同学们的遵守公共秩序的美好品德6285树和二叉树培养家国情怀，对自己国家一种高度认同感和归属感、责任感和使命感。82126图82127查找树立正确的人生观和价值观688排序469总复习22合计48856第1章绪论（支撑教学目标1、2）教学要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。重点：数据、数据元素、数据逻辑结构、数据存储结构和数据结构的定义，算法的定义以及5个特征，算法描述语言（ADL），时间复杂性分析方法，复杂性函数的渐进表示。难点：数据逻辑结构和存储结构的定义以及区别，算法时间复杂性分析方法以及复杂性函数的渐进表示。思政元素：通过学生查找算法应用案例资料，让学生逐步认识我国当前计算机领域面临的“卡脖子”难题，引导学生将自我价值实现与服务国家重大战略需求、建设世界科技强国的时代使命结合，为民族复兴贡献力量。教学内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表现与实现1.4算法和算法分析第2章线性表（支撑教学目标1、2、3）教学要求：理解线性表的定义和特点；掌握顺序表和链表的特点，掌握在这两种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这两种存储结构上进行算法设计的方法，以达到利用基本算法进行较复杂算法设计的目的。重点：顺序存储线性表的定义及基本操作，单链表的定义及基本操作，双向链表的定义及基本操作。难点：双向链表的插入删除操作。思政元素:在讲解链表创建的代码时，培养学生准确的表达能力、严谨的科学态度和精益求精的工匠精神。教学内容：2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4线性表的应用第3章栈和队列（支撑教学目标1、2、3）教学目标：理解栈和队列的定义、特点，学习它们的各种组织方式及算法；掌握它们的空和满的判断条件；并学会它们的实际应用。通过编译器变异机制、网页浏览器访问机制、文本编辑器编辑操作的历史记录功能、计算机及其网络自身内部的各种计算资源管理等高阶应用实例培养学生的创新思维能力。重点：栈的定义、基本操作及应用，队列的定义、基本操作及应用。难点：栈的基本操作，栈的应用，循环队列操作。教学内容：3.1栈3.2栈与递归3.3队列第4章数组和字符串（支撑教学目标1、2）教学要求：了解串的定义，理解和领会串的存储方式、串的模式匹配算法，掌握常用的串运算。通过字符串匹配算法改进，引导学生掌握科学的思维方法，提高科学思维能力和创新思维能力。重点：二维和多维数组的寻址方式，矩阵的存储和基本操作，字符串的存储和基本操作、模式匹配方法。难点：KMP模式匹配方法。教学内容：4.1串的定义4.2串的存储结构及其运算4.3数组4.4广义表第5章树和二叉树（支撑教学目1、2、3）教学要求：理解树型结构的概念和术语，领会二叉树的定义、形态、性质和存储结构，掌握二叉树的各种遍历算法极其实现过程，了解树和森林及其相互转换；掌握哈夫曼树及其应用。思政元素：通过家族族谱设计和实现，让学生认识到个人命运和家族沉浮与国家命运患难相系、休戚与共，培养学生的家国情怀，对自己国家一种高度认同感和归属感、责任感和使命感。重点：二叉树的性质、存储结构，二叉树的三种遍历算法，哈夫曼树和哈夫曼编码。难点：哈夫曼树和哈夫曼编码。教学内容：5.1树的定义和基本术语5.2二叉树5.3遍历二叉树5.4线索二叉树5.5树和森林5.6赫夫曼树及其应用第6章图（支撑教学目标1、2、3）教学要求：理解图型结构的概念和术语，掌握图的邻接矩阵和邻接表两种存储形式，理解图的遍历的基本思想，掌握图的两种遍历的方法和其实现的过程，学会图结构在最小生成树、拓扑排序、关键路径中的应用。通过初阶、中阶和高阶案例应用，强调创新思维的系统性和实践性，鼓励运用创新思维应对新挑战，提升学生复杂问题的分析与解决能力。重点：图的定义、术语及其含义、图的存储结构、图的遍历算法、最小生成树、拓扑序列、关键路径、最短路径。难点：图的遍历算法、最小生成树、拓扑序列、关键路径、最短路径算法。教学内容：6.1图的定义和术语6.2图的存储结构6.3图的遍历6.4图的应用第7章查找（支撑教学目标2、3）教学目标：查找表是集合类型的数据结构，其操作借助静态查找表、动态查找表、哈希表实现。理解静态查找表的概念、掌握顺序查找和折半查找算法及其实现方法、理解顺序查找和折半查找的特点，学会分析算法的性能；理解动态查找表和二叉排序树的概念、掌握二叉排序树的构造算法及其实现方法、掌握二叉排序树的查找算法及其实现方法；掌握哈希表的概念作用及意义，哈希表的构造方法。思政元素：通过哈希表的算法在信息科学的前沿、网络技术中信息交流安全验证、操作系统密钥原理，尤其是黑客技术的应用，培养学生树立正确的人生观和价值观。重点：查找表的基本概念、静态查找表的算法及实现、二叉排序树的定义、性质，二叉排序树的查找算法、平衡二叉树、散列表的概念、散列表的组织、解决冲突的方法。难点：二叉排序树的查找算法、平衡二叉树、散列表的概念、散列表的组织、解决冲突的方法。教学内容：7.1线性表查找7.2树表查找7.3散列表查找第8章内部排序（支撑教学目标2、3）教学要求：理解排序的基本概念和性能分析方法。掌握：插入排序（直接插入排序；折半插入排序；链表插入排序）、交换排序（起泡排序；快速排序）、选择排序（直接选择排序；链表选择排序；锦标赛排序；堆排序）、归并排序等内排序的方法、算法及其性能分析方法。思政元素：通过几种排序算法在大规模数据集并行运算中的应用，引导学生要学会运用科学、辩证的观点和思想全面观察事物和分析问题。重点：排序基本概念、插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序。难点：快速排序、堆排序、归并排序。教学内容：8.1概述8.2插入排序8.3交换排序8.4选择排序8.5归并排序课内实践教学内容及要求本课程共有8个实验项目，所有实践教学类型为上机操作。实验一：线性表相关项目（支撑教学目标：1、2、3）实验目标：通过线性表的项目使学生掌握顺序表及其基本操作的实现，以及链表及其基本操作的实现；具备能够采用顺序存储和链接存储等数据的基本存储方式来处理数据在计算机中的存储能力。培养学生准确的表达能力、严谨的科学态度和精益求精的工匠精神。实验要求：掌握顺序表的创建以及相关的基本操作；单链表(带头结点、不带头结点)、双向链表的创建及其相关的基本操作。实验过程：(1)编写实现顺序表初始化、查询、插入、删除等操作的程序。(2)编写实现单链表初始化、建立、求长度、查询、插入、删除等操作的程序。(3)编写实现双向链表初始化、建立、求长度、查询、插入、删除等操作的程序。(4)实现项目1：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。(5)实现项目2：利用单向循环链表和双向循环链表分别实现约瑟夫生死游戏。实验二：二叉树相关项目（支撑教学目标：1、2、3）实验目标：通过二叉树的项目使学生掌握二叉树的链式存储结构及其相关操作的实现；掌握二叉树的先序、中序、后序的递归遍历算法；理解二叉树的各种非递归遍历算法的实现。通过家族族谱管理项目、哈夫曼编码的代码设计和实现，提升二叉树知识的工程应用能力。实验要求：掌握二叉树的基本概念，以及二叉树的基本操作；重点掌握二叉树的前、中和后序遍历，以及二叉树的线索化等算法；掌握赫夫曼树的含义及其应用。实验过程：(1)编写程序实现二叉树的前、中和后序遍历的算法。(2)编写程序实现二叉树的线索化算法。(3)编写程序实现哈夫曼树的构造算法和字符编码输出。(4)实现项目1：利用二叉树实现家族族谱管理（数据录入、查找等）。(5)实现项目2：实现学校的数据统计：文件中给出学校组织机构内容，根据文件内容创建树结构，输出所有学院，每个学院的所有专业，每个专业的学生人数等。实验三：图相关项目（支撑教学目标：1、2、3）实验目标：通过对图的一些基本操作的项目使学生掌握图的深度优先遍历和广度优先遍历算法；掌握图的的拓扑排序、关键路径和最短路径等算法的实现过程。具备运用图的基本算法解决实际工程问题的能力。通过深入分析和实现项目，加强对学生创新思维的系统性和实践性培养，提升学生复杂问题的分析与解决能力。实验要求：图的深度优先遍历和广度优先遍历算法的实现；图的拓扑排序、关键路径和最短路径算法的实现。实验过程：(1)选择合适的图的存储方式编写程序实现图的深度优先遍历和广度优先遍历算法。(2)编写程序实现图的拓扑排序算法。(3)编写程序实现图的关键路径算法。(4)编写程序实现图的最短路径算法。(5)实现项目1：“六度空间”理论：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。首先，需要如何验证这个理论的正确性？其次，采用哪种图结构算法实现理论的验证？(6)实现项目2：出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。实验四：查找相关项目（支撑教学目标：1、2、3）实验目标：通过对不同查找方法的项目使学生掌握顺序查找与折半（二分法）查找算法；掌握二叉排序树的创建及查找算法的实现；掌握哈希表的造表及在哈希表中查找算法的实现。具备依据不同问题选择不同查找方法处理实际问题的能力。实验要求：顺序查找与折半（二分法）查找算法；二叉排序树的创建及查找算法的实现；哈希表的造表及在哈希表中查找算法的实现。实验过程：(1)用递归调用形式编写折半查找算法程序。(2)编写读入一串整数构成一棵二叉排序树的算法，并且对其做一些相关的查找。(3)编写实现哈希表的造表及在哈希表中查找的算法实验五排序相关项目（支撑教学目标：1、2、3）实验目标：通过对不同排序算法的项目使学生掌握交换排序（冒泡排序、快速排序）算法的实现方法；掌握选择排序（堆排序）算法的实现方法。具备依据不同问题选择较为合适的排序方法来解决实际问题的能力。实验要求：冒泡排序、快速排序和堆排序算法的实现。实验过程：编写程序实现冒泡排序、快速排序和堆排序等算法。课程考核与评价1.课程考核方式本课程的总成绩为100分，由平时作业及课堂练习、上机实验和期末考核3部分组成，平时考核占总成绩的20%，上机考核占总成绩的15%，期末考核占总成绩的65%。平时作业及课堂练习100分，贯穿整个学习期间，考核内容包括章节知识点掌握情况，特别是涉及不易在限定时间内完成的作业，需要查阅相关资料，需要考虑非技术因素，需要考虑对问题的分析与建模能力的内容。上机