教育材料《数据结构》-课程标准

《数据结构》课程标准课程代码KC12课程性质专业基础课总学时72适用专业软件技术及相关专业教学方式“教、学、做”一体化制定单位学校武汉软件工程职业技术学院制定日期2012.8.8审核部门软件技术专业资源库建设项目组企业武汉光谷信息技术有限公司一、课程定位本课程是软件技术专业的专业基础课，是培养学生程序设计能力的支撑课程。本课程主要培养学生的数据结构应用能力、算法分析能力与程序设计素质，通过“教、学、做”一体化教学，使学生掌握分析研究计算机加工对象的特性，选择合适的数据结构和存储表示，编制相应的实现算法，培养和提高学生程序设计的能力，为后续课程及其他程序设计课程的学习和应用打下基础。先修课程：《计算机应用基础》、《JAVA语言程序设计》。后续课程：《数据库管理与应用》、《Java程序设计》、《C#程序设计》等。二、课程目标通过对本课程的学习，使学生掌握各种常用数据的逻辑结构、存储表示、基本操作及算法设计，学会分析计算机加工的数据对象的特性，以便选择合适的数据逻辑结构、存贮结构及相应的基本处理算法；初步掌握算法的时间和空间复杂度分析技术,培养学生数据抽象能力和复杂程序设计能力，为今后软件开发设计打下坚实基础。知识目标1．了解数据结构的逻辑结构和物理结构之间的关系，数据结构和数据类型的关系，数据结构和算法的关系。2．熟悉各种基本数据结构的概念、特点、存储结构；3．掌握各种基本数据结构的运算及其算法设计；4．掌握常用算法的基本分析方法；5．掌握排序和查找的基本算法。能力目标1．掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法实现。2．使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。3．通过对本课程算法设计和上机实践的训练，培养学生的数据抽象能力和复杂程序设计的能力。4．有初步的算法分析和设计能力。5．能够有效地获取、利用、传递信息。6．通过独立学习，不断获取新的知识和技能，能够在工作中寻求发现问题、解决问题的途径。素质目标1．培养学生良好的协调和沟通能力；2．培养学生勇于创新和严谨细致的工作作风；3．培养学生良好的职业道德和团队合作精神；4．培养学生善于收集信息和良好的自学能力；5．培养学生理论联系实际，善于发现问题并积极寻求解决问题方法的能力。其他目标通过本课程的学习，可以参加以下职业资格证书的考试。1．全国计算机等级二级考试；2．程序员。三、课程内容与要求根据课程目标确定学习内容，包括绪论、线性表、栈和队列、串、数组和广义表、树、图、查找、排序、文件。知识体系结构如下表。表1《数据结构》内容及要求序号单元名称主要内容目标与要求建议学时1绪论数据结构的基本概念；算法概念及特性；算法分析的一般概念。理解数据结构的基本概念；掌握逻辑结构、物理结构的概念及相互关系；掌握本书介绍的四种基本结构的特点；理解算法及其特性；了解算法分析的一般概念；掌握JAVA开发工具的使用方法。62线性表线性表的定义、逻辑结构、顺序存储结构、链式存储结构；线性表在顺序结构和链式结构上的基本操作和应用；双向链表、循环链表的原理和相关操作。理解线性表的定义及两种存储结构；理解线性表顺序存储的特点、实现方法和应用；掌握顺序表的基本操作；掌握链表的基本操作（包括建立链表、遍历链表、删除、插入、查找）和应用。特别要求能够利用链表的操作和相关的程序设计技术编制有一定难度的程序；了解双向链表、循环链表的原理和相关操作。83栈和队列栈的定义、栈的存储结构（顺序存储、链式存储）和基本操作、栈的应用；队列的定义、队列的存储结构（顺序存储、链式存储）、队列的应用；循环队列的概念和实现方法；掌握栈和队列的操作特点；理解顺序栈、顺序队列的基本操作；了解在实际编程中栈和队列的不同应用；理解循环队列的概念、实现方法。掌握循环队列判空、判满的条件；能按照后续章节（例如二叉树、排序等）的要求利用递归程序设计技术实现相关算法。64串串类型定义、JAVA语言中字符串的特点和处理方法；串的顺序存储结构和链式存储结构；串的基本运算和实现方法。理解串的定义和存储方法；了解串的基本操作和相关算法；掌握用JAVA语言处理字符串的语法规则。65数组和广义表数组的定义和存储结构；特殊矩阵和稀疏矩阵的存储结构；广义表的定义和存储结构。了解数组的存储结构；掌握特殊矩阵进行压缩存储的下标转换公式；理解稀疏矩阵的压缩存储原理；掌握利用三元组表示稀疏矩阵的方法；了解广义表的概念和存储结构。86树树的基本概念；二叉树的性质和存储结构；二叉树的遍历和线索二叉树；哈夫曼树及其应用。了解树和二叉树的定义；掌握二叉树的基本性质，能利用相关性质解决简单计算问题；了解二叉树的顺序存储结构；掌握二叉树的链式存储结构、相关操作；掌握二叉树的有关算法并能编程实现；掌握利用遍历序历构造二叉树的规则和具体步骤；掌握哈夫曼树的定义、性质和构造方法；了解哈夫曼树的应用。127图图的基本概念；图的存储结构；图的遍历；最小生成树和最短路径。了解图的基本概念；掌握图的存储方法（邻接矩阵、邻接表）；掌握图的深度优先和广度优先遍历的规则和步骤；理解在连通图中求最小生成树的方法；了解求图的最短路径等相关算法及其应用。128查找顺序查找；折半查找；分块查找；二叉排序树的查找；哈希表的定义；哈希函数的构造；处理冲突的方法；哈希表的查找和分析。了解查找的相关概念；掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度；掌握在有序的顺序表上进行折半查找的方法、步骤、程序实现；掌握折半查找的判定树的构造方法；掌握二叉排序树的确切定义；掌握建立二叉排序树的步骤和方法；理解在二叉排序树中进行输入、删除操作的规则；了解哈希表的相关概念和原理；了解常用哈希函数的构造和处理冲突的方法；掌握哈希函数和哈希表的关系及在查找中的应用。69排序直接插入排序；希尔排序；冒泡排序；快速排序；简单选择排序；堆排序；归并排序。掌握教材中介绍的各种排序算法的基本原理、步骤；掌握相关排序算法的规则人工完成排序；能通过分析排序的中间结果判断所用的排序算法；能正确理解相关排序算法的程序实例，并重点掌握算法中的关键步骤和关键语句；掌握堆和特殊的完全二叉树的对应关系；掌握建堆、筛选算法和完全二叉树相关操作的对应关系。610文件文件的概念；各种类型的文件；各类文件的操作。了解文件的概念和文件的分类；掌握顺序文件操作；掌握索引文件操作；了解多关键字文件。2合计72四、教学资源要求教材选用原则1．包含基本数据结构的分析与算法设计；2．案例选用与实际问题相结合；3．改革传统的教材组织方式，注重以能力培养为主线、做到理实一体。推荐教材与参考书籍1．《数据结构—JAVA语言描述》，北京理工大学出版社，库波、曹静主编；2．《数据结构（JAVA语言版）》，清华大学出版社，严蔚敏吴伟民编著；3．《数据结构教程上机实验指导》，清华大学出版社，李春葆；4．C程序设计题解与上机指导（第2版），清华大学出版社，谭浩强著。其他学习资源1．武汉软件工程职业学院精品课程网站：/jpkc/sjjg2．西北大学数据结构学习网：/datastr3．数据结构课件（严蔚敏）：/source/3835194．北大数据结构与算法课程网：/pkujpk/course/sjjg5．电子书：JAVA语言入门基础知识。教师要求主讲教师需要熟练掌握数据结构及其相关内容，具备运用JAVA语言进行程序开发的能力、具备较丰富的教学经验、基本的设计能力、能按照本课程标准制定详细的授课计划，精心设计每一次课的教学过程，具备一定的课堂控制能力和应变能力，做到因材施教。学习场地、设施要求1．计算机硬件要求：CPU主频>1Ghz,内存容量>=1GB；2．软件要求：WindowsXP及以上，JDK6.0环境；3．其他要求：本课程要求在多媒体机房完成，以实现“教、学、做”三体合一，同时要求安装多媒体教学软件和数据结构集成学习环境，便于下发教学任务和收集学生课堂实践任务。五、考核与评价本课程考核采用形成性考核方式，总评成绩由形成性考核的各项成绩组成，全面考核学生的动手能力、基础理论和平时学习状况，分数比例为：综合素质评价（平时表现+通用能力考核）20%过程性考核（课堂实践考核+课后实践考核+单元测试）50%终结性考核（期终考核）30%六、教学实施建议1．课堂教学采用“教、学、做”一体化方式，用案例引导学生学习知识，通过动手实践，让学生理解、掌握基本的编程知识和基本技能。教学过程突出精讲多练，并