数据结构教学大纲

XX师范学院大学本科专业教学大纲中文课程名称：数据构造英文课程名称：DataStructures合用专业：信息管理与信息系统制订单位：商学院执笔人：审核人：单位负责人：制订时间：-2-10XX师范学院教务处一月《数据构造》课程教学大纲一、课程基本信息（一）课程代码及课程名称1.课程代码：061510902.课程名称（中/英文）：数据构造/DataStructures（二）课程类别及课程性质专业教育必修课程（三）学时及学分：总学时数：64；总学分数：3。其中，讲授学时：32，实践（实验）学时：32。（四）合用专业及开设学期合用专业：信息管理与信息系统（本科）开设学期：第二学期（五）先修课程与后续课程先修课程：大学计算机基础、高等数学、C语言程序设计后续课程：数据库原理与应用、管理信息系统分析与设计、管理信息系统、Java程序设计(高级)二、课程介绍“数据构造”是信息管理与信息系统专业一门重点专业基础课程，也是学科专业核心专业基础课程之一，属于专业学位必修课程。本课程的教学任务是针对大量的信息解决对象，介绍对象信息与数据表达的多个抽象的、基本的逻辑构造及其上的基本运算操作。通过研究多个基本数据构造内在的逻辑关系和它们在计算机中的存储表达方式，初步建立数据构造上基本运算操作的对的性概念，同时，结合多个典型问题讨论其上的多个基本运算操作及其基本算法，讲授多个数据构造的特点、合用范畴，以及对某些基本算法效率的定性和定量分析办法，为后续课程提供必要的数据构造基础。另外，配合实验课程的教学中，学生应理论联系实际，理论指导实践，通过规范地完毕一系列数据构造实验进一步巩固所学的有关课本知识，在知识、能力、素质上得到进一步的提高。三、教学目的与基本规定（一）该课程教学目的与专业培养规定对应关系矩阵培养规定课程名称培养规定1培养规定2培养规定3培养规定4培养规定5培养规定6培养规定7培养规定8培养规定9培养规定数据构造●●◎●●◎●●◎○阐明：表格要清晰展示该课程与每项培养规定达成的关联度状况，关联度强的用“●”标记，关联度中档的用“◎”标记，关联度弱的用“○”标记；每门课程与4-8项（底线为总培养规定的50%）培养规定有关联。（二）教学目的《数据构造A》在计算机科学中是一门综合性的专业基础课，不仅是普通程序设计的基础，并且是设计和实现操作系统、数据库系统、编译程序及其它系统程序和大型应用程序的重要基础。本课程讨论多个数据组织中的数据的逻辑构造、存储构造以及有关操作的算法。目的是使学生学会分析研究计算机所要加工解决的数据的特性，掌握组织数据、存储数据和解决数据的基本办法，并加强在实际应用中选择适宜的数据构造和设计对应算法的训练，课程的具体教学目的以下：数据构造与算法是计算机科学教育中的一门核心课程。数据构造与算法重要讨论在应用计算机解决问题时，如何有效地组织数据、表达数据和解决数据，以及如何设计对的的算法和评价算法的效率。课程介绍常见的数据构造及其应用，惯用的数据解决技术和算法，以及算法效率估算的基本技术。通过本课程的学习，学生应当掌握惯用的数据构造，掌握合理地组织数据构造和表达数据的办法，掌握有效地解决数据的办法，掌握评价算法性能的基本办法。通过本课程的训练，进一步提高学生的数据抽象能力；提高学生设计高质量程序的能力。本课程也为学生学习操作系统、编译原理和数据库等后续课程奠定基础。1.知识方面1.1理解数据构造的某些基本概念、理解并掌握算法的描述办法，理解并掌握算法的时间复杂度和空间复杂度的概念以及分析办法。1.2理解多个数据构造的基本概念，深刻理解多个数据构造的逻辑特性，理解并纯熟掌握多个数据构造的存储表达办法，理解并掌握在多个数据构造基础上的算法设计与描述，并理解和掌握对算法性能进行分析的办法以及分析成果。1.3理解查找、排序的基本概念，掌握多个查找、排序办法及其算法描述和性能分析办法和分析成果。2.能力与素质方面2.1含有根据工程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能力。2.2含有为解决工程实际问题进行算法设计与分析的能力。2.3含有将算法通过具体的编程语言加以实现的能力。（三）教学规定：通过本课程的学习，在基础方面，规定学生能够掌握惯用数据构造的基本概念及其不同的实现办法；在技能方面，通过系统学习能够在不同存储构造上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全方面的掌握多个惯用的数据构造，提高运用数据构造解决实际问题的能力。1.掌握数据构造的概念及术语。2.掌握线性表（栈、队列）的存储构造（次序和链式存储）、算法描述及应用。3.掌握数组的次序存储和特殊矩阵的压缩存储。4.掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储构造及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。5.掌握图的基本概念和术语、存储构造（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。6.掌握查找的基本概念、基于线性表的查找办法（次序、折半）。7.掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。四、教学内容（一）绪论（共4学时）（一）教学目的和规定介绍数据构造课程的研究对象，基本术语，掌握算法的要领，描述算法的类语言。理解数据构造的发展概况及其在计算机中的地位。（二）教学重点与难点教学重点：1、熟悉各名词、术语的含义，特别是数据的逻辑构造和存储构造之间的关系。分清哪些是逻辑构造的性质，哪些是存储构造的性质；2、理解抽象数据类型的定义、表达和实现办法；3、理解算法五个要素确实切含义：①动态有穷性（能执行结束）；②拟定性（对于相似的输入执行相似的途径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）；4、掌握计算语句频度和估算算法时间复杂度的办法。教学难点：1、掌握数据构造的意义及数据构造的基本内容；2、掌握数据构造及数据、数据元素等有关概念；3、掌握算法描述的办法；4、算法时间复杂度的计算。（三）教学内容1、什么是数据构造2、基本概念和术语3、抽象数据类型的表达与实现4、算法和算法分析（二）线性表（共8学时）（一）教学目的和规定掌握线性表的逻辑构造、次序存储构造和链式存储构造。掌握在线性表上实现基本运算的算法。（二）教学重点与难点教学重点：1、线性表的定义及逻辑上的特点；2、次序表上插入、删除和定位运算的实现；3、单链表的构造特点及类型阐明；4、头指针和头结点的作用及区别；指针操作；5、定位、删除、插入运算在单链表上的实现；6、循环链表、双链表的构造特点；及其删除与插入运算的实现。教学难点：1、线性表与线性构造的联系与区别；2、线性表的次序存储构造及其运算；3、头结点在链表中的作用和指针的操作；4、单链表存储构造定义，删除、插入运算中的指针操作次序；5、单链表的基本运算的实现；6、循环链表、双链表上指针的操作次序及其有关运算。（三）教学内容1、线性表的类型定义2、线性表的次序表达和实现3、线性表的链式表达和实现4、一元多项式的表达及相加（三）栈和队列（共8学时）（一）教学目的和规定掌握栈和队列的逻辑构造定义，掌握在两种存储构造上如何实现栈和队列的基本运算，掌握栈在程序设计中的应用。（二）教学重点与难点教学重点：1、栈的定义及逻辑特点；栈上的基本运算；2、栈的次序存储构造及运算实现；链式存储构造；3、入栈、出栈等运算在链栈上的实现；4、队列的定义及逻辑特点；队列上的基本运算；5、队列的次序存储构造及其上的运算实现；6、队列的链式存储构造；7、入队、出队等运算在链队列上的实现。教学难点：1、次序栈基本运算的实现；2、次序栈的溢出判断条件；3、栈的应用；4、循环队列的队空、队满判断条件；循环队列上的插入、删除操作。（三）教学内容1、栈的类型定义2、栈的应用举例3、栈与递归的实现4、队列的类型定义（四）串和数组（共8学时）（一）教学目的和规定掌握字符串的存储构造，以及字符串的操作算法，掌握数组的次序存储和特殊矩阵的压缩存储。（二）教学重点与难点教学重点：1、熟悉串的定义及串的基本操作；2、串的两种存储方式；3、字符串的运算；4、串的模式匹配算法。5、多维组的逻辑构造，两种次序存储方式；6、计算给定元素在存储区中的地址；7、对称矩阵、三角矩阵的压缩存储方式；8、计算给定元素在存储区中的地址；9、稀疏矩阵的三元组表表达办法；教学难点：1、串的基本运算的综合应用；2、串的模式匹配算法。3、理解数组的两种存储表达办法，并掌握数组在以行为主的存储构造中的地址计算办法；4、稀疏矩阵的压缩存储表达下的运算的实现；5、理解稀疏矩阵的三类压缩存储办法的特点和合用范畴，领略以三元组表达稀疏矩阵时进行矩阵运算采用的解决办法；（三）教学内容1、栈的类型定义2、栈的应用举例3、栈与递归的实现4、队列的类型定义5、数组的定义6、数组的次序表达和实现7、矩阵的压缩存储（五）树和二叉树（共12学时）（一）教学目的和规定掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储构造及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。（二）教学重点与难点教学重点：1、二叉树的定义、性质、逻辑特点及五种基本形态、基本运算；2、二叉树的链式存储构造、次序存储构造及其类型阐明；3、二叉树链式存储构造的组织方式；4、二叉树的三种遍历办法及其算法，以遍历为基础在二叉树上实现的几个运算；5、哈夫曼树和哈夫曼算法；森林与二叉树的转换。教学难点：1、二叉树的递归定义；2、二叉树链式存储构造的组织方式；3、三种遍历的重要区别；二叉树上的复杂运算4、森林与二叉树的转换；5、哈夫曼算法及其应用。（三）教学内容1、树的定义和基本术语2、二叉树3、遍历二叉树和线索二叉树4、树和森林5、回溯法与树的遍历6、赫夫曼树及其应用（六）图（共8学时）（一）教学目的和规定掌握图的基本概念和术语、存储构造（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。理解拓扑排序及核心途径和最短途径的应用及意义。（二）教学重点与难点教学重点：1、理解图的定义、术语及其含义，多个图的邻接矩阵表达法及其类型阐明；2、理解并掌握图的按深度优先搜索遍历办法和按广度优先搜索遍历办法；3、领略生成树和最小生成树的概念；4、掌握由Prim算法思想构造最小生成树按Prim算法思想；5、掌握拓扑序列和拓扑排序的概念，拓扑排序、核心途径、最短途径的算法思想。教学难点：1、对的理解与区别图的惯用术语；2、区别图的两种存储构造的不同点及其应用场合；3、核心途径的算法思想；最短途径的算法思想。（三）教学内容1、图的定义和术语2、图的存储构造3、图的遍历4、图的连通性问题5、有向无环图及其应用6、最短途径（七）查找（共8学时）（一）教学目的和规定掌握查找的基本概念、基于线性表的查找办法（次序、折半）。理解基于树的查找办法（二叉排序树、平衡二排序叉树）。（二）教学重点与难点教学重点：1、查找表的基本概念及查找原理；次序存储构造、次序表及其类型阐明；2、查找运算在查找表和有序表上的实现；3、二叉排序树的定义、性质及各结点间的键值关系，查找算法和基本思想；4、平衡二叉排序树的概念；B-树和B+树的概念；5、散列表及散列存储和散列查找的基本思想；多个散列表的组织、解决冲突的办法；教学难点：1、理解查找表的逻辑构造是集合，它的运算以查找为核心；2、二叉排序树上的插入算法；平衡二叉树的旋转平衡算法；3、散列表上的有关算法。（三）教学内容1、静态查找表2、动态查找表3、哈希表（八）排序（共8学时）（一）教学目的和规定掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。理解选择类排序、归并类排序和基数类排序。（二）教学重点与难点教学重点：1、排序基本概念及内排序和外排序、稳定排序和非稳定排序的区别；2、插入排序、冒泡排序、快速排序、直接选择排序、堆排序的基本思想、基本环节和算法；3、归并排序的思想；两个有序文献合并的办法和算法；4、二路归并排序的算法和时空性能；教学难点：1、快速排序算法；2、堆排序办法。（三）教学内容1、插入排序2、快速排序3、选择排序4、归并排序5、基数排序6、多个内部排序办法的比较讨论五、教学时数分派《数据构造》课程教学时数分派表总学时：64学分：3章次章标题名称学时小计讲授学时实验学时实践学时讨论、习题课等学时第一章绪论422第二章线性表8341第三章栈和队列8341第四章串和数组844第五章树和二叉树12462第六章图8341第七章查找8341第八章排序8341六、实验内容与学时分派《数据构造》课程实验教学一览表序号项目名称内容提纲学时实验类型（演示、验证、综合、设计等）开放1一元二次方程求解复习函数定义，函数调用和参数传递及有关知识。2验证否2线性表的操作建立次序表及链表，并完毕查找、插入、删除操作。4验证否3栈与队列的应用运用栈完毕括号匹配，运用队列模拟病人看病。4设计否4二叉树的遍历及应用运用二叉链表办法建立二叉树，实现二叉树的前、中、后序三种遍历算法。并运用遍历算法实现二叉树的其它操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等。10验证否5查找算法设计与实现选择两种查找算法实现查找并比较。6验证否6排序算法设计与实现选择两种排序算法实现排序并比较。6验证否七、本课程的实践环节八、重要的教学办法与教学手段1.课程与教学办法、教学手段对应关系矩阵课程名称对应的教学方式办法讲授法启发式讨论法案