新乡学院：数学与统计学院信息与计算科学专业《数据结构》课程教学大纲（2015）

团购合买资源类别：文库，文档格式：PDF，文档页数：9，文件大小：127.09KB

《数据结构》教学大纲课程编码：1512105703 课程名称：数据结构学时/学分：48/3 先修课程：《高等代数》、《离散数学》、《C语言程序设计》适用专业：信息与计算科学开课教研室：信息与计算科学教研室一、课程的性质和任务 1.课程性质：该课程是信息与计算科学专业的一门专业必修课。 2.课程任务：通过本课程的学习，应使学生掌握线性表、堆栈、队列、串、数组、叉树、图等典型数据结构的设计方法：了解各种抽象数据类型的性质：掌握处理各种抽象数据类型的基本算法：重点掌握各种典型数据结构的应用：了解各种典型排序和查找算法的性能和设计方法：重点学握程序设计的基本原理和方法：初步掌握算法的时间分析和空间分析的技术。学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护。二、课程教学基本要求学生通过学习该课程后能够针对不同数据对象的特性，选择适当的数据结构和存储结构以及相应的算法，去解决实际应用问题。学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护，为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。本课程共计学时：理论学时48。成绩考核形式：末考成绩（闭卷考查）(70%)+平时成绩（平时测验、作业、课堂提问、课堂讨论等)(30%)。成绩评定采用百分制，60分为及格。三、课程教学内容第一章绪论 1.教学基本要求了解数据的逻辑结构和物理结构：了解算法对于程序设计的重要性：掌握算法时间复杂度的分析方法 2.要求学生掌握的基本概念、理论、技能

《数据结构》教学大纲课程编码：1512105703 课程名称：数据结构学时/学分：48/3 先修课程：《高等代数》、《离散数学》、《C 语言程序设计》适用专业：信息与计算科学开课教研室：信息与计算科学教研室一、课程的性质和任务 1．课程性质：该课程是信息与计算科学专业的一门专业必修课。 2．课程任务：通过本课程的学习，应使学生掌握线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法；了解各种抽象数据类型的性质；掌握处理各种抽象数据类型的基本算法；重点掌握各种典型数据结构的应用；了解各种典型排序和查找算法的性能和设计方法；重点掌握程序设计的基本原理和方法；初步掌握算法的时间分析和空间分析的技术。学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护。二、课程教学基本要求学生通过学习该课程后能够针对不同数据对象的特性，选择适当的数据结构和存储结构以及相应的算法，去解决实际应用问题。学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护，为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。本课程共计学时：理论学时 48。成绩考核形式：末考成绩（闭卷考查）（70%）＋平时成绩（平时测验、作业、课堂提问、课堂讨论等）（30％)。成绩评定采用百分制，60 分为及格。三、课程教学内容第一章绪论 1.教学基本要求了解数据的逻辑结构和物理结构；了解算法对于程序设计的重要性；掌握算法时间复杂度的分析方法。 2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生了解数据结构的基本概念，主要包括数据、数据元素、数据项、数据结构、四种逻辑结构、四种存储结构、时间复杂度等基本概念：掌握时间复杂度和空间复杂度来评价算法效率的基本分析方法。 3.教学重点和难点教学重点是数据结构的基本概念。教学难点是抽象数据类型和算法分析技术。 4.教学内容 (1)什么是数据结构主要知识点：从数据结构实验演示认识数据结构：数据结构研究的内容 (2)数据的逻辑结构主要知识点：基本概念：数据、数据元素、数据项、数据对象、数据的逻辑结构。 (3)数据的存储结构主要知识点：顺序存储：链式存储：索引存储：散列存储， (4)算法和算法分析主要知识点：算法特性：算法的效率：算法效率的评价。第二章线性表 1.教学基本要求掌握线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握线性表的逻辑结构特征，线性表上定义的基本运算，掌握顺序表的定义及特点，顺序表上的插入删除操作及其平均时间性能：掌握单链表、双链表、循环链表链式存储方式上的区别、基本运算算法和平均时间性能分析。通过本章学习，使学生能够针对具体应用问题的要求和性质，选择合活的存诸结构设计出相应的有效算法，解决与线性表相关的实际问题。 3.教学重点和难点教学重点是顺序表的插入运算、刷除运算，链表的创建、插入、删除运算。教学难点是双链表插入、删除运算的算法：利用链表结构的特点设计算法。 4.教学内容 (1)线性表的定义与运算主要知识点：线性表的定义：线性表的基本操作。 (2)线性表的顺序存储主要知识点：线性表的顺序存储特点：顺序表结构体类型的定义：顺序表上基本运算的实现：顺序表的空间分配及初始化、插入、刷除等基本运算及其平均时间性能分析

