《数据结构》课程教学大纲

《数据结构》课程教学大纲课程编号：课程名称（中文）：数据结构课程名称（英文）：DataStructures适用专业：计算机科学与技术学分：3.5开设学期：第3学期总学时：64（授课学时：56上机学时：0实验学时：8）先修课程：程序设计基础、面向对象程序设计、离散数学后续课程：算法分析与设计、数据库原理及应用、操作系统课程简介本课程是为计算机科学与技术技术专业本科生开设的一门专业基础必修课。本课程的任务是培养学生掌握基本的数据结构，算法的基本概念、设计策略和分析方法，使学生通过本课程的学习和实践能够学会针对具体的问题，选择适当的数据结构，设计出有效的算法。本课程的主要教学内容包括：数据结构的逻辑结构、如何使用数据结构的存储结构实现逻辑结构及基本操作、如何评价确定存储结构下操作实现的性能。具体内容包括数据结构的相关概念和作用，泛型及实现方法；算法的概念、基本性质和设计原则，以及算法的时间和空间复杂度分析方法；线性表的逻辑结构、顺序和链式存储结构及基本操作的实现；栈与队列的逻辑结构、存储结构和基本操作的实现及其应用；二叉树的基本概念、基本性质和存储结构，二叉树的遍历方法及应用，树和森林的存储结构和遍历方法及与二叉树的关系，哈夫曼树和哈夫曼编码；图的基本概念，图的存储结构和基本操作的实现，图的遍历、最小生成树、拓扑排序和最短路径；静态查找和动态查找以及哈希表的思想及实现方法；各种内部排序算法的设计思想和分析方法。本课程主要侧重于如何使用数据结构的存储结构实现逻辑结构和基本操作以及操作实现性能分析的讲解，其中算法的概念、基本性质和设计原则，以及算法的时间和空间复杂度分析方法是《算法分析与设计》课程的基础；为了实现数据库，通常需要使用很多数据结构，如使用B+树做索引等；数据结构是操作系统中使用的一种工具，比如链表、栈、队列、树、图等都是常见的数据结构，它们可以用来实现各种功能，如进程控制块、缓冲区、路由表等。课程教学目标课程目标通过本课程教学，应达到以下目标：课程目标1:记忆数据结构的基本概念；掌握线性表、栈和队列、树和二叉树，图等各种基本数据结构的逻辑结构、物理（存储）结构及其基本操作的实现，掌握查找和排序的经典算法，记忆算法的基本概念、特点、设计原则，理解算法的时间复杂度和空间复杂度的分析方法。课程目标2:运用数据结构基本理论，分析具体应用问题和不同解决方案的利弊，建立准确的问题模型，选择合理的数据结构及其存储结构，设计出有效的算法，并对其进行分析和评价。课程目标3:理解泛型和异常处理的应用，掌握面向对象程序设计方法和创新方法，能够编写结构清晰、正确易读、移植性较好且效率高的程序，并解决实际问题。课程目标对毕业要求的支撑表2.1课程目标对毕业要求支撑表毕业要求二级指标点课程目标支撑强度建议占比1.工程知识：能够将数学、自然科学、工程基础和专业知识用于解决计算机应用领域复杂工程问题。1.2能够针对计算机应用领域具体工程问题建立数学模型，并对其求解。1H30%~40%2.问题分析：能够运用数学、自然科学和工程科学的基本原理和计算机科学与技术专业知识，识别、表达、并通过文献研究分析计算机应用领域复杂工程问题，以获得有效结论。2.1能够应用数学、自然科学和计算机科学与技术专业的基本原理对复杂工程问题进行分解,指出关键环节。2H30%~35%3.设计/开发解决方案：能够设计针对计算机应用领域复杂工程问题的解决方案，设计满足特定需求的计算机应用系统，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。3.1掌握计算机应用领域复杂工程问题的相关设计开发方法，了解影响设计目标和技术方案的各种因素。3L30%~35%课程教学内容的基本要求、重点和难点及学时分配（一）课程内容结构说明本课程的主要内容包括12部分，由8部分理论授课和4部分实验授课环节构成。具体教学内容、教学环节和课程目标的对应关系，如表3.1所示。表3.1教学内容、教学环节和课程目标对应关系表编号教学内容教学环节课程目标1绪论授课：2学时课程目标1、32算法和算法分析授课：2学时课程目标23线性表授课：6学时课程目标1、2、34栈和队列授课：6学时课程目标1、25树与二叉树授课：14学时课程目标1、2、36图授课：12学时课程目标1、2、37查找授课：8学时课程目标1、2、38排序授课：6学时课程目标1、2、3授课学时合计：56（二）课程教学内容的基本要求、重点和难点1.绪论（2学时）（支撑课程目标1、3）教学内容：数据结构的概念；数据的逻辑结构；数据的存储结构；Java泛型。重点和难点：数据结构的逻辑结构和存储结构，泛型及实现方法。学习成果：理解数据结构的相关概念和作用；记忆逻辑结构和存储结构的特点及区别；掌握泛型及实现方法。教学形式教学方法：讲授新课+课堂讨论2.算法和算法分析（2学时）（支撑课程目标2）教学内容：(1)算法的概念；(2)算法的特性；(3)算法的设计原则；(4)算法的分析；(5)算法的时间复杂度分析。重点和难点：算法的时间复杂度分析。学习成果：理解算法的概念、基本性质和设计原则，掌握算法的时间复杂度分析方法,了解空间复杂度分析方法。教学形式教学方法：复习+讲授新课+课堂讨论3.线性表（6学时）（支撑课程目标1、2、3）教学内容：(1)线性表的相关概念；(2)线性表的抽象数据类型定义；(3)线性表的顺序存储结构及其实现；(4)线性表的链式存储结构及其实现；(5)单链表的定义及实现；(6)双向链表的定义及实现；(7)双向循环链表的定义及实现。重点和难点：线性表的链式存储结构，基本操作边界条件的检查。学习成果：掌握线性表的逻辑结构、存储结构和基本操作的实现。教学形式教学方法：复习+讲授新课+课堂讨论4.栈与队列（6学时）（支撑课程目标1、2）教学内容：(1)栈的定义及特点；(2)栈的顺序结构及其实现；(3)栈的链式结构及其实现；(4)栈的应用；(5)队列的定义及特点；(6)循环队列的实现；(7)队列的链式结构及其实现；(8)优先队列。重点和难点：栈与队列的存储结构，循环队列的实现方法，递归程序设计。学习成果：掌握栈与队列的逻辑结构、存储结构和基本操作的实现及其应用，理解递归的含义和实现过程，掌握递归程序设计的基本思想。教学形式教学方法：复习+讲授新课+课堂讨论5.树与二叉树（14学时）（支撑课程目标1、2、3）教学内容：(1)树的定义、相关概念和表示方法；(2)二叉树的定义和基本性质；(3)二叉树的顺序存储结构；(4)二叉树的链式存结构；(5)二叉树的遍历及应用；(6)森林的定义和相关概念；(7)树、森林和二叉树之间的对应关系及转换；(8)哈夫曼树的定义、哈夫曼树的构造方法和哈夫曼编码；重点和难点：二叉树的遍历，树和森林与二叉树的关系，哈夫曼树和哈夫曼编码。学习成果：理解树和二叉树的基本概念，掌握二叉树的基本性质和存储结构；掌握二叉树的遍历方法及应用，掌握树和森林的存储结构和遍历方法及与二叉树的关系；掌握哈夫曼树和哈夫曼编码。教学形式教学方法：复习+讲授新课+课堂讨论6.图（12学时）（支撑课程目标1、2、3）教学内容：(1)图的定义及其相关术语；(2)图的存储结构定义及实现；(3)图的遍历及生成树；(4)最小生成树的概念及构造最小生成树的Kruskal算法和Prim算法；(5)最短路径的概念及计算最短路径的Dijkstra算法和Floyd算法。(6)拓扑排序的概念及拓扑排序算法。重点和难点：图的存储结构和遍历，最小生成树、拓扑排序和最短路径。学习成果：理解关于图的基本概念，掌握图的存储结构和基本操作的实现，掌握图的遍历、最小生成树、拓扑排序和最短路径。教学形式教学方法：复习+讲授新课+课堂讨论7.查找（8学时）（支撑课程目标1、2、3）教学内容：(1)查找的概念及分类；(2)静态查找和动态查找；(3)二叉排序树的定义、实现及平均查找长度性能分析；(4)平衡二叉树的定义、实现及平均查找长度性能分析；(5)哈希表的相关定义、构造方法及查找性能分析；重点和难点：二叉排序树和二叉平衡树基本操作的实现，哈希函数的确定和解决冲突的方法。学习成果：理解静态查找和动态查找的基本思想，掌握二叉排序树的定义和基本操作的实现；掌握二叉平衡树的定义和基本操作的实现；掌握哈希表的定义、哈希函数的确定和解决冲突的方法。教学形式教学方法：复习+讲授新课+课堂讨论8.排序（6学时）（支撑课程目标1、2、3）教学内容：(1)排序的概念及分类；(2)插入类排序算法：直接插入排序和希尔排序；(3)交换类排序算法：冒泡排序和快速排序；(4)交换类排序算法：直接选择排序和堆排序；(5)归并排序；(6)基数排序；重点和难点：排序算法的分类、分析和比较。学习成果：通过学习，使学生掌握各种内部排序算法的设计思想和分析方法，能根据需要选用合适的算法。教学形式教学方法：复习+讲授新课+课堂讨论9.实验教学（8学时）本课程安排8学时的实验，每个实验2个学时，共4次实验，包括：单循环链表的基本操作、二叉树的遍历、图的基本操作、折半查找和二叉排序树。（1）实验教学必需的保障条件实验室应具备一定数量的计算机，安装了相关的编程工具软件。（2）实验项目、实验内容与学时安排实验名称、内容与学时的分配，如表3.2所示。表3.2实验名称、内容与学时分配表序号实验项目名称内容提要学时项目类型课程教学目标1单循环链表的基本操作采用链式存储结构，实现线性表的插入、删除、取元素、移动最小值等操作。2设计型课程目标22二叉树的遍历二叉树的创建及先序、中序和后序遍历及应用。2设计型课程目标33图的基本操作图的创建及在确定的存储结构下求顶点的度、求邻接点、顶点和边的插入、删除等操作；图的深度优先和广度优先遍历。2设计型课程目标34折半查找和二叉排序树折半查找算法，二叉排序树的创建、插入、删除、查找等操作的实现。2设计型课程目标2实验一：单循环链表的基本操作（2学时，支撑课程目标2）实验内容：定义单循环链表类型并动态创建使用tail指向尾结点的单循环链表（有头结点）。实现单循环链表的取元素、插入、删除、索引元素位置号等操作以及迭代器。实现输出单循环链表中各元素值的操作；将单循环链表中的最小元素移到最前面。重点与难点：实现单循环链表的取元素、插入、删除、索引元素位置号等操作以及迭代器。学习成果：通过本实验使学生熟悉线性表的应用，掌握线性链表的操作特点，熟练掌握单循环链表基本操作的实现过程，掌握动态产生带尾指针的单循环链表的方法，熟悉程序代码，并能够独立撰写实验报告。培养学生编程灵活控制链表的能力，为今后编程控制更为复杂的数据结构奠定基础。实验二：二叉树的遍历（2学时，支撑课程目标3）实验内容：用先序方法建立一棵二叉树。实现输出二叉树先序、中序和后序遍历序列中第k个数据元素的操作。实现判断二叉树是否是完全二叉树的操作。重点与难点：输出二叉树先序、中序和后序遍历序列，判断二叉树是否是完全二叉树。学习成果：通过本实验使学生熟悉二叉树遍历的各种算法；掌握采用递归实现二叉树遍历算法的方法；深刻理解栈在递归中的作用；掌握二叉树的特点及其存储方式；掌握二叉树的创建；掌握二叉树先序、中序、后序遍历的基本方法及应用；掌握判断二叉树是否是完全二叉树的方法，并能够独立撰写实验报告。培养学生在编程上控制树的结构的能力，为今后控制更为复杂的数据结构奠定基础。实验三：图的基本操作（2学时，支撑课程目标3）实验内容：分别定义图的邻接矩阵和邻接表存储结构。分别在两种存储结构下根据输入的顶点和边（或弧）创建图。分别在两种存储结构下实现求顶点度的操作。分别在两种存储结构下实现图的深度和广度优先遍历算法。实现图的邻接矩阵和邻接表存储结构的转换。重点与难点：在两种存储结构下实现图的深度和广度优先遍历算法。学习成果：通过本实验使学生熟悉图遍历的两种方法：深度优先与广度优先；掌握编程实现图遍历具体算法；熟练掌握图的顺序存储（邻接矩阵）与链式存储（邻接链表）的特性；掌握图的创建方法；掌握求顶点度的方法；掌握图的深度优先和广度优先遍历方法；掌握图的邻接矩阵和邻接表存储结构的转换，并能够独立撰写实验报告。培养学生在编程上控制复图的结构的能力，为进而解决有一定难度的复杂问题奠定基础。实验四：折半查找和二叉排序树（2学时，支撑课程目标2）实验内容：设有关键字序列k={5,14,18,21,23,29,31,35}，请找出小于29的最大关键字值是什么。根据关键字序列{45、24、53、12、37、93}构造二叉排序树，并完成插入13删除关键字53和24的操作。重点与难点：二叉排序树的插入、删除操作。学习成果：掌握查找的特点；掌握折半查找的基本思想及其算法；熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作，并能够独立撰写实验报告。培养学生在编程上灵活使用多种查找和排序方法的能力，为进而解决复杂问题而奠定基础。四、课程考核与成绩评定课程成绩评定以考核学生能力培养目标的达成为主要目的，以检查学生对各知识点的掌握程度和应用能力为重要内容。课程成绩评定采取过程考核和期末考试相结合的方式综合评定，过程考核成绩、期末考试成绩及总评成绩均为百分制。课程考核成绩构成课程考核成绩构成：过程考核成绩占40%，期末考试（闭卷）成绩占60%。过程考核过程考核含平时成绩（占总成绩的30%）和实验成绩（占总成绩的10%）。平时成绩主要采用作业的形式进行评价。实验成绩的考核可通过实验设计的合理度、实验报告的质量、实验结果的正确度等综合评定。期末考试考核形式：闭卷考试。考核内容：支撑课程目标1-3试题类型：要求采用多种试题类型，比如：选择题、理解论述题、综合分析题等。其中，主观题不少于60%。考核目的：客观题主要考核学生对课程重要知识点、关键技术细节的理解与掌握情况，灵活运用所学知识分析问题的能力。主观题主要考核学生是否能灵活运用所学知识，理解并分析实际应用中的复杂问题；考核学生对数据结构理论知识、技术和方法的综合分析和应用能力。（二）考核评价方式与课程目标的支撑关系课程考核评价方式与课程目标的支撑关系，如表4.1所示。表4.1考核评价方式与课程目标支撑关系表考核方式支撑课程目标评价方式学习结果载体平时成绩实验成绩期末考试成绩过程考核课程目标1课程目标2课程目标3√作业课程目标2课程目标3√实验报告期末考试成绩课程目标1课程目标2课程目标3√期末考试卷（三）考核方式与比例课程目标达成考核与评价方式及成绩评定的对照，如表4.2所示。表4.2考核与评价方式及成绩评定对照表课程目标考核与评价方式及成绩比例（%）成绩建议比例（100%）平时成绩（30%）课程实验（10%）期末考试（60%）课程目标140-4036课程目标230503032课程目标330503032合计100100100100（三）课程目标评价方式及评价标准课程目标评价方式及评价标准，如表4.3所示。表4.3课程目标评价方式及评价标准课程目标考核方式课程目标评价标准优秀良好合格（达成）不合格课程目标1平时成绩按时提交作业；对线性表、树、图、查找、排序等相关基本原理、概念理解完全正确，论述逻辑清楚；层次分明。按时提交作业；对线性表、树、图、查找、排序等相关基本原理、概念理解比较准确，论述逻辑比较清楚。基本能够按时提交作业；对线性表、树、图、查找、排序等相关基本原理、概念理解基本正确。不交作业；论述逻辑混乱；作业存在有严重的抄袭现象。期末考试对数据结构相关概念理解正确；能准确的利用数据结构的相关算法对问题进行分析求解。对数据结构相关概念理解比较正确；能比较准确的利用数据结构的相关算法对问题进行分析求解。对数据结构相关概念理解基本正确；能基本准确的利用数据结构的相关算法对问题进行分析求解。对数据结构相关概念理解完全错误；根本不能利用数据结构的相关算法对问题进行分析求解。课程目标2平时成绩能够根据问题需求编写完整的基于面向对象的数据结构程序，程序结果完全正确，逻辑清楚、效率高。能够根据问题需求编写完整的基于面向对象的数据结构程序，程序结果基本正确，逻辑较清楚、效率较高。基本能够根据问题需求编写完整的基于面向对象的数据结构程序，程序结果存在个别错误、效率不高。程序无法满足需求；或者程序结果完全错误，逻辑混乱；或者有抄袭现象。实验成绩能够正确运用数据结构的专业知识对问题进行分析，能够正确的选择相应的逻辑和存储结构以及合适的算法进行设计和性能分析，设计方案完全满足需求。能够运用数据结构的专业知识对问题行析，能够选择相应的逻辑和存储结构以及合适的算法进行设计和性能分析，设计方案能够满足需求。基本能够运用数据结构的专业知识对问题进行分析，较为正确地选择相应的逻辑和存储结构以及合适的算法进行设计和性能分析，设计方案基本满足需求。不能运用数据结构的专业知识对问题进行分析，对数据选择的逻辑和存储结构以及算法存在严重错误，设计方案无法满足需求。期末考试全面掌握数据结构的相关算法，能够非常熟练的编写程序，解决具体问题时能提出正确合理的方案，并有良好的实现结果。比较全面地掌握数据结构的相关算法，能够较为熟练地编写程序，解决具体问题时能提出正确合理的方案，并有较好的实现结果。基本掌握数据结构的相关算法，能够编写程序，解决具体问题时提出的方案基本可行，实现结果存在个别错误。仅仅学会了小部分数据结构的相关算法，不能独立编写完整的程序，无法应用所学知识解决具体问题。课程目标3平时成绩能够根据问题需求编写完整的基于面向对象的数据结构程序，程序结果完全正确，逻辑清楚、效率高。能够根据问题需求编写完整的基于面向对象的数据结构程序，程序结果基本正确，逻辑较清楚、效率较高。基本能够根据问题需求编写完整的基于面向对象的数据结构程序，程序结果存在个别错误、效率不高。程序无法满足需求；或者程序结果完全错误，逻辑混乱；或者有抄袭现象。实验能够正确运用面向对象编程方法，编写结构清晰、正确易读、移植性好、效率高、思路新颖的程序。能够运用面向对象编程方法，编写结构较清晰、可读性和移植性较好、效率较高、思路较新颖的程序。能够运用面向对象编程方法编写程序，程序结构清晰性、可读性和移植性一般、效率不够高、思路不够新颖。不能较好地运用面向对象编程方法编写程序，程序无法满足需求；或者程序结果完全错误、逻辑混乱；或抄袭现象严重。期末考试全面掌握数据结构的相关算法，能够非常熟练的编写程序，解决具体问题时能提出正确合理的方案，并有良好的实现结果。比较全面地掌握数据结构的相关算法，能够较为熟练地编写程序，解决具体问题时