数据结构-56学时-教学大纲-面向计算机专业

数据结构DataStructures课程编号：XXX学分：XXX开课学院：XXX学时：56适用专业：XXX先修课程：高等数学，高级语言程序设计课程类别：专业基础课课程性质：必修/限选一、课程性质数据结构是高等工科院校“信息管理与信息系统”、“大数据管理与应用”、“电子商务”等相关专业的一门重要的必修专业基础课。二、课程目标（一）课程目标通过本课程学习，使学生掌握分析数据元素的组成和逻辑关系的能力；能够综合运用数据结构的基本理论和设计方法，研究针对计算机及应用领域复杂工程问题自主设计数据结构，实现运算效率的提高，并能通过实验对研究方案的可行性进行论证，增强程序开发能力；培养学生具备自主学习的能力，主动挖掘数据结构背后隐含的算法设计思想并扩展相关前沿技术知识，传播正确的核心价值观，激发学生报效祖国的爱国热情。具体课程目标如下：课程目标1：培养学生分析计算机应用领域复杂工程问题的能力，强化抽象思维与逻辑分析能力。课程目标2：能够针对复杂工程问题，运用计算思维分析数据组成和逻辑关系，选用合适的数据存储结构，设计高效的算法和可行的解决方案。课程目标3：能综合运用数据结构知识和算法分析方法，使用定性和定量分析方法进行数据分析与处理，设计实验方案并正确实施，对解决方案的可行性进行验证。（二）课程目标对毕业要求指标点的支撑关系课程教学目标所支撑的毕业要求具体的毕业要求指标点内容课程目标11、工程知识掌握计算机软硬件相关工程基础知识，建立数学模型，能将其用于分析计算机及应用领域的相关工程问题。课程目标23、设计/开发解决方案能够在专业相关系统中合理的组织数据、有效存储和处理数据，能够根据用户需求，选取适当的研究方法和技术手段，确定复杂工程问题的解决方案。课程目标34、研究能够根据实验方案，配置实验环境、开展实验，使用定性或定量分析方法进行数据分析与处理，综合实验结果以获得合理有效的结论。三、课程教学内容及基本要求本课程教学内容包括：线性表、栈和队列、数组、树和二叉树、集合、搜索树、散列表、图等常见的数据结构，讨论各种典型搜索和排序算法。此外，还介绍算法分析的基本方法。本课程基本要求是：从数据的逻辑结构、存储结构和运算三个方面理解并掌握线性表、栈、队列、数组、树和图等常用的数据结构；了解在各种常用的数据结构上实现的排序和查找运算；对算法的时间和空间复杂度有一定的分析能力；针对常见的应用问题，能选择合适的数据结构及设计有效的算法解决问题。（一）课程教学内容及知识模块顺序1.知识单元一：基础知识（3学时）（1）知识点一：算法与数据结构（2）知识点二：什么是数据结构（3）知识点三：数据抽象和抽象数据类型（4）知识点四：描述数据结构和算法（5）知识点五：算法分析的基本方法教学基本要求：了解课程的学习目的和内容，深刻理解有关数据结构的基本概念，理解将抽象数据类型应用于数据结构研究的方法，掌握算法分析的基本方法。对课程目标支撑的说明：本知识单元支撑课程目标1、课程目标32.知识单元二：线性表（6学时）（1）知识点一：线性表ADT（2）知识点二：线性表的顺序表示（3）知识点三：线性表的链接表示（4）知识点四：多项式的算术运算教学基本要求：深刻理解线性表抽象数据类型以及线性表的顺序和链接表示方法，熟练掌握线性表中基本运算的实现算法，学会分析各算法的性能，以及学会使用线性表求解一元多项式的算术运算。对课程目标支撑的说明：本知识单元支撑课程目标1、课程目标23.知识单元三：栈和队列（4学时）（1）知识点一：栈（2）知识点二：队列（3）知识点三：表达式计算（4）知识点四：递归教学基本要求：深刻理解栈和队列抽象数据类型以及它们的顺序和链接表示方法，熟练掌握栈和队列数据结构中基本运算的实现算法，掌握如何借助栈进行后缀表达式计算、理解其实现方法，了解递归的基本概念及递归调用的方法。对课程目标支撑的说明：本知识单元支撑课程目标14.知识单元四：数组（4学时）（1）知识点一：数组（2）知识点二：特殊矩阵（3）知识点三：稀疏矩阵教学基本要求：理解数组抽象数据类型，掌握一般数组的顺序表示方法以及对称矩阵的存储方式，理解稀疏矩阵的含义，掌握稀疏矩阵的三元组表示方法，了解利用三元组表示法的矩阵快速转置算法。对课程目标支撑的说明：本知识单元支撑课程目标1、课程目标25.知识单元五：树（10学时）（1）知识点一：树的基本概念（2）知识点二：二叉树（3）知识点三：二叉树的遍历（4）知识点四：树和森林（5）知识点五：堆和优先权队列（6）知识点六：哈夫曼树和哈夫曼编码教学基本要求：了解树和森林的基本概念及主要存储方式，深刻理解二叉树的定义、性质和二叉链表存储结构，熟练掌握二叉树遍历的三种递归算法，学会利用二叉树遍历求解其它相关问题，掌握森林与二叉树的转换方法，了解堆和优先权队列数据结构，掌握建堆算法，了解在优先权队列中插入、删除元素的方法，理解哈夫曼树构造方法，学会哈夫曼编码和译码的方法。对课程目标支撑的说明：本知识单元支撑课程目标1、课程目标2、课程目标36.知识单元六：集合（2学时）（1）知识点一：基本概念（2）知识点二：顺序搜索（3）知识点三：二分搜索教学基本要求：理解集合的基本概念，熟练掌握在集合中相关的搜索算法，具体包括有序表的顺序搜索、对半搜索的递归和非递归算法，了解使用二叉判定树进行二分搜索平均时间复杂度的方法。对课程目标支撑的说明：本知识单元支撑课程目标1、课程目标27.知识单元七：搜索树（5学时）（1）知识点一：二叉搜索树（2）知识点二：二叉平衡树（3）知识点三：B−树教学基本要求：深刻理解二叉搜索树的定义和性质，熟练掌握二叉搜索树中搜索、插入和删除元素的算法，了解二叉平衡树定义以及在二叉平衡树中插入元素的平衡旋转方法，掌握B-树的定义以及在B-树中插入和删除元素的方法。对课程目标支撑的说明：本知识单元支撑课程目标28.知识单元八：散列表（3学时）（1）知识点一：散列表教学基本要求：掌握散列表的概念，了解常见的散列函数，掌握解决冲突的拉链法和开地址法。对课程目标支撑的说明：本知识单元支撑课程目标2、课程目标39.知识单元九：图（10学时）（1）知识点一：图的基本概念（2）知识点二：图的存储结构（3）知识点三：图的遍历（4）知识点四：拓扑排序（5）知识点五：关键路径（6）知识点六：最小代价生成树（7）知识点七：单源最短路径教学基本要求：深刻理解图的基本概念，熟练掌握图的邻接矩阵和邻接表存储结构，理解图中一些常见的算法：图的深度优先和广度优先遍历算法，拓扑排序和关键路径算法，求最小代价生成树的普里姆和克鲁斯卡尔算法，以及求单源最短路径。对课程目标支撑的说明：本知识单元支撑课程目标1、课程目标2、课程目标310.知识单元十：排序（9学时）（1）知识点一：内排序基本概念（2）知识点二：简单排序算法（3）知识点三：快速排序（4）知识点四：两路合并排序（5）知识点五：堆排序教学基本要求：熟练掌握各种常见的内排序算法，学会分析和比较各种内排序算法的时间和空间复杂度，理解这些算法的异同，学会针对实际排序问题，选择合适的排序算法。对课程目标支撑的说明：本知识单元支撑课程目标2、课程目标3（二）课程的重点、难点及解决办法课程重点：理解各种数据结构所表达的数据间的关系以及对各种数据结构的灵活应用课程难点：针对实际应用问题，选择合适的数据结构、设计并实现有效的算法解决问题；解决的办法：首先在教学过程中，注重突出重点和难度，以基础为主，理解各类逻辑结构的内涵；重视并强化上机实践教学环节，通过编程实践加强学生对各类数据结构存储表示与运算的掌握，并进一步地理解逻辑结构、存储结构与运算结构之间的关系。其次，充分利用现有的资源共享课网站和在线课程网站，为学生提供更多种类的自学途径和学习资源，并安排教师定期维护课程论坛，解答学生问题；通过建设课程QQ群或微信群，与学生进行实时在线答疑；以上网络资源与在线互动可以作为课堂教学的有效补充。最后，编制与课程配套的课件、复习要点、例题分析、习题与思考，以组合方式提供给学生，使学生能发挥学习的自主性、启发性以及研究性，思考题引导学生如何深入进行研究。再针对难点问题，加强与学生的互动环节，加深学生对难点的掌握。（三）实验实践环节及基本要求1．实验实践教学环节在本课程中的作用及要求。通过上机实践，一方面使学生加深对课内所学各种数据逻辑结构、存储表示和运算基本内容的理解，学习如何运用所学的数据结构和算法知识处理应用问题的方法；另一方面，在程序设计方法、C语言编程环境以及程序的调试和测试等方面得到必要的训练。上机实践教学环节要求学生能设计结构清晰的算法和程序，学习分析所设计算法的时间和空间复杂度，选择足够的测试用例进行测试，实验结束后认真完成实验报告，整理所编写源程序代码和可执行程序，递交实验报告和程序。2．实验项目与课程目标对应关系(具体要求见实验教学大纲)实验项目学时课程目标实验一：线性表的基本运算及多项式的算术运算2课程目标1、2实验二：二叉树的基本操作及哈夫曼编码译码系统的实现2课程目标2、3实验三：图的基本运算及智能交通中的最佳路径选择问题2课程目标2、3实验四：各种内排序算法的实现及性能比较2课程目标2、3（四）课程思政教学设计教学内容思政目标思政素材融入方式评价方法基础知识爱国情怀、奉献精神、科学精神介绍各类数据结构演变历史，强调其在算法设计方面的重要性，对比国内外研究现状，表明我国在经典数据结构和算法研究方面的不足，激发学生的爱国情怀，努力学习，追赶不足。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论论坛发言问卷调查学习报告线性表科学精神、科学发展观、团队协作通过顺序存储和链接存储，建立计算机的时空交换的概念，促进学生树立正确的科学发展观。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论小组合作游戏论坛发言问卷调查学习报告栈和队列科学精神、传统文化、科学发展观循序渐进地讲授重点，在讲授递归知识时融合分而治之、合而驭之等解决问题的算法思想，促进学生树立正确的科学发展观。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论小组合作游戏论坛发言问卷调查学习报告数组绿色计算、尊重知识产权、抵制盗版介绍各种压缩存储和提高效率的算法设计思想，向学生灌输绿色计算思想；介绍各种压缩软件，强调知识产权，抵制盗版软件。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论论坛发言问卷调查学习报告树爱国情怀、奉献精神、科学精神介绍哈夫曼的科学家精神。由哈夫曼编码引出加密算法的思想，进而介绍我国信息安全领域加密算法研究现状、不足，激发学生奋发向上，努力赶超先进水平。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论小组合作游戏论坛发言问卷调查学习报告集合爱国情怀、奉献精神、科学精神、团队协作介绍搜索算法在搜索引擎设计方面的重要性，对比Baidu和Google现状，表明我国搜索引擎开发方面的优势与不足，激发学生积极向上的学习热情。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论小组合作游戏论坛发言问卷调查学习报告搜索树爱国情怀、奉献精神、科学精神、团队协作介绍搜索算法在搜索引擎设计方面的重要性，对比百度和Google现状，表明我国搜索引擎开发方面的优势与不足，激发学生积极向上的学习热情。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论论坛发言问卷调查学习报告散列表爱国情怀、奉献精神、科学精神、团队协作介绍搜索算法在搜索引擎设计方面的重要性，对比Baidu和Google现状，表明我国搜索引擎开发方面的优势与不足，激发学生积极向上的学习热情。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论论坛发言问卷调查学习报告图爱国情怀、奉献精神、科学精神、团队协作介绍图算法对导航等应用的重要性，对比目前几大导航应用，促进学生学习热情和爱国情怀。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论论坛发言问卷调查学习报告排序爱国情怀、奉献精神、科学精神、团队协作介绍排序算法的发展历史，表明我国在排序算法方面原创不足，激发学生的学习热情与爱国情怀。线上拓展材料阅读线上观看拓展视频参与线上话题讨论课堂讲授分组讨论小组合作游戏论坛发言问卷调查学习报告四、教学方法在具体教学组织实施的过程中，建议但不限于使用以下的教学方法。讲授式教学：本课程教学以教师课堂讲授为主，辅以课前基于在线开放课程的线上自学和课后作业。在授课过程中应灵活运用板书和多媒体教学，同时在课前、课中和课后通过使用慕课堂等智慧教学工具加强师生互动。研讨式教学：根据具体教学内容适当开展研讨活动。由教师提供研讨问题，同学以小组为单位进行课前准备，此后进行课上研讨，从而提高同学们的团队协作能力。启发式教学：针对重要知识点采用提出问题、分析问题、解决问题的思路进行授课，潜移默化地培养学生的相应能力；课中结合强调实践经验的重要性，在实践中学习。案例式教学：针对最短路径、哈夫曼编码、最小代价生成树等内容，列举实际工程案例，通过适时、适度地提问引出案例，再组织学生思考、讨论和总结，最后教师讲评、总结。游戏式教学：针对搜索算法、排序算法、二叉平衡树、堆栈与队列等内容，设计小组合作游戏，同学以小组为单位在课堂中完成，从而加深同学们对抽象的知识点的理解以及团队协作能力。五、课程教学内容、学时分配、教学方法与课程目标对应关系本课程总学时56，线下课堂讲课48学时，实验8学时。课程主要内容和学时分配见下表。教学内容学时分配教学方法课程目标讲课实验上机线上课外基础知识3讲授式教学、类比教学、启发式教学课程目标1课程目标3线性表42讲授式教学、类比教学、启发式教学课程目标1课程目标2栈和队列4讲授式教学、类比教学、游戏式教学、启发式教学课程目标1数组4讲授式教学、类比教学、启发式教学课程目标1课程目标2树82讲授式教学、类比教学、游戏式教学、启发式教学课程目标1课程目标2课程目标3集合2讲授式教学、类比教学、游戏式教学、启发式教学课程目标1课程目标2搜索树5讲授式教学、类比教学、启发式教学课程目标2散列表3讲授式教学、类比教学、启发式教学课程目标2课程目标3图82讲授式教学、类比教学、启发式教学课程目标1课程目标2课程目标3排序72讲授式教学、类比教学、游戏式教学、启发式教学课程目标2课程目标3总计488六、本课程与其它课程的联系与分工学习该课程前应该具备基本的编程语言和程序设计知识，例如C语言。还应该具备高等数学计算和推导能力，例如进行时间复杂度分析需要用到等差数列和等比级数的知识。这些内容在本课程的先修课程“高级语言程序设计”和“高等数学”中已经学习过。通过本课程的学习，学生能够综合运用数据结构的基本理论和设计方法，针对计算机及应用领域复杂工程问题自主设计数据结构，具备基本算法设计能力，为后续“操作系统”和“算法分析与设计”等专业课程的学习奠定坚实的理论和实践基础。七、教材、教学参考资料和网络资源（一）教材[1]数据结构（C语言）（二）主要参考书（三）网络资源八、课程考核（一）课程成绩构成与要求本课程采用过程性评价与终结性评价相结合，平时成绩在总评成绩占比中，不低于40%，期末卷面成绩在总评成绩占比中，不高于60%。在教学过程中，应加强过程性评价，每次评价的形式和内容要围绕课程目标开展。九、说明（一）课程目标达成情况评价本课程的课程目标达成情况评价可以采用问卷调查（学生自评）、成绩分析（过程性评价和期末终结性评价相结合）、专家（同行）评价等多种方法进行。教师可以选择其中的一种方法或者多种方法在每学期期末完成，采用多种方法时，建议对各种方法的评价结果进行对比分析，并随考试试卷等材料上交存档。以成绩分析法为例，下面给出课程目标的评价过程，鼓励教师采用多样化的评价方式。课程目标的达成情况按照平时成绩和期末考试卷面成绩来综合评价，具体要求见表1。本课程平时成绩组成中，有40分考查了课程目标1的达成情况，40分考查了课程目标2的达成情况，20分考查了课程目标3的达成情况（以上均为建议值，任课教师可以根据实际情况稍作调整）；期末试卷中，考查课程目标1-3的题目所占分值按照实际情况填写（建议考查课程目标1-2的试题所占分值更高）。附表1课程目标达成评价表教学目标平时成绩卷面成绩总评价值满分值绝对值评价值满分值绝对值评价值课程目标140课程目标240课程目标320合计100×100××附表1说明：1、课程目标对应的平时