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