《数据结构与算法》课程教学大纲 一、课程基本信息 课程代码：18110214 课程名称：数据结构与算法 英文名称：Data Structure&Algorithm 课程类别：专业基础课 学 时：64 学分：4 适用对象：软件工程专业 考核方式：考试 先修课程：Java面向对象程序设计 二、课程简介 数据结构是一门专业基础课，是学习其他软件开发与设计等方面课程的基 础。主要内容包括：线性表、栈和队列、串、数组和广义表、树、图、查找算法 和排序算法。数据结构研究数据的组织方式，内容丰言、学习量大，隐含在各部 分内容中的方法和技术多，旨在让学生掌握计算机软件系统所必需的数据结构的 算法。要求学生掌握贯踪全课程的动态链表存储结构，掌握算法设计的动态性和 抽象性。要求学生学会分析研究计算机加工的数据对象的特征，以便在实际应用 中选择适当的数据结构、存储结构和相应算法，初步掌握算法的时间与空间性能 分析技巧，并培养复杂程序设计的技能。 Data structure is a professional basic course.which is the basis of learning other software development and design courses.The main contents include:linear table, stack and queue,string.array and generalized table,tree,graph,search algorithm and sorting algorithm.Data structure research data organization,rich content,large amount of learning,hidden in each part of the content of the method and technology, aims to let students master the computer software system necessary data structure algorithm.Students are required to master the dynamic linked list storage structure throughout the whole course and the dynamic and abstract nature of algorithm design Students are required to learn to analyze and study the characteristics of data objects processed by computer,so as to select appropriate data structure,storage structure and corresponding algorithm in practical application,preliminarily master the time and space performance analysis skills of algorithm,and cultivate the skills of complex
《数据结构与算法》课程教学大纲 一、课程基本信息 课程代码：18110214 课程名称：数据结构与算法 英文名称：Data Structure & Algorithm 课程类别：专业基础课 学 时：64 学 分：4 适用对象: 软件工程专业 考核方式：考试 先修课程：Java 面向对象程序设计 二、课程简介 数据结构是一门专业基础课，是学习其他软件开发与设计等方面课程的基 础。主要内容包括：线性表、栈和队列、串、数组和广义表、树、图、查找算法 和排序算法。数据结构研究数据的组织方式，内容丰富、学习量大，隐含在各部 分内容中的方法和技术多，旨在让学生掌握计算机软件系统所必需的数据结构的 算法。要求学生掌握贯穿全课程的动态链表存储结构，掌握算法设计的动态性和 抽象性。要求学生学会分析研究计算机加工的数据对象的特征，以便在实际应用 中选择适当的数据结构、存储结构和相应算法，初步掌握算法的时间与空间性能 分析技巧，并培养复杂程序设计的技能。 Data structure is a professional basic course, which is the basis of learning other software development and design courses. The main contents include: linear table, stack and queue, string, array and generalized table, tree, graph, search algorithm and sorting algorithm. Data structure research data organization, rich content, large amount of learning, hidden in each part of the content of the method and technology, aims to let students master the computer software system necessary data structure algorithm. Students are required to master the dynamic linked list storage structure throughout the whole course and the dynamic and abstract nature of algorithm design. Students are required to learn to analyze and study the characteristics of data objects processed by computer, so as to select appropriate data structure, storage structure and corresponding algorithm in practical application, preliminarily master the time and space performance analysis skills of algorithm, and cultivate the skills of complex
programming. 三、课程性质与教学目的 课程性质：数据结构与算法是软件工程专业的一门重要学科基础课，是必修 。 教学目的：通过本课程的学习，一方面，使学生学会分析研究计算机加工的 数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应 的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课 程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能 力。在讲解过程中引入思政案例，培养学生的爱国、敬业情操。 四、教学内容及要求 1.绪论 教学内容： ()数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结 构、算法等。 (2)抽象数据类型的表示和实现。 (3)算法时间复杂度和空间复杂度的分析。 基本要求： 掌握数据结构的基本概念，了解抽象数据类型，掌握算法时间复杂度和空间 复杂度的分析方法。学习国学选读，增强学生文化自信，民族自信。 2.线性表 教学内容： (1)线性表的类型定义。 (2)线性表的顺序表示和实现 (3)线性表的链式表示和实现。 基本要求： 理解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表 示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链 表)。熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首 元结点的区别及循环链表、双向链表的特点等。掌握顺序表的查找、插入和删除 算法，掌握链表的查找、插入和删除算法。能够从时间和空间复杂度的角度比较 两种存储结构的不同特点及其适用场合
programming. 三、课程性质与教学目的 课程性质：数据结构与算法是软件工程专业的一门重要学科基础课，是必修 课。 教学目的：通过本课程的学习，一方面，使学生学会分析研究计算机加工的 数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应 的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课 程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能 力。在讲解过程中引入思政案例，培养学生的爱国、敬业情操。 四、教学内容及要求 1. 绪论 教学内容： (1) 数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结 构、算法等。 (2) 抽象数据类型的表示和实现。 (3) 算法时间复杂度和空间复杂度的分析。 基本要求： 掌握数据结构的基本概念，了解抽象数据类型，掌握算法时间复杂度和空间 复杂度的分析方法。学习国学选读，增强学生文化自信，民族自信。 2. 线性表 教学内容： (1) 线性表的类型定义。 (2) 线性表的顺序表示和实现。 (3) 线性表的链式表示和实现。 基本要求： 理解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表 示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链 表）。熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首 元结点的区别及循环链表、双向链表的特点等。掌握顺序表的查找、插入和删除 算法，掌握链表的查找、插入和删除算法。能够从时间和空间复杂度的角度比较 两种存储结构的不同特点及其适用场合
实验： 实验内容：单链表的基本操作。实验要求：以单链表形式创建一个学生表或 图书表，并能实现相关的查找、插入和删除等算法。 3.栈和队列 教学内容： ()栈的类型定义，栈的顺序存储和链接存储的表示和实现 (②)栈的应用举例，如迷宫求解和表达式求值。 (3)栈与递归的实现，Hanoi塔问题。 (④)队列的类型，队列的顺序存储（循环队）和链接存储的表示和实现 基本要求： 掌握栈和队列的特点，并能在相应的应用问题中正确选用。熟练掌握栈的顺 序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。熟练掌握循环队列 和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。理解 递归算法执行过程中栈的状态变化过程。了解在表达式计算时栈是如何使用的， 重点了解计算表达式的方法和算法思路。 实验： 实验内容：栈的应用。实验要求：借助栈来解决某些实际应用问题，如表达 式求值等。 4.串、数组和广义表 教学内容： (1)串的表示和实现，包括顺序存储和链式存储表示。古典的模式匹配算法。 (②)数组的存储方法。 (3)广义表的逻辑结构和存储结构。 基本要求： 了解串的顺序存储结构和堆存储结构。掌握串的古典的模式匹配算法。掌握 数组的地址计算方法。了解广义表的结构特点及其存储方法。 5.树和二叉树 教学内容： (1)二叉树的定义和术语，二叉树的性质，特殊的二叉树。 (2)二叉树的存储结构，顺序存储和二叉链表。 (③)二叉树的的前序、中序、后序、层次遍历方法。 (4)树的应用，哈夫曼树及哈夫曼编码。 基本要求： 了解树和森林的概念，包括树的定义、树的术语。掌握二叉树的概念、性质
实验： 实验内容：单链表的基本操作。实验要求：以单链表形式创建一个学生表或 图书表，并能实现相关的查找、插入和删除等算法。 3. 栈和队列 教学内容： (1) 栈的类型定义，栈的顺序存储和链接存储的表示和实现。 (2) 栈的应用举例，如迷宫求解和表达式求值。 (3) 栈与递归的实现，Hanoi 塔问题。 (4) 队列的类型，队列的顺序存储(循环队)和链接存储的表示和实现。 基本要求： 掌握栈和队列的特点，并能在相应的应用问题中正确选用。熟练掌握栈的顺 序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。熟练掌握循环队列 和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。理解 递归算法执行过程中栈的状态变化过程。了解在表达式计算时栈是如何使用的， 重点了解计算表达式的方法和算法思路。 实验： 实验内容：栈的应用。实验要求：借助栈来解决某些实际应用问题，如表达 式求值等。 4. 串 、数组和广义表 教学内容： (1) 串的表示和实现，包括顺序存储和链式存储表示。古典的模式匹配算法。 (2) 数组的存储方法。 (3) 广义表的逻辑结构和存储结构。 基本要求： 了解串的顺序存储结构和堆存储结构。掌握串的古典的模式匹配算法。掌握 数组的地址计算方法。了解广义表的结构特点及其存储方法。 5. 树和二叉树 教学内容： (1) 二叉树的定义和术语，二叉树的性质，特殊的二叉树。 (2) 二叉树的存储结构，顺序存储和二叉链表。 (3) 二叉树的的前序、中序、后序、层次遍历方法。 (4) 树的应用，哈夫曼树及哈夫曼编码。 基本要求： 了解树和森林的概念，包括树的定义、树的术语。掌握二叉树的概念、性质
及二叉树的表示。熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二 叉树的其他操作。掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径 长度的计算。 实验： 实验内容：二叉树的基本算法。实验要求：利用二叉链表方法建立二叉树， 实现二叉树的前、中、后序三种遍历算法，并运用遍历算法实现二叉树的其他操 作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等。 6.图 教学内容： (1)图的定义和术语。 (2)图的存储结构两种存储结构：邻接矩阵和邻接表表示法。 (③)图的两种遍历策略：深度优先搜索和广度优先搜索。 (4)构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法， (⑤)拓扑排序。 (6)求最短路径问题的算法，迪杰斯特拉算法。 基本要求： 掌握图的基本概念及相关术语和性质，掌握图的邻接矩阵和邻接表表示法 了解实际问题的求解效率与采用何种存储结构和算法有密切联系。熟练掌握图的 两种搜索路径的遍历：深度优先搜索和广度优先搜索算法的思想。掌握构造最小 生成树的两种算法及拓扑排序算法的思想，学握迪杰斯特拉算法的思想。学习毛 邓思节选，培养学生为社会主义的发展做贡献的远大理想。 7.查找 教学内容： (1)查找的基本概念，平均查找长度。 (2)基于线性表的查找：顺序查找、折半查找。 (3)基于树表的查找：二叉排序树。 (4)散列表：散列表的基本概念，散列函数的构造方法、处理冲突的方法 散列表的查找与分析。 基本要求： 熟练掌握顺序表和有序表的查找方法及其实现，掌握二叉排序树的插入和查 找算法的思想。熟练掌握散列表的构造方法、处理冲突的方法，深刻理散列表与 其他结构的表的实质性的差别，了解各种散列函数的特点。掌握描述折半查找过 程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功 时的平均查找长度
及二叉树的表示。熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二 叉树的其他操作。掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径 长度的计算。 实验： 实验内容：二叉树的基本算法。实验要求：利用二叉链表方法建立二叉树， 实现二叉树的前、中、后序三种遍历算法，并运用遍历算法实现二叉树的其他操 作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等。 6. 图 教学内容： (1) 图的定义和术语。 (2) 图的存储结构两种存储结构：邻接矩阵和邻接表表示法。 (3) 图的两种遍历策略：深度优先搜索和广度优先搜索。 (4) 构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法。 (5) 拓扑排序。 (6) 求最短路径问题的算法，迪杰斯特拉算法。 基本要求： 掌握图的基本概念及相关术语和性质，掌握图的邻接矩阵和邻接表表示法， 了解实际问题的求解效率与采用何种存储结构和算法有密切联系。熟练掌握图的 两种搜索路径的遍历：深度优先搜索和广度优先搜索算法的思想。掌握构造最小 生成树的两种算法及拓扑排序算法的思想，掌握迪杰斯特拉算法的思想。学习毛 邓思节选，培养学生为社会主义的发展做贡献的远大理想。 7. 查找 教学内容： (1) 查找的基本概念，平均查找长度。 (2) 基于线性表的查找：顺序查找、折半查找。 (3) 基于树表的查找：二叉排序树。 (4) 散列表：散列表的基本概念，散列函数的构造方法、处理冲突的方法、 散列表的查找与分析。 基本要求： 熟练掌握顺序表和有序表的查找方法及其实现，掌握二叉排序树的插入和查 找算法的思想。熟练掌握散列表的构造方法、处理冲突的方法，深刻理散列表与 其他结构的表的实质性的差别，了解各种散列函数的特点。掌握描述折半查找过 程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功 时的平均查找长度
8.排序 教学内容： (1)排序的基本概念，包括正序，逆序，稳定性，排序方法的分类。 (②)插入排序：直接插入排序、折半插入排序。 (3)交换排序：冒泡排序和快速排序。 (4)选择排序：简单选择排序和堆排序。 (⑤)归并排序：2-路归并排序。 (6)排序算法分析：各种排序算法的比较和移动次数，时间复杂度和空间复 杂度的分析。 基本要求： 明确排序的基本概念，排序方法的分类。深刻理解排序算法的过程、特点及 其依据的原则，并能加以灵活应用。掌握各种排序方法的时间和空间复杂度的分 析方法。能从关键字间的比较次数和移动次数分析算法的平均情况和最坏情况的 时间性能。理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要 求应用的排序方法必须是稳定的。快速排序、堆排序和归并排序等高效排序方法 是本章的学习重点和难点。接合具体案例，讲解排序的应用，及其对我国软件技 术的发展所起的做用，培养学生树立正确的人生观、价值观、世界观。 实验： 实验内容：综合性实验。实验要求：选取一个合适的数据结构存储数据，能 对数据进行插入、删除，用不同查找算法进行查找、用不同的排序算法进行排序 等。 五、各教学环节学时分配 教学环节 习 讨 其他教 教学时数 课 题课 实验 学环节 课 计 课程内容 第一章 2 第二章 第三章 第四章 6 第五章 10
8. 排序 教学内容： (1) 排序的基本概念，包括正序，逆序，稳定性，排序方法的分类。 (2) 插入排序：直接插入排序、折半插入排序。 (3) 交换排序：冒泡排序和快速排序。 (4) 选择排序：简单选择排序和堆排序。 (5) 归并排序：2-路归并排序。 (6) 排序算法分析：各种排序算法的比较和移动次数，时间复杂度和空间复 杂度的分析。 基本要求： 明确排序的基本概念，排序方法的分类。深刻理解排序算法的过程、特点及 其依据的原则，并能加以灵活应用。掌握各种排序方法的时间和空间复杂度的分 析方法。能从关键字间的比较次数和移动次数分析算法的平均情况和最坏情况的 时间性能。理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要 求应用的排序方法必须是稳定的。快速排序、堆排序和归并排序等高效排序方法 是本章的学习重点和难点。接合具体案例，讲解排序的应用，及其对我国软件技 术的发展所起的做用，培养学生树立正确的人生观、价值观、世界观。 实验： 实验内容：综合性实验。实验要求：选取一个合适的数据结构存储数据，能 对数据进行插入、删除，用不同查找算法进行查找、用不同的排序算法进行排序 等。 五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教 学环节 小 计 第一章 2 2 第二章 6 2 8 第三章 6 2 8 第四章 4 2 6 第五章 8 2 10
第六章 第七章 第八章 综合设计 合计 六、课程考核 (一)考核方式 考试 (二)成绩构成 平时成绩所占比例：30 期末成绩所占比例：70 七、推荐教材和教学参考资源 l.罗福强，杨剑，刘英.数据结构(Java语言描述)，北京：人民邮电出 版社，2020 2.罗文劫，王苗，张小莉.数据结构与算法(Java版)，北京：机械工业出版社，2016 3.严蔚敏，李冬梅，吴伟民.数据结构(C语言版).北京：人民邮电出版社.2016 4.叶小平，陈瑛.数据结构与算法简明教程(Java语言版).北京：清华大学出版社.2016 5.殷人昆主编.数据结构（用面向对象方法与C+描述）.北京：清华大学出版社.2016 八、其他说明 课后实验学时：16 平时成绩所占比例：30 期末成绩所占比例：70 大纲修订人：胡建军 修订日期：2022年1月 大纲审定人：郭玉柱 审定日期：2022年1月
第六章 8 2 10 第七章 6 2 8 第八章 6 2 8 综合设计 2 2 4 合计 48 16 64 六、课程考核 （一）考核方式 考试 （二）成绩构成 平时成绩所占比例：30 期末成绩所占比例：70 七、推荐教材和教学参考资源 1. 罗福强，杨剑，刘英. 数据结构（Java 语言描述），北京：人民邮电出 版社，2020 2. 罗文劫，王苗，张小莉. 数据结构与算法（Java 版），北京：机械工业出版社，2016 3. 严蔚敏，李冬梅，吴伟民．数据结构（C 语言版）．北京：人民邮电出版社．2016 4. 叶小平，陈瑛．数据结构与算法简明教程（Java 语言版）．北京：清华大学出版社．2016 5. 殷人昆主编．数据结构（用面向对象方法与 C++描述）．北京：清华大学出版社．2016 八、其他说明 课后实验学时： 16 平时成绩所占比例：30 期末成绩所占比例：70 大纲修订人：胡建军 修订日期：2022 年 1 月 大纲审定人：郭玉柱 审定日期：2022 年 1 月