数据结构课程标准

数据结构模块化课程标准课程名称：数据结构适用专业：计算机科学与技术、通信工程、信息管理与信息系统等相关专业学时/学分：64/4一、课程定位《数据结构》是研究现实世界中数据的各种逻辑结构在计算机中的存储结构以及进行各种非数值操作的方法。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。它不仅是计算机程序设计的理论基础，而且是学习计算机操作系统、编译原理、数据库原理等课程的重要基础。数据结构是要培养学生分析和研究计算机加工的数据对象特征的能力，本课程定位严格服务于应用型高等学校专业人才培养目标，坚持理论与上机实践相结合，通过算法训练提高学生的编程思维与编程能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。二、课程设计思路课程建设指导思想是：树立精品意识；渗透创新理念；体现应用型办学特色；注重实践教学。课程安排在大学二年级第一个学期，学习数据结构的目的是为了可以更好地理解计算机处理对象的特性、将实际问题所涉及的处理对象在计算机中表示出来并对它们进行处理。数据结构课程内容概念多、综合性和技巧性强，对于学生来说，学生难以听懂，因此，在教学方法上宜采用案例教学，实验上采用项目驱动。课程教学要结合学校应用型人才培养的定位，培养学生的学习兴趣和良好的学习习惯，通过实践教学中以培养学生的独立思考能力、动手能力。通过小组合作、项目带动等方式进一步培养学生的沟通能力和创新能力。课程结束后，学生应能独立上机编写并调试程序，用程序解决实际问题。在二年级的学习中，学生需要掌握各种逻辑结构在不同存储方式下的常用算法，能够编写课程标准中的所有实训项目。教学方法和手段：在实际教学中，我们采取多媒体进行教学，课外让学生在慕课网注册学习，学生可根据自身的学习情况利用课外时间进行针对性的复习；根据不同的章节内容，在教学中突出重点，并根据不同的章节制订相应的授课计划。所有教师均加入QQ群和微信群以方便与学生进行讨论；为巩固课堂教学内容，除书本的课后作业外，我们又补充了一些习题，并给出详尽的解析，使学生在循序渐进中得到提高；随着信息技术的发展，我们将不断探索如何将启发式、因材施教的教学方法与以网络、多媒体等现代信息技术更好的结合起来，启发式教学能诱导学生深入思考，实现教与学的互动，激发学生的创造性，达到创新能力培养和提高教学效果的目的，所以一方面要发挥传统的黑板书写与口头交流的课堂教学的优势，另一方面要利用现代化的教学手段，探索和建构基于信息技术的教学模式，提高学生自主学习的主动性；通过实验课教学，一方面加深学生对数据结构课程内容的理解，另一方面达到理论联系实际的目的，使得学生不仅能够掌握算法，而且能培养综合运用所学知识独立解决实际问题的能力，并给学生发展个性化以更加广阔的天地。教学条件建设方面：授课、实验等严格按课程标准执行，内容规范。采用国家级优秀高校教材及其配套实习验及习题集；教师授课全部采用电子教案，教案质量高，并根据课程标准要求随时进行动态更新。数据结构课程全部使用多媒体教室上课，用电子教案授课。学生上机实验有质量高的实验指导书。师资队伍建设方面：我们十分重视数据结构课程教师队伍的建设，要想办出高质量的本科应用型人才教育，“双师型”教师队伍的建设是关键，我院自开设数据结构课程以来，一直比较重视本科应用型人才教育师资队伍的建设，经过几年的建设，我院本科应用型人才教育教师队伍的职称结构、学历结构、年龄结构均比较合理，我们的建设的目标是建立一支高质量的专兼职结合的“双师型”教师队伍。根据人才培养方案和应用型大学培养应用型人才的要求，制定本课程标准。三、课程目标学习本课程后，学生应达到以下教学目标：知识目标：1.掌握算法时间复杂度和空间复杂度的分析方法；2.理解线性表、栈、队列、串等线性结构的基本概念、特点及常用算法；3.理解特殊矩阵的压缩存储及其算法；4.理解树、图等非线性结构的基本概念、特点及常用算法；5.理解顺序存储结构和链式存储结构的优缺点；6.理解查找静态查找表、动态查找表和哈希查找表及其查找算法；7.理解各种内部排序算法；技能目标1．培养学生的数据抽象能力和复杂程序设计的能力；2．培养学生分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构；3．培养学生分析问题、解决实际问题的能力；4．培养学生算法分析和设计能力；5．培养学生团队协作能力职业能力目标1．具备协同工作和团队合作能力；2．具备较强的语言表达能力、良好的沟通能力和协调能力；3．具备独立分析和思考能力，具备良好的自学能力；4．具有理解和应用软件规范、软件开发流程的能力；5．学会使用计算机处理问题的思维方法，具有阅读和编写程序的能力；6.具有一定的应用创新能力。四、课程内容及标准（一）课程内容标准模块名称能力目标知识与技能要素考核标准基本概念1、能正确理解数据结构的基本概念；2、能正确理解数据的各种逻辑结构中各元素之间的关系；3、能正确理解顺序存储和链式存储结构；4、能定义抽象数据类型。5、能分析算法时间复杂度和空间复杂度。1、数据结构的定义及术语；2、数据的逻辑结构（集合、线性结构、非线性结构（图、树））3、数据的存储结构（顺序存储结构和链式存储结构）4、抽象数据类型；5、算法概念、特性、评1.考核内容：1)数据结构的基本概念、数据之间的逻辑关系、存储结构；2)对给出的一段程序写出算法时间复杂度，用大O表示法表示；2、考核方式：价标准作业、实验报告、测试；3、占总成绩的比例：2~8%线性表1.能理解线性表的基本概念、特点2.能实现顺序表的定义、输入、输出、插入、删除、查找等基本操作，并能分析他们的时间复杂度3.能理清单链表、循环单链表、循环双向链表的特点及关系4.能实现链表的定义、建立、输出、插入、删除、查找等基本操作，并能分析他们的时间复杂度5.能够根据实际问题，选择合适的存储结构。6.能实现两个顺序表的合并、顺序表的逆置、顺序表元素分解、合并两个有序链表、一元多项式求解。1.线性表的基本概念、逻辑关系2.顺序表的定义及特点3.顺序表的基本操作及插入和删除操作的性能分析等4.链表的定义、链表基本操作。5.循环链表、双向链表1.考核内容1）线性表的基本概念2）顺序表的定义、顺序表的基本操作操作3）链表的定义、链表的基本操作。4）线性表的应用2.考核方式作业、实验报告、平时小测试3.成绩比例：16%~20%栈和队列1.能理解栈和队列的基本概念2.能实现顺序栈的基本操作3.能实现链栈的基本操作4.能实现顺序队列的基本操作5.能实现链队列的基本操作6.能用栈的思想编程完成进制的转换、迷宫问题求解、表达式求值等问题。1.栈和队列基本概念及特点2.栈和队列顺序存储和实现3.栈和队列链式存储和实现4.栈和队列的应用1.考核内容：1）栈和队列的基本概念及特点2）顺序栈的基本操作3）链栈的基本操作4）顺序队列的基本操作5）链队列的基本操作6）栈和队列的应用2.考核方式作业、实验报告、小测验3.占总成绩的比例：12%~20%串1.能定义顺序串和链串；2.能完成串的输入、使用和输出；3.能实现串的模式匹配算法。1.串抽象数据类型2.串的表示和实现3.串的模式匹配1.考核内容1）串的定义、初始化和使用2）顺序串的输入、输出3）链串的输入输出4）串的模式匹配算法2.考核方式：作业、实验报告、小测试3.考试所占比例：2~6%数组和广义表1.能知道数组首地址计算数组中其他元素的地址2.能处理特殊矩阵的压缩存储3.能实现稀疏矩阵的三元组表的存储及运算4.能定义广义表，运用相关的操作1.数组的顺序存储和实现2.特殊矩阵的压缩存储3.稀疏矩阵的三元组表存储4.广义表抽象数据类型及存储结构1．考核内容1）计算数组元素的地址2）特殊矩阵的压缩存储方式3）稀疏矩阵的存储及转置操作4）广义表的概念2.考核方式作业、实验报告、测试2．总成绩比例：4~6%树型结构1.能用顺表存储结构存储二叉树2.能用二叉链表存储二叉树3.能完成二叉树的创建、二叉树的先序遍历、中序遍历、后序遍历和层次遍历（求叶子结点数）。4.能已知前序序列和中序序列求后序序列，已知后序序列和中序遍历求前序序列。5.能实现哈夫曼树的创建、哈夫曼编码及哈夫曼译码1.树及二叉树的概念2.二叉树的性质3.二叉树的存储4.二叉树的创建5.二叉树的遍历6.线索二叉树7.树、森林与二叉树的相互转换8.哈夫曼树及哈夫曼编码译码1.考核内容1）树的概念2）二叉树的概念和性质3）已知前序序列和中序序列求后序序列，已知后序序列和中序遍历求前序序列4）哈夫曼树的概念及生成算法，哈夫曼编码设计、哈夫曼译码5）树、森林与二叉树的相互转换6）线索二叉树求前驱和后继2.考核方式作业、实验报告、小测验3.占总成绩比例：20~30%图型结构1.能用邻接矩阵法存储图2.能用邻接表或逆邻接表法存储图3.能用顺序存储结构存储最小生成树4.能实现邻接矩阵表示的图的创建、深度优先遍历和广度优先遍历5.能实现邻接表表示的图的创建、深度优先遍历和广度优先遍历6.能实现最小生成树的prim算法和克鲁斯卡尔算法7.能实现最短路径的迪杰斯特拉算法1.图和网络的概念及其性质2.图和网络的存储形式3.图深度优先遍历和广度优先遍历4.最小生成树的prim算法和克鲁斯卡尔算法5.最短路径及迪杰斯特拉算法1.考核内容1）图的性质2）图的邻接矩阵表示法和邻接表表示法3）图深度优先遍历和广度优先遍历4）prim算法,克鲁斯卡尔算法5）迪杰斯特拉算法2.考核方式：作业、实验报告、小测试3.考试所占比例：10~15%查找1.能实现顺序查找、二分查找、分块查找2.能实现二叉排序的创建及查找3.能实现散列表的存储及查找4.能分析各种查找算法的性能1.顺序查找及性能分析2.二分查找适用条件，查找算法及分析性能3.分块查找及性能分析4.二叉排序树查找及性能分析5.散列表查找及性能分析1.考核内容1）几种查找算法的优缺点比较2）几种查找算法各自的适用条件3）几种查找算分析法思想及性能2.考核方式：作业、实验报告、小测试3.考试所占比例：10~15%排序1.能编程实现插入排序法中的直接插入排序法，折半插入排序法2.能编程实现选择排序法中的直接选择排序法和堆排序法3.能编程实现交换排序法中的冒泡排序法和快速排序法1.插入排序法及时间复杂度和稳定性分析2.选择排序法及时间复杂度和稳定性分析3.交换排序法及时间复杂度和稳定性分析1.考核内容1）几种排序算法算法思想2）几种排序算法的稳定性和时间复杂度分析2.考核方式：作业、实验报告、小测试3.考试所占比例：4~10%（二）教学过程实施标准1.理论教学（含课内学时实施标准）模块名称二级子模块讲授实践教学方法与手段绪论数据结构的定义及术语；数据的逻辑结构（集合、线性结构、非线性结构（图、树））数据的存储结构（顺序存储结构和链式存储结构）抽象数据类型2案例教学课堂讲授算法概念、特性、评价标准2课堂讲授线性表线性表的基本概念、逻辑关系顺序表的定义及特点顺序表的基本操作及插入和删除操作的性能分析等2案例教学顺序表的基本操作，顺序表案例顺序逆置、两个顺序有序表合并，顺序表按某个条件分解等22案例教学链表的定义、建立、输出、插入、删除、查找等基本操作，并能分析他们的时间复杂度2案例教学循环链表、双向链表的定义及基本操作一元多项式的计算22案例教学栈和队列栈的基本概念及特点栈的顺序存储2课堂讲授案例教学栈的链式存储栈的应用22案例教学队列的基本概念及特点队列的顺序存储、循环队列2课堂讲授案例教学链队列队列的应用22课堂讲授案例教学串串抽象数据类型串的表示和实现串的模式匹配2课堂讲授案例教学数组和广义表数组的顺序存储和实现特殊矩阵的压缩存储稀疏矩阵的三元组表存储广义表抽象数据类型及存储结构2课堂讲授案例教学树树及二叉树的概念二叉树的性质二叉树的存储2课堂讲授案例教学二叉树的创建及遍历22课堂讲授案例教学线索二叉树树和森林2课堂讲授案例教学哈夫曼树及应用22课堂讲授案例教学图图的定义和术语图的存储结构2课堂