通过本章教学使学生了解数据结构的基本概念，主要包括数据、数据元素、数据项、数据结构、四种逻辑结构、四种存储结构、时间复杂度等基本概念；掌握时间复杂度和空间复杂度来评价算法效率的基本分析方法。 3.教学重点和难点教学重点是数据结构的基本概念。教学难点是抽象数据类型和算法分析技术。 4.教学内容（1）什么是数据结构主要知识点：从数据结构实验演示认识数据结构；数据结构研究的内容。（2）数据的逻辑结构主要知识点：.基本概念：数据、数据元素、数据项、数据对象、数据的逻辑结构。（3）数据的存储结构主要知识点：顺序存储；链式存储；索引存储；散列存储。（4）算法和算法分析主要知识点：算法特性；算法的效率；算法效率的评价。第二章线性表 1.教学基本要求掌握线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握线性表的逻辑结构特征，线性表上定义的基本运算，掌握顺序表的定义及特点，顺序表上的插入删除操作及其平均时间性能；掌握单链表、双链表、循环链表链式存储方式上的区别、基本运算算法和平均时间性能分析。通过本章学习，使学生能够针对具体应用问题的要求和性质，选择合适的存诸结构设计出相应的有效算法，解决与线性表相关的实际问题。 3.教学重点和难点教学重点是顺序表的插入运算、删除运算，链表的创建、插入、删除运算。教学难点是双链表插入、删除运算的算法；利用链表结构的特点设计算法。 4.教学内容（1）线性表的定义与运算主要知识点：线性表的定义；线性表的基本操作。（2）线性表的顺序存储主要知识点：线性表的顺序存储特点；顺序表结构体类型的定义；顺序表上基本运算的实现：顺序表的空间分配及初始化、插入、删除等基本运算及其平均时间性能分析

(3)线性表的链式存储结构主要知识点：线性表的链式存储的特点：线性表的链式存储的基本运算：头部尾部建立线性链表、带头指针和不带头指针求表长、插入、删除等基本运算：循环链表特点及基本运算、尾指针取代头指针：存储密度：双链表的特点及基本运算。第三章栈 1.教学基本要求掌握栈的逻辑结构以及在两种存储结构上如何实现栈的基本运算。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握栈的逻辑结构特点，栈与线性表的异同。顺序栈和链栈上实现的入栈、出栈等基本算法。栈的”上溢“和“下溢“的概念及其判别条件，利用栈设计算法解决简单的应用问题 3.教学重点和难点教学重点是栈的定义和特点、栈的基本运算和算法以及栈的典型应用。教学难点是后缀表达式的算法、数制的换算、利用本章的基本知识设计相关的应用问题 4.教学内容 (1)栈的定义与运算主要知识点：栈的定义：栈的特性：栈的应用实例。 (2)栈的存储和实现主要知识点：顺序栈的特点、顺序栈结构体类型的定义、顺序栈的基本运算：链栈的特点、链栈结构体类型的定义、链栈的基本运算。 (3)栈的应用举例主要知识点：数制转换：括号匹配：表达式求值：子程序调用：递归调用。第四章队列 1.教学基本要求掌握队列的逻辑结构以及在两种存储结构上如何实现队列的基本运算。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握队列的逻辑结构特点，队列与线性表的异同，队列的”上溢“和下溢“的概念及其判别条件，使用数组实现的循环队列取代普通的顺序队列的原因，循环队列中对边界条件的处理方法，利用队列设计算法解决简单的应用问题。 3.教学重点和难点教学重点是队列的定义和特点、队列的基本运算和算法以及队列的典型应用。教学难点

