《数据结构与算法》课程教学大纲

《数据结构与算法》课程教学大纲课程代码：适用专业:计算机应用技术总学时数: 68学时,其中：理论教学34学时,实践教学3４学时。学分:４、5考核方式:机试一、制订大纲得依据本大纲根据201３年软件技术专业教学计划制订。二、课程简介数据结构就是介于数学、计算机硬件与计算机软件之间得一门计算机科学与技术专业得核心课程,就是高级程序设计语言、编译原理、操作系统、数据库等课程得从数据表示与数据处理上瞧有五个基本组成“要素”分别就是逻辑结构,存储结构、基本运算、算法及不同数据结构得比较与算法分析。三、课程性质、教育目标(一)性质:本课程为计算机系软件技术专业得专业课。(二）得程序,为学习操作系统、编译原理与数据库等课程奠定基础。四、课程教学内容与基本要求第一部分 绪(一)教学内容数据结构得基本概念与术语；抽象数据类型得表示;算法与算法分析。（二)重点、难点重点：数据结构得基本概念及相关术语。难点：算法得时间复杂度分析。(三）教学基本要求知识要求:了解：抽象数据类型及面向对象概念;理解:算法得定义及算法得特性；掌握:数据结构得基本概念、算法得性能分析与度量方法第二部分 线性表(一)教学内容线性表得定义及操作；线性表得顺序存储定义及操作实现；３.单链表得定义;单链表中得插入与删除;带表头结点得单链表;静态链表;４.循环链表得类定义及运算;双向链表得类定义及运算;线性表得应用:多项式及其相加。（二)重点、难点重点：顺序表得数组定义方式及实现,单链表得定义及实现。难点:循环链表与双向链表得定义及实现。(三)教学基本要求知识要求：了解:静态链表。理解:线性表得定义及操作。掌握:顺序表得数组定义方式及实现,单链表、循环链表与双向链表得定义及实现第三部分 栈与队列(一)教学内容示上得基本运算;栈得应用；及基本运算;(二)重点、难点重点:栈得定义及实现;队列得定义及实现。难点：栈得应用中得表达式求值;循环队列(队列得顺序存储)。(三)教学基本要求知识要求：了解:队列得应用。理解:栈得应用中得递归算法。掌握:栈得定义及实现；队列得定义及实现。栈得应用中得表达式求值;循环队列(队列得顺序存储)。第四部分 串、数组与广义(一)教学内容字符串得抽象数据类型;字符串操作得实现;字符串得模式匹配数组得逻辑结构定义与存储方法;特殊矩阵与稀疏矩阵得压缩存储方法;广义表得概念；广义表得表示及操作;广义表存储结构得实现；(二)重点、难点重点:串与数组得基本概念、存储结构。广义表得概念与存储结构及其相关运算得实现。难点:串得模式匹配算法,特殊矩阵与稀疏矩阵得压缩存储。(三)教学基本要求知识要求:了解:串得一些基本处理操作、矩阵得相关运算。理解:广义表得递归算法。掌握：串与数组得基本概念、存储结构。广义表得概念与存储结构及其相关运算得实现。串得模式匹配算法，特殊矩阵与稀疏矩阵得压缩存储。第五部分 树与二叉(一)教学内容树得基本概念;二叉树得定义、性质、存储表示及相关运算;二叉树得遍历；线索二叉树;森林与二叉树得相互转换；哈夫曼树及哈夫曼编码。（二)重点、难点重点:二叉树得定义、性质、存储表示;二叉树得遍历;难点:二叉树得相关运算。(三)教学基本要求知识要求:了解：线索二叉树上得复杂运算实现。理解：二叉树得相关运算。掌握：二叉树得定义、性质、存储表示；二叉树得遍历;森林与二叉树得相互转换;哈夫曼树及哈夫曼编码。第六部分 (一)教学内容1.图得基本概念、存储表示(邻接矩阵、邻接表、十字链表,邻接多重表)；２.图得遍历与连通性:深度优先搜索;广度优先搜索;连通分量;重连通分量;3.最小生成树:克鲁斯卡尔算法;普里姆算法;最短路径;(二)重点、难点重点:图得存储表示;图得遍历;最小生成树;最短路径;难点:关键路径得求解。(三)教学基本要求知识要求:了解:图得存储结构中得邻接多重表。理解:图得遍历算法。掌握：图得存储表示（邻接矩阵、邻接表)；图得遍历;最小生成树;最短路径;拓扑排序、关键路径第七部分 查找（一)教学内容１.静态查找(顺序查找、折半查找、分块查找)；２．动态查找（二叉排序树);3.哈希查找。(二)重点、难点重点：静态查找；二叉排序树得建立。难点:二叉排序树得删除;平衡二叉树得调整。(三)教学基本要求知识要求:了解:查找得相关概念、作用。理解:哈希函数得构造。掌握:静态查找;二叉排序树得相关知识;哈希查找法与解决冲突得方法第八部分 排序(一）教学内容1.排序概念;２.插入排序、交换排序、选择排序、归并排序、基数排序;3.各种排序方法得比较。(二)重点、难点难点:堆排序。(三)教学基本要求知识要求:了解:各种排序方法得时间复杂度得分析方法。理解:排序方法“稳定”或“不稳定”得含义。掌握:各种方法得排序过程及其依据得原则。第九部分 文(一)教学内容1.基本概念;2.文件组织；３.顺序文件、随机文件、索引文件、倒排文件。(二)重点、难点难点:文件得使用。4串、数组与广义表4串、数组与广义表34六、学习教学场地、设施要求(课程中得实践部分）34１0０%序号项目(实验)名称学习教学场地、设施要求1线性表得应用2栈与队列得应用实践教学在机房进行，机器需要安装有C言环境。素质要求：具备良好得编程习惯与能力。五、学时（理论与实践）分配表序号 教学内容课时分配理论教学实践教学考核权重１ 绪论 225%２ 线性表 442２%3 栈与队列 55５%5树与二叉树5树与二叉树6图7查找８排序９总文件计４４3%5６25%４42０%4410％4４８％2２2%33串得简单操作4二叉树得算法实现5图得遍历6分块查找7冒泡排序说明:分实践项目列出场地、设施要求,如每个实践项目得场地与设施基本相同,也可以一次性描述。七、考核及评分办法考核得原则:闭卷考试。考核方式:考试；期末考试;笔试(闭卷);各教学环节占总分得比例:实验、作业占30%,