《数据结构与算法》教学大纲

1、数据结构与算法一Python版课程教学大纲课程名称：数据结构与算法一Python版适用专业：计算机科学与技术先修课程：计算机导论、离散数学学分：4总学时：64授课学时：40 实验（上机）学时：24一课程简介Python是一门开源的高级动态编程语言，支持命令式编程、函数式编程、 面向对象程序设计，语法简洁清晰，并且拥有大量功能丰富的标准库和扩展库。 数据结构是计算机各专业的专业基础课。它是操作系统、数据库、编译原理等软 件专业基础课和专业课的重要基础；它还是进行程序设计，尤其是进行高水平的 应用程序和系统程序设计必不可少的基础。通过本课程的学习，使学生掌握数据 组织、存储和运算的基本原理和方法，

2、培养学生对各类数据结构和相关算法的分 析和设计的能力，使学生能够编写出正确、清晰和较高质量的算法和程序。二 本课程与其它课程的联系本课程的先修课是面向过程程序设计、离散数学。面向过程程序设计为本课 程提供实践工具，离散数学为本课程提供理论基础。本课程是操作系统、数据库、 编译原理等软件专业基础课和专业课的重要基础；为这些后续课程分析问题时提 供规范的思路，为解决问题提供好的结构和算法。同时它还为进行程序设计，尤 其是进行高水平的应用程序和系统程序设计打下必不可少的坚实的基础。该课程学习完成后，学生还要进行“数据结构课程设计”的实践环节，使学 生在掌握数据结构基本理论知识的基础上，进一步掌握应用

3、系统设计的方法和步 骤，灵活运用并深刻理解典型数据结构在软件开发中的应用，进一步提高分析问 题和解决问题的能力，提高程序设计水平。和相应算法，并 对算法进行评价 分析。相应算法，并对 算法进行评价分 析。构和相应算法， 但不够准确；能 对算法进行评价 分析，但存在缺 陷。和相应算法，基 本概念时出现错 误，未完全理解 算法评价分析方 法。七、建议教材及参考资料建议教材：1周元哲.数据结构与算法Python版.北京：机械工业出版社.2020 参考资料：1周元哲，刘伟，邓万宇.程序基本算法习题解析.北京：清华大学出版 社 20182周元哲.Python3程序设计基础.北京：机械工业出版社.2019

4、三、课程内容及要求第1章数据结构与算法主要内容：.数据结构的概念、内容；.算法的概念、评价标准、描述方法、性能分析。基本要求：了解数据结构、算法的基本概念；了解数据结构的地位；了解各 种算法描述方法和算法设计的基本要求；掌握对算法的评价标准和算法效率的度 量方法。重.点：逻辑结构和存储结构的区别，时间复杂度的分析和计算方法。难.点：时间复杂度的分析和计算方法。第2章Python开发环境主要内容：Python语言的开展。Python语言特点。Python程序开发工具介绍。基本要求：了解程序设计语言及其开展历史；了解Python语言的特点；掌 握程序设计的一般过程。重 点：Python语言环境安装

5、及使用。难 点：Python语言的基本结构。第3章Python数据类型主要内容：.常量、变量和表达式. Python的基本数据类型.运算符与表达式.列表.元组.字符串.字典.集合基本要求：理解数据类型的概念、作用以及Python语言的基本数据类型； 掌握常量、变量基本概念；掌握Python语言各类运算符的含义、运算符的优先 级和结合性、表达式的构成以及表达式的求解过程。掌握序列基础知识；熟练掌 握列表的定义、常用操作和常用函数；熟练掌握元组的定义和常用操作；熟练掌 握字典的定义和常用操作；掌握字符串格式化、字符串截取的方法；理解与字符 串相关的重要内置方法。熟练掌握字典的定义和常用操作；熟练掌