（3）线性表的链式存储结构主要知识点：线性表的链式存储的特点；线性表的链式存储的基本运算：头部尾部建立线性链表、带头指针和不带头指针求表长、插入、删除等基本运算；循环链表特点及基本运算、尾指针取代头指针；存储密度；双链表的特点及基本运算。第三章栈 1.教学基本要求掌握栈的逻辑结构以及在两种存储结构上如何实现栈的基本运算。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握.栈的逻辑结构特点，栈与线性表的异同。顺序栈和链栈上实现的入栈、出栈等基本算法。栈的"上溢"和"下溢"的概念及其判别条件，利用栈设计算法解决简单的应用问题。 3.教学重点和难点教学重点是栈的定义和特点、栈的基本运算和算法以及栈的典型应用。教学难点是后缀表达式的算法、数制的换算、利用本章的基本知识设计相关的应用问题 4.教学内容（1）栈的定义与运算主要知识点：栈的定义；栈的特性；栈的应用实例。（2）栈的存储和实现主要知识点：顺序栈的特点、顺序栈结构体类型的定义、顺序栈的基本运算；链栈的特点、链栈结构体类型的定义、链栈的基本运算。（3）栈的应用举例主要知识点：数制转换；括号匹配；表达式求值；子程序调用；递归调用。第四章队列 1.教学基本要求掌握队列的逻辑结构以及在两种存储结构上如何实现队列的基本运算。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握队列的逻辑结构特点，队列与线性表的异同，队列的"上溢"和" 下溢"的概念及其判别条件，使用数组实现的循环队列取代普通的顺序队列的原因，循环队列中对边界条件的处理方法，利用队列设计算法解决简单的应用问题。 3.教学重点和难点教学重点是队列的定义和特点、队列的基本运算和算法以及队列的典型应用。教学难点

是循环队列的特点及判断溢出的条件：利用队列的特点设计相关的应用问题。 4.教学内容 (1)队列的定义与运算主要知识点：队列的定义：队列的特性：队列的应用实例。 (2)队列的存储实现及运算的实现主要知识点：顺序队列的特点、顺序队列结构体类型的定义、顺序队列的基本运算：循环队列的特点、循环队列结构体类型的定义、循环队列的基本运算：链队列的特点、链队列结构体类型的定义、链队列的基本运算。 (3)队列的应用举例主要知识点：队列在输入、输出管理中的应用：对CPU的分配管理：优先队列。第五章串 1.教学基本要求掌握串的逻辑结构、存储结构及其串上的基本运算，C语言及其它高级语言均已具备了较强的串处理功能，掌握串上实现的模式匹配算法。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握串的有关概念及基本运算。串与线性表的关系，掌握串的两种存储表示。串上实现的模式匹配算法及其时间性能分析，使用高级程序设计语言提供的串操作函数构造与串相关的算法解决简单的应用问题。 3.教学重点和难点教学重点是串的有关概念和术语、串的基本运算、串的存储方法和串的模式匹配运算算法。教学难点是串的模式匹配运算算法。 4.教学内容 (1)串的定义主要知识点：串的定义：串的相关术语：长度、空串、空格串、串相等、子串、主串、模式匹配：串的应用：串的输入输出：串的基本运算 (2)串的表示和实现主要知识点：定长顺序存储描述、存储方式：链接存储的描述：串的存储密度：大结点结构：串的堆分配存储结构：堆分配存储的方法：带长度索引表的描述。 (3)串的基本运算主要知识点：串长度、求子串、串连接、串比较、插入子串、删除子串、模式匹配基本算法

