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

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

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

3、论知识的基础上，进一步掌握应用系统设计的方法和步 骤，灵活运用并深刻理解典型数拯结构在软件开发中的应用，进一步提高分析问 题和解决问题的能力，提高程序设计水平。 三、课程内容及要求 第1章数据结构与算法 主要内容： 1. 数据结构的概念、内容； 2. 算法的概念、评价标准、描述方法、性能分析。 基本要求：了解数据结构、算法的基本概念；了解数据结构的地位；了解各 种算法描述方法和算法设计的基本要求；掌握对算法的评价标准和算法效率的度 量方法。 重 点：逻辑结构和存储结构的区别，时间复杂度的分析和计算方法。 难 点：时间复杂度的分析和计算方法。 第2章Python开发环境 主要内容： 1. Pyt

4、hon语言的发展。 2. Python语言特点。 3. Python程序开发工具介绍。 基本要求：了解程序设计语言及其发展历史；了解Python语言的特点；掌 握程序设计的一般过程。 重 点：Python语言环境安装及使用。 难 点：Python语言的基本结构。 第3章Python数据类型 主要内容： 1. 常量、变量和表达式 2. Python的基本数据类型 3. 运算符与表达式 4. 列表 5. 元组 6. 字符串 7. 字典 8. 集合 基本要求：理解数据类型的概念、作用以及Python语言的基本数据类型; 掌握常量、变量基本概念；掌握Python语言各类运算符的含义、运算符的优先 级和

5、结合性、表达式的构成以及表达式的求解过程。掌握序列基础知识；熟练掌 握列表的定义、常用操作和常用函数；熟练掌握元组的定义和常用操作；熟练掌 握字典的定义和常用操作；掌握字符吊格式化、字符审截取的方法；理解与字符 吊相关的重要内置方法。熟练掌握字典的定义和常用操作；熟练掌握集合的定义 和常用操作。 重 点：数据类型的作用、变量的定义，各类运算符以及构成的表达式的求 解。序列、列表、元组的定义和常用操作。字典、集合的定义和常用操作。 难 点：运算符的优先级和结合性。列表常用函数的应用，字符吊的应用。 字典及集合的应用。 第4章Python三大结构 主要内容： 1. 数据的输入与输出 2. 单分支选

6、择结构 3. 双分支选择结构 4. 多分支选择结构 5. while循环结构 6. for语句结构 7. 循环的嵌套 基本要求：掌握程序的三种基本结构；掌握顺序结构程序设计；熟练掌握 Python语言中输入输出格式的规则和用法。熟练掌握if语句的三种形式和用法 以及if语句的嵌套使用：掌握选择分支结构的应用。熟练掌握循环结构while, for语句的规则和用法；熟悉continue breaks pass语句的用法；掌握循环结构 的嵌套规则。 重 点：数据的输入输出。if语句的三种形式和使用方法。循环结构的应用。 难点：格式化输出的规则和用法。选择分支结构的应用。循环的嵌套。 第5章函数 主要

7、内容： 1. 函数的定义与调用 2. 函数的参数及返回值 3. 递归函数 4. 变量的作用域 5. 模块 基本要求：理解函数的作用；熟练掌握函数定义和函数调用的规则和用法； 掌握函数参数传递的规则和用法；理解函数的嵌套和递归调用；掌握模块的定义 及导入方法。 重 点：函数的作用、定义和调用。 难点：函数的参数传递、递归调用。 第6章线性表 主要内容： 1. 线性表的逻辑结构定义、基本操作 2. 两种存储结构中基本操作的实现： 3. 栈的应用。 4. 队列的应用。 5, 宙的应用 基本要求J理解线性表的概念、定义、逻辑结构和存储结构；熟练掌握线性 表的顺序存储结构及其各种基本运算：熟练寧:握单链

8、表等链式存储结构及其各种 基本运算。 重 点：线性表的特征；顺序表、单链表的存储结构及其各种基本运算。栈 和队列的特点、存储方式及基本操作；栈和队列的应用。串的模式匹配算法。 难 点：顺序表和链表这两种存储表示方法的综合比较，静态链表的存储表 示方法。采用栈和队列数据结构解决实际具体问题；串的KMP模式匹配算法。 第7章树与二叉树 主要内容： 1. 树的概念； 2. 二义树的定义、性质.存储结构: 3. 二义树的遍历及基于遍历的应用: 4. 树、二义树之间的转换: 5哈夫曼树及其应用。 基本要求：理解树的基本概念及其存储结构；熟练掌握二义树的定义、性质 以及各种存储结构和遍历算法;掌握线索二义

9、树的概念、存储结构及线索化算法; 掌握树和森林与二义树间的转换，掌握哈夫曼树的概念、存储结构和应用。 重 点：二义树的遍历算法及基于遍历的简单应用；树和森林与二义树间的 转换：哈夫曼树的概念.存储结构和应用哈夫曼树构造哈夫曼编码。 难 点，应用哈夫曼树构造编码。 第8章图 主要内容： 1. 图的基本概念: 2. 图的存储结构; 3. 图的遍历: 4. 图的应用。 基本要求：理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构；熟 练掌握图的深度优先和广度优先遍历算法;理解图的连通性、最小生成树的概念, 掌握求最小生成树算法；掌握求最短路径的算法。 重点：图的邻接矩阵和邻接表的存储结构；图的深度