6、握集合的定义 和常用操作。重 点：数据类型的作用、变量的定义，各类运算符以及构成的表达式的求 解。序列、列表、元组的定义和常用操作。字典、集合的定义和常用操作。难 点：运算符的优先级和结合性。列表常用函数的应用，字符串的应用。 字典及集合的应用。第4章Python三大结构主要内容：.数据的输入与输出.单分支选择结构.双分支选择结构.多分支选择结构. while循环结构. for语句结构.循环的嵌套基本要求：掌握程序的三种基本结构；掌握顺序结构程序设计；熟练掌握 Python语言中输入输出格式的规那么和用法。熟练掌握if语句的三种形式和用法 以及if语句的嵌套使用；掌握选择分支结构的应用。熟练掌

7、握循环结构while、 for语句的规那么和用法；熟悉continue、break、pass语句的用法；掌握循环结构 的嵌套规那么。重 点：数据的输入输出。if语句的三种形式和使用方法。循环结构的应用。 难点：格式化输出的规那么和用法。选择分支结构的应用。循环的嵌套。第5章函数主要内容：.函数的定义与调用.函数的参数及返回值.递归函数.变量的作用域.模块基本要求：理解函数的作用；熟练掌握函数定义和函数调用的规那么和用法; 掌握函数参数传递的规那么和用法；理解函数的嵌套和递归调用；掌握模块的定义 及导入方法。重 点：函数的作用、定义和调用。难点：函数的参数传递、递归调用。6章线性表主要内容：.线

8、性表的逻辑结构定义、基本操作.两种存储结构中基本操作的实现；.栈的应用。.队列的应用。.串的应用基本要求：理解线性表的概念、定义、逻辑结构和存储结构；熟练掌握线性 表的顺序存储结构及其各种基本运算；熟练掌握单链表等链式存储结构及其各种 基本运算。重点：线性表的特征；顺序表、单链表的存储结构及其各种基本运算。栈 和队列的特点、存储方式及基本操作；栈和队列的应用。串的模式匹配算法。难点：顺序表和链表这两种存储表示方法的综合比拟，静态链表的存储表 示方法。采用栈和队列数据结构解决实际具体问题；串的KMP模式匹配算法。7章树与二叉树主要内容：.树的概念；.二叉树的定义、性质、存储结构；.二叉树的遍历及

9、基于遍历的应用；.树、二叉树之间的转换；.哈夫曼树及其应用。基本要求：理解树的基本概念及其存储结构；熟练掌握二叉树的定义、性质 以及各种存储结构和遍历算法；掌握线索二叉树的概念、存储结构及线索化算法; 掌握树和森林与二叉树间的转换，掌握哈夫曼树的概念、存储结构和应用。重 点：二叉树的遍历算法及基于遍历的简单应用；树和森林与二叉树间的 转换；哈夫曼树的概念、存储结构和应用哈夫曼树构造哈夫曼编码。难点：应用哈夫曼树构造编码。第8章图主要内容：.图的基本概念；.图的存储结构；.图的遍历；.图的应用。基本要求：理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构；熟 练掌握图的深度优先和广度优先遍历算

10、法;理解图的连通性、最小生成树的概念, 掌握求最小生成树算法；掌握求最短路径的算法。重点：图的邻接矩阵和邻接表的存储结构；图的深度优先遍历算法和广度 优先遍历算法；图的最小生成树算法、图的求最短路径的Dijkstra算法、Floyd 算法。难点：理解图的关键路径算法、图的求最短路径算法；利用图的重要算 法解决实际具体问题。9章查找主要内容：.查找的概念以及效率的评价方法；.基于线性表的查找一一顺序查找、折半查找、索引查找；.基于树的查找一一二叉排序树、平衡二叉排序树；.哈希查找法的概念和构造方法。基本要求：理解查找的概念及其效率的评价方法；理解静态查找表的概念, 熟练掌握顺序、折半和分块查找算

11、法；理解动态查找表和二叉排序树的概念；了 解平衡二叉树的概念，创立调整过程；理解哈希表的含义，掌握哈希函数的构造 和处理冲突的基本方法；重 点：顺序、折半查找算法、二叉排序树的插入、删除和查找算法；哈希 函数的构造和处理冲突的基本方法；查找成功和不成功时的平均查找长度计算方 法。难 点：理解折半查找的判定树，分析折半查找的平均查找长度；二叉排 序树的插入、删除算法；平衡二叉排序树的创立调整过程；哈希函数的查找成功 和不成功的平均查找长度计算方法。第10章排序主要内容：.排序的概念以及排序算法的性能评价；.插入类排序一一直接插入排序、折半插入排序、希尔排序；.交换类排序一一冒泡排序、快速排序；.