是循环队列的特点及判断溢出的条件；利用队列的特点设计相关的应用问题。 4.教学内容（1）队列的定义与运算主要知识点：队列的定义；队列的特性；队列的应用实例。（2）队列的存储实现及运算的实现主要知识点：顺序队列的特点、顺序队列结构体类型的定义、顺序队列的基本运算；循环队列的特点、循环队列结构体类型的定义、循环队列的基本运算；链队列的特点、链队列结构体类型的定义、链队列的基本运算。（3）队列的应用举例主要知识点：队列在输入、输出管理中的应用；对 CPU 的分配管理；优先队列。第五章串 1.教学基本要求掌握串的逻辑结构、存储结构及其串上的基本运算，C 语言及其它高级语言均已具备了较强的串处理功能，掌握串上实现的模式匹配算法。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握串的有关概念及基本运算。串与线性表的关系，掌握串的两种存储表示。串上实现的模式匹配算法及其时间性能分析，使用高级程序设计语言提供的串操作函数构造与串相关的算法解决简单的应用问题。 3.教学重点和难点教学重点是串的有关概念和术语、串的基本运算、串的存储方法和串的模式匹配运算算法。教学难点是串的模式匹配运算算法。 4.教学内容（1）串的定义主要知识点：串的定义；串的相关术语：长度、空串、空格串、串相等、子串、主串、模式匹配；串的应用；串的输入输出；串的基本运算。（2）串的表示和实现主要知识点：定长顺序存储描述、存储方式；链接存储的描述；串的存储密度；大结点结构；串的堆分配存储结构；堆分配存储的方法；带长度索引表的描述。（3）串的基本运算主要知识点：串长度、求子串、串连接、串比较、插入子串、删除子串、模式匹配基本算法

第六章多维数组和广义表 1.教学基本要求掌握多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念， 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握多维数组的顺序存储结构及地址计算方式，多维数组的存储方式、特殊矩阵的压缩存储方式，稀疏矩阵的三元组表表示方法及有关算法，广义表的定义及其求表头和表尾的运算。 3.教学重点和难点教学重点是多维数组的逻辑结构和存储结构，特殊矩阵的压缩存储，稀疏矩阵的三元组存储，广义表的逻辑结构、存储结构。教学难点是十字链表存储。 4.教学内容 (1)多维数组主要知识点：多维数组的逻辑结构：多维数组的存储结构。 (2)特殊矩阵的压缩存储主要知识点：对称矩阵的特点及压缩存储方式：三角矩阵的特点及压缩存储方式。 (3)稀疏矩阵主要知识点：稀疏矩阵的三元组存储：稀疏矩阵的带行指针的链表存储：稀疏矩阵的十字链表存储。 (4)广义表主要知识点：广义表的定义、性质：广义表的首尾存储法。第七章树和二叉树 1.教学基本要求掌握二叉树的定义、性质、存储结构、遍历、线索化：树的定义、存储结构、遍历、树、森林与二叉树的转换：哈夫曼树及哈夫曼编码等内容，使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问愿。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握树的逻辑结构特征，二叉树的递归定义及树与二叉树的差别，二叉树的性质，二叉树的两种存储方法、特点及适用范围：二叉树的三种遍历算法，理解其执行过程，以遍历算法为基础，设计有关算法解决简单的应用问恩：二叉树线索化的目的及实质，中序线索树中查找给定结点的中序前趋和中序后继的方法：树和森林与二叉树之间的转换方法，树的各种存储结构及其特点。最优二叉树和最优前缀码的概念及特点，哈夫曼算法的思想

