数据结构与算法（Python版）第2版 教学大纲

PAGEPAGE14《数据结构与算法（第二版）》教学大纲课程名称：数据结构与算法（Python版）适用专业：计算机科学与技术、软件工程、大数据等信息专业先修课程：计算机导论、离散数学、Python程序设计语言总学时：90授课学时：42实验学时：48一、课程简介数据结构是计算机科学与技术专业的核心课程之一，主要研究数据的逻辑结构、存储结构以及在其上的操作算法。通过本课程的学习，学生能够掌握数据组织、存储和处理的基本方法，培养分析问题和解决问题的能力，为后续的专业课程学习和软件开发实践奠定坚实基础。Python是一门开源的面向对象程序设计，拥有大量功能丰富的标准库和扩展库。通过本课程的学习，使学生掌握使用Python语言及其第三库实现数据结构中数据组织、存储和运算的基本原理和方法，培养学生对各类数据结构和相关算法的分析和设计的能力，使学生能够编写出正确、清晰的算法和程序。二、课程目标1.知识目标掌握基本数据结构（线性表、栈、队列、串、二叉树、图论、查找、排序等）的定义、特性及存储方式。理解常用算法（如排序、查找等）的实现原理及性能分析。了解数据结构在程序设计中的应用。2.能力目标能够根据实际问题选择合适的数据结构进行数据组织和存储。具备设计和实现数据结构相关算法的能力。能够运用所学数据结构知识解决简单的实际问题。3.素质目标培养学生的逻辑思维能力和抽象思维能力。提高学生的程序设计能力和代码实现能力。培养学生分析问题和解决问题的能力。三、本课程与其它课程的联系本课程的先修课是离散数学、Python程序设计语言。Python程序设计语言为本课程提供实践工具，离散数学为本课程提供理论基础。本课程是操作系统、数据库、编译原理等软件专业课的重要基础；为这些后续课程分析问题时提供规范的思路以及良好的数据结构和算法。该课程学习完成后，“数据结构课程设计”的实践环节使得学生在掌握数据结构基本理论知识的基础上，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用，进一步提高分析问题和解决问题的能力，提高程序设计水平。四、课程内容及要求第1章数据结构与算法主要内容：1.数据结构的概念、内容；2.算法的概念、评价标准、描述方法、性能分析。基本要求：了解数据结构、算法的基本概念；了解数据结构的地位；了解各种算法描述方法和算法设计的基本要求；掌握对算法的评价标准和算法效率的度量方法。重点难点：逻辑结构和存储结构的区别，时间复杂度的分析和计算方法。第2章异常处理与调试主要内容：1.Python中异常处理结构2.断言与上下文管理基本要求：理解Python异常处理的结构；理解断言与上下文管理的含义。重点难点：异常处理结构及断言,自定义异常处理，调式工具。第3章线性表主要内容：1.线性表的逻辑结构定义、基本操作2.两种存储结构中基本操作的实现；基本要求：理解线性表的概念、定义、逻辑结构和存储结构；熟练掌握线性表的顺序存储结构及其各种基本运算；熟练掌握单链表等链式存储结构及其各种基本运算。重点难点：线性表的特征；顺序表、单链表的存储结构及其各种基本运算。顺序表和链表这两种存储表示方法的综合比较，静态链表的存储表示方法。第4章队列和栈主要内容：1.栈的应用。2.队列的应用。基本要求：栈和队列的特点、存储方式及基本操作；栈和队列的应用。重点难点：栈和队列的特点、存储方式及基本操作；栈和队列的应用。第5章串主要内容：1存储结构2基本操作 3正则表达式 4re模块 5模式匹配 基本要求：正则表达式、串的KMP模式匹配算法。重点难点：正则表达式、串的KMP模式匹配算法。第6章树与二叉树主要内容：1．树的概念；2．二叉树的定义、性质、存储结构；3．二叉树的遍历及基于遍历的应用；基本要求：理解树的基本概念及其存储结构；熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法；掌握线索二叉树的概念、存储结构及线索化算法。重点难点：二叉树的遍历算法及基于遍历的简单应用。第7章树与二叉树的应用主要内容：1哈夫曼树 2树的存储 3树与二叉树转换基本要求：掌握树和森林与二叉树间的转换，掌握哈夫曼树的概念、存储结构和应用。重点难点：树和森林与二叉树间的转换；哈夫曼树的概念、存储结构和应用哈夫曼树构造哈夫曼编码。第8章图论主要内容：1．图的基本概念；2．图的存储结构；3．图的遍历；基本要求：理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构；熟练掌握图的深度优先和广度优先遍历算法重点难点：图的邻接矩阵和邻接表的存储结构；图的深度优先遍历算法和广度优先遍历算法。理解图的关键路径算法第9章图的应用主要内容：1．理解图的连通性、最小生成树的概念2．掌握求最小生成树算法3．掌握求最短路径的算法。基本要求：；理解图的连通性、最小生成树的概念，掌握求最小生成树算法；掌握求最短路径的算法。理解图的连通性、最小生成树的概念，掌握求最小生成树算法；掌握求最短路径的算法。重点难点：图的最小生成树算法、图的求最短路径的Dijkstra算法、Floyd算法。利用图的重要算法解决实际具体问题。第10章查找主要内容：1．查找的概念以及效率的评价方法；2．基于线性表的查找——顺序查找、折半查找、索引查找；3．基于树的查找——二叉排序树；4．哈希查找法的概念和构造方法。基本要求：理解查找的概念及其效率的评价方法；理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法；理解动态查找表和二叉排序树的概念；了解平衡二叉树的概念，创建调整过程；理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法；重点难点：顺序、折半查找算法、二叉排序树的插入、删除和查找算法；了解平衡二叉树的概念，创建调整过程；哈希函数的构造和处理冲突的基本方法；查找成功和不成功时的平均查找长度计算方法。第11章排序主要内容：1．排序的概念以及排序算法的性能评价；2．插入类排序——直接插入排序、折半插入排序、希尔排序；3．交换类排序——冒泡排序、快速排序；4．选择类排序——简单选择排序、堆排序；5．归并类排序；基本要求：掌握插入类排序的算法：直接插入排序、希尔排序；掌握交换类排序的算法：冒泡排序、快速排序；掌握选择类排序的算法：简单选择排序、堆排序；了解归并排序思想重点难点：理解快速排序、堆排序、归并排序等排序算法的思想；掌握排序方法的平均时间复杂度、最坏时间复杂度和算法所需的辅助存储空间。第12章Scipy 主要内容：1邻接矩阵 2图的遍历 3最短路径 4图的连通分量 基本要求：掌握Scipy采用邻接矩阵存储图结构，其后介绍了图的遍历、深度优先搜索、广度优先搜索、最短路径和图的连通分量。重点难点：图的遍历、深度广度优先搜索、最短路径和图的连通分量。第13章Pandas主要内容：1Series2DataFrame 3Index4图的两种存储方式5节点度数 6图的遍历基本要求：掌握Pandas的基本数据类型：Series、DataFrame和Index。掌握如何实现图的两种存储方式（邻接矩阵和边列表），如何实现节点度数（有向图、加权图）重点难点：实现图的两种存储方式（邻接矩阵和边列表），如何实现节点度数（有向图、加权图）第14章NetworkX主要内容：1各类图 2节点 3边 4搜索 5图的连通性分析 6最短路径 基本要求：掌握各类图（无向图、有向图、多重图），节点、边的属性和操作，掌握深度广度优先搜索方法，掌握图的连通性的分析和判断，掌握无权图和加权图的最路路径的实现方法重点难点：掌握各类图（无向图、有向图、多重图），节点、边的属性和操作，掌握深度广度优先搜索方法，掌握图的连通性的分析和判断，掌握无权图和加权图的最路路径的实现方法。五、教学安排及学时分配教学环节及学时主要内容学时分配授课习题课实验网络其它小计第1章数据结构与算法22第2章异常处理与调试224第3章线性表2125第4章队列和栈2125第5章串2125第6章树和二叉树4149第7章树和二叉树的应用4149第8章图论4149第9章图的应用4149第10章查找4149第11章排序4149第12章Scipy2125第13章Pandas2125第14章networkX2125合计40123890六、实验部分教学内容和要求：序号实验项目名称实验内容及要求学时实验类型演示验证设计综合1异常处理与调试Python各类编程环境的安装及使用、调试的应用。222线性表线性表的应用223栈和队列栈的应用。队列的应用224串串的应用225树和二叉树二叉树的遍历算法及基于遍历的简单应用4226树和二叉树的应用应用哈夫曼树构造哈夫曼编码。4227图论图的深度优先遍历算法和广度优先遍历算法4228图的应用图的最小生成树算法、图的拓扑排序和关键路径算法、图的求最短路径的Dijkstra算法、Floyd算法。4229查找顺序查找、折半查找、索引查找；二叉排序树、平衡二叉排序树；4410排序直接插入排序、希尔排序；掌握交换类排序的算法：冒泡排序、快速排序；掌握选择类排序的算法：简单选择排序、堆排序；了解归并排序思想4411Scipy图的遍历、深度广度优先搜索、最短路径和图的连通分量2212Pandas基本数据类型：Series、DataFrame和Index。掌握实现图的两种存储方式（邻接矩阵和边列表），如何实现节点度数（有向图、加权图）2213networkX掌握各类图（无向图、有向图、多重图），节点、边的属性和操作，掌握深度广度优先搜索方法，掌握图的连通性的分析和判断，掌握无权图和加权图的最短路径的实现方法22合计3820414七、考核方式1.考核方式与成绩评定方法课程考核总评成绩（满分100）=平时（满分100，占比40%）+期中考试（满分100分，占30%）+期末考试（满分100分，占比30%）（1）平时：主要考核对各个知识点的复习、理解和掌握程度；课堂讨论情况、平时作业和每次实验的完成情况。（2）期中考试：机试，主要考核对课程知识点掌握程度以及运用理论知识解决实际问题的能力。（3）期末考试：机试，全面考核对数据结构与算法课程的整体知识点掌握程度以及运用理论知识解决实际问题的能力。考核与评价标准：平时成绩考核及评价标准评分标准优秀（0.90-1.0）良好（0.75-0.89）合格（0.60-0.74）不合格（0-0.59）按时交作业；基本概念正确、论述逻辑清楚；层次分明，语言规范。按时交作业；基本概念正确、论述基本清楚；语言较规范。按时交作业；基本概念基本正确、论述基本清楚；语言较规范。不能按时交作业；有抄袭现象；或者基本概念不清楚、论述不清楚。期中成绩考核及评价标准评分标准优秀（0.90-1.0）良好（0.75-0.89）合格（0.60-0.74）不合格（0-0.59）很好的掌握线性结构和树状结构，和其存储结构，及其相应基本算法，并对算法进行评价分析。能掌握线性结构和树状结构，和其存储结构，及其相应基本算法，并对算法进行评价分析。基本能够掌握线性结构和树状结构，和其存储结构，及其相应基本算法，但不够准确；能对算法进行评价分析，但存在缺陷。未完全掌握线性结构和树状结构，和其存储结构，及其相应基本算法，基本概念时出现错误，未完全理解算法评价分析方法。期末成绩考核及评价标准评分标准优秀（0.90-1.0）良好（0.75-0.89）合格（0.60-0.74）不合格（0-0.59）很好的掌握数据结构的各种逻辑结构、存储结构和相应算法，并对算法进行评价分析。能掌握数据结构的各种逻辑结构、存储结构和相应算法，并对算法进行评价分析。基本能够掌握数据结构的各种逻辑结构、存储结构和相应算法，但不够