12、选择类排序一一简单项选择择排序、堆排序；.归并类排序；基本要求：掌握插入类排序的算法：直接插入排序、希尔排序；掌握交换类 排序的算法：冒泡排序、快速排序；掌握选择类排序的算法：简单项选择择排序、堆 排序；了解归并排序思想重 点：理解快速排序、堆排序、归并排序等排序算法的思想；掌握排序 方法的平均时间复杂度、最坏时间复杂度和算法所需的辅助存储空间。难 点：快速排序、堆排序、归并排序的思想；各种排序方法的综合比拟。11章 异常处理与调试主要内容：. Python中异常处理结构.断言与上下文管理基本要求：理解Python异常处理的结构；理解断言与上下文管理的含义。重点：异常处理结构及断言。难点：自定

13、义异常处理。四、教学安排及学时分配节及学时主要内容学时分配授课习题课实验网络其它小计第1章数据结构与算法22第2章python开发环境22第3章python数据类型224第4章python三大结构426第5章函数426第6章线性表426第7章树和二叉树4149第8章图4149第9章查找4149第10章排序4149第11章异常处理与调试22合计3642464五、实验局部教学内容和要求：（含课内实验的课程填写本局部）序号实验工程名称实验内容及要求学时实验类型演示验证设计综合1顺序、选择程 序设计Python编程环境的安装及使用、 顺序、选择结构的设计的应用。222循环结构程序 设计循环结构的设计方

14、法及循环控制 语句的应用。223函数函数的定义、函数的嵌套以及递归 调用，并体会函数的特点。224线性表栈的应用。队列的应用。串的应 用225树和二叉树二叉树的遍历算法及基于遍历的 简单应用；应用哈夫曼树构造哈夫 曼编码。446图图的深度优先遍历算法和广度优先遍历算法；图的最小生成树 算法、图的拓扑排序和关键路径算 法、图的求最短路径的Dijkstra算 法、Floyd算法。447查找顺序查找、折半查找、索引查找； 二叉排序树、平衡二叉排序树；448排序直接插入排序、希尔排序；掌握 交换类排序的算法：冒泡排序、快 速排序；掌握选择类排序的算法： 简单项选择择排序、堆排序；了解归并 排序思想44

15、合计241446六 考核方式.考核方式与成绩评定方法课程考核总评成绩（总分值100）;平时（总分值100,占比45%） +期中考试（满 分100分，占20%） +期末考试（总分值100分，占比35%）（1）平时：主要考核对各个知识点的复习、理解和掌握程度；课堂讨论情 况、平时作业和每次实验的完成情况。（2）期中考试：主要考核对课程前六章的知识点掌握程度以及运用理论知识解决实际问题的能力。（3）期末考试：主要考核对数据结构与算法课程的知识点掌握程度以及运用理论知识解决实际问题的能力。.考核与评价标准：（1）平时成绩考核及评价标准评分标准优秀 (0. 90-1.0)良好(0. 75-0. 89)合

16、格(0. 60-0. 74)不合格 (0-0. 59)按时交作业；基 本概念正确、论 述逻辑清楚；层 次清楚，语言规 范。按时交作业；基 本概念正确、论 述基本清楚；语 言较规范。按时交作业；基 本概念基本正 确、论述基本清 楚；语言较规范。不能按时交作 业；有抄袭现象； 或者基本概念不 清楚、论述不清 楚。（2）期中成绩考核及评价标准评分标准优秀 (0.90-1.0)良好(0. 75-0. 89)合格 (0, 60-0. 74)不合格 (0-0. 59)很好的掌握线性 结构和树状结 构，和其存储结 构，及其相应基 本算法，并对算 法进行评价分 析。能掌握线性结构 和树状结构，和 其存储结构，及 其相应基本算 法，并对算法进 行评价分析。基本能够掌握线 性结构和树状结 构，和其存储结 构