第六章多维数组和广义表 1.教学基本要求掌握多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念， 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握多维数组的顺序存储结构及地址计算方式，多维数组的存储方式、特殊矩阵的压缩存储方式，稀疏矩阵的三元组表表示方法及有关算法，广义表的定义及其求表头和表尾的运算。 3.教学重点和难点教学重点是多维数组的逻辑结构和存储结构，特殊矩阵的压缩存储，稀疏矩阵的三元组存储，广义表的逻辑结构、存储结构。教学难点是十字链表存储。 4.教学内容（1）多维数组主要知识点：多维数组的逻辑结构；多维数组的存储结构。（2）特殊矩阵的压缩存储主要知识点：对称矩阵的特点及压缩存储方式；三角矩阵的特点及压缩存储方式。（3）稀疏矩阵主要知识点：稀疏矩阵的三元组存储；稀疏矩阵的带行指针的链表存储；稀疏矩阵的十字链表存储。（4）广义表主要知识点：广义表的定义、性质；广义表的首尾存储法。第七章树和二叉树 1.教学基本要求掌握二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历、树、森林与二叉树的转换；哈夫曼树及哈夫曼编码等内容，使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握树的逻辑结构特征，二叉树的递归定义及树与二叉树的差别，二叉树的性质，二叉树的两种存储方法、特点及适用范围；二叉树的三种遍历算法，理解其执行过程，以遍历算法为基础，设计有关算法解决简单的应用问题；二叉树线索化的目的及实质，中序线索树中查找给定结点的中序前趋和中序后继的方法；树和森林与二叉树之间的转换方法，树的各种存储结构及其特点。最优二叉树和最优前缀码的概念及特点，哈夫曼算法的思想

3.教学重点和难点教学重点是树的基本概念与术语、二叉树及二叉树的存储结构、二叉树的遍历及线索二叉树、哈夫曼树及哈夫曼编码。教学难点是二叉树遍历算法的设计，利用二叉树遍历算法，解决简单应用问题，哈夫曼树的算法。 4.教学内容 (1)树的定义和术语主要知识点：树的定义：树的表示法：树的相关术语 (2)二叉树主要知识点：叉树的定义：二叉树的性质：二叉树的存储。 (3)遍历二叉树和线索二叉树主要知识点：二叉树的遍历：二叉树的恢复：线索二叉树方法及优点。 (4)二叉树的转换主要知识点：一般树转换为二叉树：森林转换为二叉树：二叉树转换为树和森林 (5)二叉树的应用主要知识点：二叉树的基本应用：标识符树与表达式。 (6)哈夫曼树及其应用主要知识点：哈夫曼树相关术语的定义及创建：哈夫曼编码：算法的实现。第八章图 1.教学基本要求掌握图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法，要求学生在熟悉这些内容的基础上，掌握在图的两种存储结构上实现的遍历算法，求最小生成树，求最短路径以及拓扑排序，同时要求学生掌握这些算法的基本思想及时间性能。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握图的逻辑结构特征，邻接矩阵和邻接表这两种存储结构的特点及适用范围，根据应用问题的特点和要求选择合适的存储结构：连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法，其执行过程以及时间分析：Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点：单源最短路径的Dijkstra算法的基本思想和时间性能：拓扑排序的基本思想和步骤。 3.教学重点和难点教学重点是图的逻辑结构及基本术语、邻接矩阵和邻接表的存储结构和特点，深度优先搜索和广度优先搜索两种遍历算法、图的连通性、最小生成树、最短路径的算法。教学难点是图的遍历、最小生成树、最短路径。 4.教学内容

