《数据结构》课程标准

PAGE1《数据结构》课程标准一、课程基本信息课程编码适用专业计算机类职业本科专业课程类别专业核心课开课单位计算机信息工程系课程学时建议（70—90）学时其中：理论（50—60）学时实践（20—30）学时建议增加（10—16）课程设计课程学分4开设学期第***学期合作单位*******公司制(修)订时间202*年**月审定时间202**年**月**日二、课程性质和作用1、课程的性质：专业核心课2、课程的作用：通过学习这门课程，学生能够掌握数据结构的基本概念，掌握各种数据结构的逻辑特性、存储表示和基本算法，针对复杂工程中的算法问题，能够设计数据结构和算法，进行算法分析，并通过具体的编程语言加以实现，具有计算思维能力和创新思维能力，能够为算法设计提出合理的改进建议，具有工程素养，能够坚持职业操守和道德规范，具有精益求精的工匠精神和探索未知终身学习的意识，具有科技报国的社会责任感。本课程计划开设在第三学期（也可以放到第四学期），前导课程有：《计算机程序设计基础》、《高等数学》等课程，同时是操作系统、软件工程、数据库概论、编译技术、人工智能、计算机图形学等专业课程的必修先行课。三、课程设计思路《数据结构》旨在使学生能够理解、设计和有效地应用各种数据结构，讲练结合，培养学生解决实际问题的能力以及主动学习和分析问题的能力，突出学生主导地位，充分调动学生在学习中的主动性和积极性。在教学实施过程中，采用基于线上线下混合开放式的教学组织形式，将全课程分为8个教学单元，每个教学单元分解为“线上-讲授-实践”三个教学环节，培养学生独立思考问题能力及应用能力。在教学内容设计中，充分利用信息化教学平台，通过教学资源建设，构建方便学生学习的新形态立体化教学资源体系。通过信息化教学平台为学生提供“课件、微课视频、网格教学资源、电子参考书目”及相关知识拓展资料，促进学生学习效率和学习质量的提高。四、课程目标学生通过学习本课程后，在知识、能力、素质等方面应达到如下目标，对专业培养规格形成必要支撑。知识目标（1）掌握数据结构的基本概念。（2）掌握各种数据结构的逻辑特性。（3）掌握各种数据结构的存储表示。（4）掌握各种数据结构的基本算法。2、能力目标（1）具有依据工程实际问题的需求来合理组织数据、并在计算机中有效地存储数据的能力。（2）能够对复杂工程中的算法问题进行抽象、提取和归纳。（3）能够在各种数据结构基础上进行算法设计与描述，掌握算法时空间复杂度的分析方法。（4）能够运用数据结构的基础知识，表达和分析计算机领域的复杂工程问题。（5）能够针对复杂工程中的算法问题，设计出比较合理的解决方案，并通过具体的编程语言加以实现，同时体现一定的创新思维能力。（6）能够基于数据结构基本原理和文献研究，针对复杂工程中的算法问题设计合理的研究方案。3、素质目标（1）培养学生具有工程素养，能够坚持职业操守和道德规范。（2）培养学生，具有精益求精的工匠精神和探索未知终身学习的意识。（3）培养学生不断追求新知识，新技能的自学能力。（4）培养学生具有科技报国的社会责任感。五、课程内容与要求《数据结构》课程内容8个教学单元。每一个教学单元的名称、教学内容、学习目的、重点难点说明和教学基本要求如下表所示。单元1：绪论[教学内容]（1）数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构等；（2）抽象数据类型的表示和实现；（3）算法的概念和特性；（4）算法时间复杂度和空间复杂度的分析。[教学目标]（1）掌握数据结构的基本概念，深刻理解各种数据结构的逻辑特性和存储表示方法。（2）具有依据工程实际问题的需求来合理组织数据、并在计算机中有效地存储数据的能力（3）能够对复杂工程中的算法问题进行抽象、提取和归纳。（4）能够在各种数据结构基础上进行算法设计与描述，掌握算法时空间复杂度的分析方法。[重点难点]（1）数据结构相关概念，算法分析（2）算法时间复杂度的计算[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）；第3款。单元2：线性表[教学内容]（1）线性表的类型定义；（2）线性表的顺序表示和实现；（3）线性表的链式表示和实现；（4）线性表的应用，如有序表的合并等；[教学目标]（1）理解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表），熟练掌握这两类存储结构的描述方法及其不同存储结构上基本算法的实现；（2）掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点及其基本算法的实现；（3）掌握有序表的合并算法，能够从时间和空间复杂度的角度比较顺序和链式两种存储结构的不同特点，能够依据实际应用问题的需求选用合理的存储结构，能够研究、设计出有效的基于线性表的算法，并能够分析算法的性能；[重点难点]（1）线性表的顺序存储（2）线性表的单链表存储结构、单链表的操作（2）单向循环链表、双向循环链表[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）、（4）；第3款。单元3：栈和队列[教学内容]（1）栈的类型定义，栈的顺序存储和链接存储的表示和实现；（2）栈的应用举例，如表达式求值算法；（3）栈与递归的实现；（4）队列的类型，队列的顺序存储（循环队列）和链接存储的表示和实现；[教学目标]（1）掌握栈和队列的特点，并能够在相应的应用问题中正确选用不同的数据结构；（2）掌握栈的两种存储表示和算法实现，特别注意栈满栈空的条件；（3）掌握队列的两种存储表示和算法实现，特别注意队满队空的条件；（4）能够利用栈来设计算法实现表达式求值；（5）深刻理解递归算法执行过程中栈的状态变化过程；[重点难点]（1）栈的顺序存储、栈的链式存储（2）队列的顺序存储、队列的链式存储（3）栈与递归的应用，队列的应用[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）、（4）、（5）；第3款。单元4：串、数组和广义表[教学内容]（1）串的定义、存储结构和基本运算，串的模式匹配算法；（2）数组的顺序存储表示和寻址方式，特殊矩阵的压缩存储；（3）广义表的逻辑结构和存储结构；[教学目标]（1）了解串、数组和广义表的基本概念；（2）理解数组的存储方式和寻找方法；（3）掌握串的字符匹配算法；（4）掌握广义表结构，会分析广义表；[重点难点]（1）栈的顺序存储、栈的链式存储（2）队列的顺序存储、队列的链式存储（3）栈与递归的应用，队列的应用[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）、（4）、（5）；第3款。单元5：树和二叉树[教学内容]（1）树、二叉树的定义和术语，二叉树的性质，特殊的二叉树；（2）二叉树的顺序存储结构和链式存储结构；（3）二叉树的的前序、中序、后序、层次遍历方法和基本操作；（4）线索二叉树的定义及线索化二叉树；（5）树和森林的定义，树的存储，树、森林与二叉树的转换；（6）树的应用，哈夫曼树及哈夫曼编码；[教学目标]（1）掌握树、二叉树的定义和相关术语，熟练掌握二叉树的性质和相应的证明方法；（2）掌握二叉树的顺序存储结构和链式存储结构，熟练掌握二叉链表存储结构；（3）熟练掌握二叉树创建、遍历的递归算法，能够灵活运用遍历算法实现二叉树的其他操作；（4）掌握二叉树的线索化过程，以及在线索二叉树上寻找某结点的前驱与后继的方法；（5）了解树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法；（6）掌握哈夫曼树的特性，熟悉掌握哈夫曼树的构造算法及哈夫曼编码算法；[重点难点]（1）二叉树的基本概念、性质、结构（2）二叉树的遍历实现（3）赫夫曼树的构造，哈夫曼编码（4）特殊树的构造和编码[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）、（4）、（5）、（6）；第3款。单元6：图[教学内容]（1）图的定义和术语；（2）图的两种存储结构：邻接矩阵和邻接表；（3）图的两种遍历策略：深度优先搜索和广度优先搜索；（4）构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法；（5）两类求最短路径问题的算：迪杰斯特拉算法和弗洛伊德算法；（6）拓扑排序和关键路径。[教学目标]（1）了解图的基本概念；（2）掌握图的存储结构图的周游（深度优先、搜索、广度优先、拓扑排序）最短路径问题（3）理解图的抽象数据类型；（4）掌握最小支撑树（Prim算法、Kruskal算法）[重点难点]图的存储、图的创建、图的遍历Kruskal算法及代码实现、Prim算法及代码实现拓扑排序算法、关键路径算法[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）、（4）、（5）、（6）；第3款。单元7：查找[教学内容]（1）查找的基本概念；（2）基于线性表的查找：顺序查找、折半查找、分块查找；（3）基于树表的查找：二叉排序树、平衡二叉树、B-树和B+树；（4）基于散列表的查找：散列表的基本概念，散列函数的构造方法、处理冲突的方法、散列表的查找与分析；[教学目标]（1）掌握查找的基本概念；（2）熟练掌握顺序表和有序表的查找方法及其实现，掌握描述折半查找过程的判定树的构造方法，了解分块查找；（3）熟练掌握二叉排序树的特性、构造和查找方法，了解平衡二叉树、B-树和B+树的基本定义和基本操作；（4）熟练掌握散列表的构造方法、处理冲突的方法和查找方法，深刻理散列表与其他结构的表的实质性的差别，了解各种散列函数的特点；（5）能够根据实际应用问题选用合适的查找算法，并按定义计算不同查找方法在等概率情况下查找成功时的平均查找长度ASL。[重点难点]顺序查找，折半查找，分块查找二叉排序树，平衡二叉树，B+和B-树散列表的基本算法，散列函数[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）、（4）、（5）、（6）；第3款。单元8：排序[教学内容]（1）排序的基本概念，包括：正序，逆序，稳定性，排序方法的分类；（2）插入排序：直接插入排序、折半插入排序和希尔排序；（3）交换排序：冒泡排序和快速排序；（4）选择排序：简单选择排序和堆排序；（5）归并排序：2-路归并排序；（6）基数排序：多关键字的排序和链数基数排序；（7）排序算法分析：计算各种排序算法的比较次数和移动次数，时间复杂度和空间复杂度的分析；[教学目标]（1）掌握排序的基本概念和排序方法的分类；（2）深刻理解不同排序方法的特点、适用情况、排序思想、具体排序过程、排序算法的实现；（3）能够分析各种排序方法的时间和空间复杂度。能够从关键字间的比较次数和移动次数分析算法的最好情况、最坏情况和平均情况的时间性能；理解排序方法“稳定”或“不稳定”的含义；（4）能够根据实际应用问题选用合适的排序算法，并能够从时间和空间复杂度上分析其排序的性能；[重点难点]常用算法的实现方法算法的时间和空间复杂度分析[对应目标]本标准第四条第1款；第2款（1）、（2）、（3）、（4）、（5）、（6）；第3款。。课时分配表（以64课时为例）教学单元教学内容课时分配（机制）理论课实践课合计单元1绪论1.1什么是数据结构0.50.51.2什么是算法0.50.51.3应用实例：最大子列和问题11单元2线性表2.1线性表概述112.2线性表的顺序表示——顺序表222.3线性表的链式存储——链表222.4循环链表222.5应用实例：一元多项式求和222.6线性表的顺序存储表示及其基本操作222.7线性表的单链表存储表示及其基本操作22单元3栈和队列3.1栈概述113.2栈的顺序存储——顺序栈223.3栈的链式存储——链栈223.4栈与递归113.5队列概述113.6队列的顺序存储——顺序队列113.7队列的链式存储——链队113.8栈和队列的存储表示及其基本操作44单元4串、数组和广义表4.1串114.2数组114.3广义表11单元5树和二叉树5.1树的定义和基本操作115.2二叉树225.3树和森林225.4哈夫曼树及其应用1235.5二叉树的构造与遍历22单元6图6.1图的定义和基本操作116.2图的遍历116.3图的存储116.4最小生成树116.5图的应用5276.6图的构造与遍历22单元7查找7.1查找的基本概念117.2静态查找表227.3动态查找表227.4散列表117.5查找算法的实现22单元8排序8.1排序的基本概念118.2插入排序118.3交换排序118.4选择排序118.5归并排序118.6计数排序118.7排序算法的实现22合计502070六、教学建议1、教学模式采用基于技能知识，以典型案例与代码为载体，理论学习与实际操作相结合的教学模式。按照由易到难，从抽象到具体的逻辑组织教学，以学生为主体，把知识的学习融合在学习任务的完成过程中，提高教学效果。2、教学方法与手段序号方法或手段应用环节或要求1理论讲解课程所有讲授环节。2实践练习以理论知识为基础，根据实际应用问题，通过代码编程实践所学技术3分组讨论法排序、查找4对比归纳法排序、查找5课余答疑面对面答疑和线上答疑。每4个课上教学课时对应安排不少于2小时的课下答疑。6笔记与总结学生用专门记录本手写，内容要涵盖课前预习和课中笔记、以及每个单元内容的归纳总结、解题经验等。3、教学评价与考核序号考核模块百分比成绩具体构成1学习态度5%主要考核学生旷课、迟到等日常出勤情况。考核学生课前自学情况。2单元作业15%主要考核学生理论知识的学习情况。每个单元至少安排1次作业。3实验成绩20%每个单元实验报告完成情况。4期末考试60%采用“选择、填空、应用题和算法设计题”相结合的方式进行期末考试七、教学条件1、教师任职要求《数据结构》是理论结合实践