数据结构与算法教学大纲.doc

数据结构与算法课程教学大纲（Data structure and algorithm）编制： 审核：一、课程信息课程名称：数据结构与算法英文名称：Data structure and algorithm 课程代码：030010 课程类别：职业技术基础课课程性质：系级必修课 学分学时：4学分，64学时先修课程：程序设计基础适用专业：计算机应用技术、计算机软件开课单位：计算机科学与技术系使用教材：张晓莉主编，数据结构与算法，机械工业出版社，2012年二、课程的性质、地位和任务数据结构与算法是计算机应用技术、计算机软件技术专业的专业基础课，学习本课程能使学生掌握数据在计算机中的表示、存储和处理。为以后学习编译程序、操作系统、数据库系统打下基础。通过本课程的学习，使学生获得计算机科学各领域的数据结构知识，及有关的应用软件所要用到的各种数据结构知识。掌握常用的数据结构及内在的逻辑关系，掌握计算机软件设计中的算法知识。提高软件设计和编程技能。学会初步对不同的存储结构和相应算法的对比，有一定的算法改进能力。三、课程教学目标（一）知识目标1要求学生掌握常用数据结构的基本概念2要求学生掌握不同存储结构的不同的实现方法（二）技能目标1通过系统学习能够在不同存储结构上实现不同的运算2能对算法设计的方式和技巧有所体会3能较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力（三）素质目标1初步具备分析问题、解决问题的能力2养成良好的程序设计风格四、教学方法手段（一）教学环节包括课堂教学、习题课、上机操作、答疑、考试等。通过各教学环节，重点培养学生的分析问题和解决问题的能力。（二）教学方法采用问题驱动的启发式教学方法，加强实践教学。（三）教学手段采用板书和多媒体课件相结合的教学手段五、课程教学内容与要求（含学时分配） （一）绪论（2学时）教学基本内容：1什么是数据结构2基本概念和术语3抽象数据类型的表示与实现4算法和算法分析重点：1数据的逻辑结构和存储结构之间的关系2计算语句频率和估算算法时间复杂度和空间复杂度的方法难点：估算算法时间复杂度和空间复杂度本章主要教学要求：1了解：算法的五要素、各名词、术语的含义2掌握：基本概念，特别是数据的逻辑结构和存储结构之间的关系3应用：计算语句频率和估算算法时间复杂度和空间复杂度的方法（二）线性表（8学时，其中实验实训4学时）教学基本内容：1线性表的概念2顺序线性表的顺序存储结构和基本操作3线性表的链式存储结构和基本操作4顺序表和链表的应用实验实训序号名称内容学时1线性表的应用顺序表的使用、包括创建、销毁、插入、删除和查找。22线性表的应用链表的使用、包括创建、销毁、插入、删除和查找。2重点：1顺序线性表的顺序存储结构和基本操作2线性表的链式存储结构和基本操作难点：顺序表和链表的应用本章主要教学要求：1了解：线性表的概念、双向链表的基本操作2掌握：顺序线性表的顺序存储结构和基本操作、掌握链表的链式存储结构和基本操作3应用：顺序表和链表的应用（三）栈和队列（8学时，其中实验实训4学时）教学基本内容：1栈的定义2栈的顺序存储结构和链式存储结构3栈的应用4队列的定义5队列的顺序存储结构和链式存储结构6队列的应用实验实训序号名称内容学时1栈的应用顺序栈的使用，包括创建、销毁、入出栈22队列的应用循环队列的使用，包括创建、销毁、入出队列2重点：1栈的顺序存储结构和链式存储结构2队列的顺序存储结构和链式存储结构难点：栈的应用本章主要教学要求：1了解：栈的定义、队列的定义及队列的应用2掌握：栈的顺序存储结构和链式存储结构、掌握队列的顺序存储结构和链式存储结构3应用：栈的应用（四）字符串、数组和广义表（8学时，其中实验实训4学时）教学基本内容：1字符串基本概念2字符串的存储结构3字符串的模式匹配4数组的类型定义5矩阵的压缩存储6广义表实验实训序号名称内容学时1字符串的应用字符串的使用22数组与广义表的应用数组与广义表的使用2重点：1字符串的存储结构2矩阵的压缩存储难点：字符串的模式匹配本章主要教学要求：1了解：串的定义、串的模式匹配、广义表的概念及广义表的应用2掌握：串的顺序存储结构和链式存储结构、数组的定义、顺序存储表示与实现3应用：串的应用及特殊矩阵的压缩存储（五）树和二叉树（10学时，其中实验实训4学时）教学基本内容：1树的定义和基本术语2二叉树3遍历二叉树和线索二叉树4树和森林5哈夫曼树及其应用实验实训序号名称内容学时1树与二叉树的应用二叉树的创建、遍历22树与二叉树的应用查找二叉树的叶子数，高度及交换二叉树的左右子树2重点：1二叉树的定义及存储结构2二叉树的遍历3二叉树的应用，包括二叉排序树、哈夫曼树等4掌握树的存储以及树、森林和二叉树的相互转换难点：遍历二叉树和线索二叉树本章主要教学要求：1了解：树的定义和基本术语、线索二叉树的定义及基本操作2掌握：二叉树的定义及存储结构、二叉树的遍历、树的存储以及树、森林和二叉树的相互转换3应用：二叉树的应用，包括二叉排序树、哈夫曼树等。（六）图（8学时，其中实验实训4学时）教学基本内容：1图的定义和术语2图的存储结构3图的遍历4最小代价生成树5最短路径6拓朴排序实验实训序号名称内容学时1图的应用图的创建、销毁和遍历4重点：1图的存储结构2图的深度优先遍历和广度优先遍历的方法难点：1最小生成树的算法2最短路径的两个经典算法：迪杰斯特拉和弗洛伊德算法本章主要教学要求：1了解：图的基本概念、拓扑排序的概念，会求拓扑序列2掌握：图的存储结构、图的深度优先遍历和广度优先遍历的方法3应用：最小生成树的算法、最短路径的两个经典算法：迪杰斯特拉和弗洛伊德算法（七）查找（10学时，其中实验实训6学时）教学基本内容：1线性表的查找2树的查找3哈希表及其查找实验实训序号名称内容学时1查找的应用顺序查找的使用22查找的应用折半查找的使用23查找的应用哈希表的使用2重点：1线性表的查找2树的查找难点：哈希表及其查找本章主要教学要求：1了解：查找的基本思想及查找成功和不成功的概念、B 树查找2掌握：在无序顺序表、有序顺序表以及有序链表上的查找方法和算法，并能求出相应的平均查找长度3应用：二叉树查找的思想与算法、平衡二叉树查找的规律、哈希表的概念、存储结构、及实现方法（八）排序（10学时，其中实验实训6学时）教学基本内容：1概述2插入排序3快速排序4选择排序5归并排序6冒泡排序7各类内部排序方法的比较讨论实验实训序号名称内容学时1内部排序的应用插入排序的使用22内部排序的应用选择排序的使用、归并排序的使用23内部排序的应用冒泡排序的使用、快速排序的使用2重点：1插入排序2快速排序3选择排序4归并排序5冒泡排序难点：各类排序算法的实现和性能分析本章主要教学要求：1了解：排序的概念2掌握：排序的种类3应用：各类排序的排序过程、算法实现和性能分析六、课程学时分配教学内容学时分配讲授实验实训小计（一）绪论202（二）线性表448（三）栈和队列448（四）字符串、数组和广义表448（五）树和二叉树6410（六）图448（七）查找4610（八）排序4610总计323264七、课程习题要求1根据教学进度中的难点、重点及学生的学习状况安排3次习题课。习题课的型式一般应以启发式与讨论式相结合，题型一般包括学生作业中最易出错的题，如：应用题、算法题等。每次课都布置一定数量的作业习题，用以巩固学生所学知识。2答疑为了使学生更好的掌握和巩固所学知识，课余应安排一定的答疑时间。八、课程考核1. 考核方式笔试考试：（闭卷）笔试题型以主观题为主，客观题为辅，时间为100分钟，试题量应以中等水平的应试者在规定的时间内答完全部试题为宜。占课程总评成绩的60%。2. 课程成绩总评课程成绩（总评）=