3.教学重点和难点教学重点是树的基本概念与术语、二叉树及二叉树的存储结构、二叉树的遍历及线索二叉树、哈夫曼树及哈夫曼编码。教学难点是二叉树遍历算法的设计，利用二叉树遍历算法，解决简单应用问题，哈夫曼树的算法。 4.教学内容（1）树的定义和术语主要知识点：树的定义；树的表示法；树的相关术语。（2）二叉树主要知识点：叉树的定义；二叉树的性质；二叉树的存储。（3）遍历二叉树和线索二叉树主要知识点：二叉树的遍历；二叉树的恢复；线索二叉树方法及优点。（4）二叉树的转换主要知识点：一般树转换为二叉树；森林转换为二叉树；二叉树转换为树和森林。（5）二叉树的应用主要知识点：二叉树的基本应用；标识符树与表达式。（6）哈夫曼树及其应用主要知识点：哈夫曼树相关术语的定义及创建；哈夫曼编码；算法的实现。第八章图 1.教学基本要求掌握图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法，要求学生在熟悉这些内容的基础上，掌握在图的两种存储结构上实现的遍历算法，求最小生成树，求最短路径以及拓扑排序，同时要求学生掌握这些算法的基本思想及时间性能。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握图的逻辑结构特征，邻接矩阵和邻接表这两种存储结构的特点及适用范围，根据应用问题的特点和要求选择合适的存储结构；连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法，其执行过程以及时间分析；Prim 和 Kruskal 算法的基本思想、时间性能及这两种算法各自的特点；单源最短路径的 Dijkstra 算法的基本思想和时间性能；拓扑排序的基本思想和步骤。 3.教学重点和难点教学重点是图的逻辑结构及基本术语、邻接矩阵和邻接表的存储结构和特点，深度优先搜索和广度优先搜索两种遍历算法、图的连通性、最小生成树、最短路径的算法。教学难点是图的遍历、最小生成树、最短路径。 4.教学内容

(1)图的定义和术语主要知识点：图的定义：图的相关术语：图的基本操作 (2)图的存储表示主要知识点：邻接矩阵：邻接表。 (3)图的遍历主要知识点：深度优先搜索：广度优先搜索：有向图的十字链表存储结构。 (4)图的连通性主要知识点：无向图的连通分量和生成树：普里姆算法求最小生成树：克鲁斯卡尔算法求最小生成树。 (5)最短路径主要知识点：迪杰斯特拉算法第九章查找 1.教学基本要求掌握顺序查找、二分查找，二叉查找树上查找、二叉平衡树以及散列表上查找的基本思想和算法实现。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握查找在数据处理中的重要性：查找算法效率的评判标准，顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析，顺序查找中哨兵的作用：二分查找对存储结构及关键字的要求，通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法：二叉查找树的特点、用途，二叉查找树的插入、删除、建树和查找算法及时间性能以及二叉平衡树的调整方法，散列函数的选取原则及产生冲突的原因，几种常用的散列函数构造方法，两类解决冲突的方法及其优缺点。 3.教学重点和难点教学重点是查找的基本概念、二分查找、分块查找、二叉排序树查找、哈希函数和解决冲突的方法。教学难点是二叉排序树查找、平衡二叉树。 4.教学内容 (1)查找的基本概念主要知识点：查找、静态查找、动态查找、关键字、主关键字、内查找和外查找、平均查找长度ASL等概念 (2)静态查找表主要知识点：顺序查找：基本思路、算法、性能分析：二分查找的基本思路、算法、性能分析：分块查找的基本思路、算法、性能分析。 (3)动态查找表

（1）图的定义和术语主要知识点：图的定义；图的相关术语；图的基本操作。（2）图的存储表示主要知识点：邻接矩阵；邻接表。（3）图的遍历主要知识点：深度优先搜索；广度优先搜索；有向图的十字链表存储结构。（4）图的连通性主要知识点：无向图的连通分量和生成树；普里姆算法求最小生成树；克鲁斯卡尔算法求最小生成树。（5）最短路径主要知识点：迪杰斯特拉算法第九章查找 1.教学基本要求掌握顺序查找、二分查找，二叉查找树上查找、二叉平衡树以及散列表上查找的基本思想和算法实现。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握查找在数据处理中的重要性；查找算法效率的评判标准，顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析，顺序查找中哨兵的作用；二分查找对存储结构及关键字的要求，通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法；二叉查找树的特点、用途，二叉查找树的插入、删除、建树和查找算法及时间性能以及二叉平衡树的调整方法，散列函数的选取原则及产生冲突的原因，几种常用的散列函数构造方法，两类解决冲突的方法及其优缺点。 3.教学重点和难点教学重点是查找的基本概念、二分查找、分块查找、二叉排序树查找、哈希函数和解决冲突的方法。教学难点是二叉排序树查找、平衡二叉树。 4.教学内容（1）查找的基本概念主要知识点：查找、静态查找、动态查找、关键字、主关键字、内查找和外查找、平均查找长度 ASL 等概念。（2）静态查找表主要知识点：顺序查找：基本思路、算法、性能分析；二分查找的基本思路、算法、性能分析；分块查找的基本思路、算法、性能分析。（3）动态查找表