10、优先遍历算法和广度 优先遍历算法；图的最小生成树算法、图的求最短路径的Dijkstra算法、Floyd 算法。 难点：理解图的关键路径算法、图的求最短路径算法；利用图的重要算 法解决实际具体问题。 第9章査找 主要内容： 1. 查找的概念以及效率的评价方法; 2. 基于线性表的查找一顺序査找、折半查找、索引查找: 3. 基于树的査找一一二义排序树、平衡二义排序树; 4哈希查找法的概念和构造方法。 基本要求：理解査找的概念及其效率的评价方法；理解静态査找表的概念, 熟练掌握顺序、折半和分块査找算法；理解动态査找表和二义排序树的概念：了 解平衡二义树的概念，创建调整过程；理解哈希表的含义，掌握哈希

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

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

13、主要内容 学时分配 授课 习题课 实脸 网络 其它 小计 第1章数据结构打算法 2 2 第2章python开发环境 2 2 第3章python数据类型 2 2 4 第4章python三大结构 4 2 6 第5章函数 4 2 6 第6章线性表 4 2 6 第7章树和二叉树 4 1 4 9 第8章图 4 I 4 9 第9章査找 4 1 4 9 第10章排序 4 1 4 9 第11章异常处理与调试 2 2 合计 36 4 24 64 五、实验部分教学内容和要求：（含课内实验的课程填写本部分） 序号 实验项目名称 实验内容及要求 学 时 实验类型 演 示 验 证 设 il- 综合 1 顺序、选择程 序

14、设计 Python编程环境的安装及使用、 顺序、选择结构的设il的应用。 2 2 2 循环结构程序 设计 循环结构的设计方法及循环控制 语句的应用。 2 2 3 函数 函数的左义、函数的嵌套以及递归 调用，并体会函数的特点。 2 2 4 线性表 栈的应用。队列的应用。串的应 用 2 2 5 树和二叉树 二叉树的遍历算法及基于遍历的 简单应用：应用哈夹曼树构造哈夫 曼编码。 4 4 6 图 图的深度优先遍历算法和广度 优先遍历算法：图的最小生成树 算法、图的拓扑排序和关键路径算 法、图的求最短路径的Dijkstra算 法、Floyd算法。 4 4 7 査找 顺序查找、折半查找、索引查找： 二叉排

15、序树、平衡二叉排序树： 4 4 8 排序 直接插入排序、希尔排序：掌握 交换类排序的算法：冒泡排序、快 速排序：掌握选择类排序的算法： 简单选择排序、堆排序：了解归并 排序思想 4 4 合讣 24 14 4 6 六、考核方式 1.考核方式与成绩评定方法 课程考核总评成绩（满分100）=平时（满分100,占比45%） +期中考试（满 分100分，占20%） +期末考试（满分100分，占比35%） （1）平时：主要考核对各个知识点的复习、理解和掌握程度；课堂讨论悄 况、平时作业和每次实验的完成请况。 2）期中考试：主要考核对课程询六章的知识点掌握程度以及运用理论知 识解决实际问题的能力。 （3）期

16、末考试：主要考核对数据结构与算法课程的知识点掌握程度以及运 用理论知识解决实际问题的能力。 2. 考核与评价标准: 1）平时成绩考核及评价标准 评分标准 (2) 优秀 (0. 90-1. 0) 良好 (0.75-0. 89) 合格 (0.60-0. 74) 不合格 (0-0. 59) 按时交作业：基 本概念正确、论 述逻辑淸楚；层 次分明，语言规 范。 按时交作业：基 本概念正确、论 述基本淸楚：语 言较规范。 按时交作业：基 本概念基本正 确、论述基本淸 楚：语言较规范。 不能按时交作 业：有抄袭现象： 或者基本概念不 淸楚、论述不清 期中成绩考核及评价标准 评分标准 优秀 (0. 9CHt

17、 0) 良好 (0.75-0. 89) 合格 (0. 60-0. 74) 不合格 (0-0. 59) 很好的掌握线性 结构和树状结 构，和其存储结 构，及其相应基 本算法，并对算 法进行评价分 析。 能掌握线性结构 和树状结构，和 其存储结构，及 其相应基本算 法，并对算法进 行评价分析。 基本能够掌握线 性结构和树状结 构，和其存储结 构，及其相应基 本算法，但不够 准确：能对算法 进行评价分折， 但存在缺陷。 未完全掌握线性 结构和树状结 构，和其存储结 构,及其相应基 本算法，基本概 念时出现错误， 未完全理解算法 评价分析方法。 3）期末成绩考核及评价标准 评分标准 优秀 (0. 9CK. 0) 良好 (0.75-0. 89) 合格 0.60-0. 74) 不合格 (0-0. 59) 很好的掌握数据 结构的徉种逻辑 结构、存储结构 能掌握数据结构 的$种逻辑结 构、存储结构和 基本能够掌握数 据结构的齐种逻 辑结构、