主要知识点：二叉排序树的定义、插入、删除、查找、查找分析：平衡二叉排序树的定义和调整 (4)哈希表主要知识点：哈希表与哈希方法：哈希函数的构造方法：直接定址法、除留余数法、平方取中法：处理冲突的方法：开放定址法、拉链法。第十章排序 1.教学基本要求掌握插入排序、快速排序、堆排序、归并排序这四类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握排序方法的“稳定“性含义，排序方法的分类及算法好坏的评判标准：掌握直接插入排序、冒泡排序中的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析：直接插入排序中哨兵的作用，能够针对给定的输入实例，要能写出它们的排序过程：掌握直接选择排序、堆排序、归并排序的基本思想和算法实现，以及时间性能分析。针对给定的输入实例，写出该排序的排序过程。 3.教学重点和难点教学重点是排序的基本概念、二分插入排序、快速排序、堆排序。教学难点是堆排序快速排序。 4.教学内容 (1)概述主要知识点：排序、内排序、外排序等相关概念。 (2)插入排序主要知识点：直接插入排序的基本思想、算法、效率分析：二分插入排序的基本思想、算法、效率分析：希尔排序的基本思想、算法、效率分析。 (3)快速排序主要知识点：目泡排序的基本思想、算法、效率分析：快速排序的基本思想、算法、效率分析。 (4)选择排序主要知识点：简单选择排序的基本思想、算法、效率分析：树形选择排序的基本思想、效率分析：堆排序的基本思想、算法、效率分析。 (5)归并排序主要知识点：归并排序的基本思想、算法、效率分析。第六节各种排序方法的比较

主要知识点：二叉排序树的定义、插入、删除、查找、查找分析；平衡二叉排序树的定义和调整。（4）哈希表主要知识点：哈希表与哈希方法；哈希函数的构造方法：直接定址法、除留余数法、平方取中法；处理冲突的方法：开放定址法、拉链法。第十章排序 1.教学基本要求掌握插入排序、快速排序、堆排序、归并排序这四类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。 2.要求学生掌握的基本概念、理论、技能通过本章的学习，掌握排序方法的"稳定"性含义，排序方法的分类及算法好坏的评判标准；掌握直接插入排序、冒泡排序中的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析；直接插入排序中哨兵的作用，能够针对给定的输入实例，要能写出它们的排序过程；掌握直接选择排序、堆排序、归并排序的基本思想和算法实现，以及时间性能分析。针对给定的输入实例，写出该排序的排序过程。 3.教学重点和难点教学重点是排序的基本概念、二分插入排序、快速排序、堆排序。教学难点是堆排序、快速排序。 4.教学内容（1）概述主要知识点：排序、内排序、外排序等相关概念。（2）插入排序主要知识点：直接插入排序的基本思想、算法、效率分析；二分插入排序的基本思想、算法、效率分析；希尔排序的基本思想、算法、效率分析。（3）快速排序主要知识点：冒泡排序的基本思想、算法、效率分析；快速排序的基本思想、算法、效率分析。（4）选择排序主要知识点：简单选择排序的基本思想、算法、效率分析；树形选择排序的基本思想、效率分析；堆排序的基本思想、算法、效率分析。（5）归并排序主要知识点：归并排序的基本思想、算法、效率分析。第六节各种排序方法的比较

点击进入文档下载页（PDF格式）

已到末页，全文结束

点击下载（PDF格式）

浏览记录