《数据结构与算法》理论教学大纲1.docx

数据结构与算法理论教学大纲(Data Structure and Algorithm)课程代码：0610009总 学 时：80学时(其中：讲课50学时、实验30学时)先修课程：C语言程序设计一、课程的性质、目的与任务数据结构与算法是数字媒体技术专业的一门重要专业基础课，是计算机及相 关学科的公认主干课。计算机科学各领域及有关的系统和应用软件都要用到各种数据 结构。本课程是计算机科学与技术专业、信息管理和信息系统专业的专业课，主要介 绍用计算机解决一系列问题，特别是非数值计算类问题时所用的各种数据组织方法、 存储结构，以及在各种结构上执行的主要操作。通过本课程的学习，要使学生熟练地 掌握数据结构的内在逻辑关系及其在计算机中的表示方法(存储结构)，以及有关基本 操作的算法实现；熟悉它们在计算机科学中的基本应用；培养和训练学生结合实际应 用，根据求解的问题合理选择数据结构、应用高级语言编写和实现结构清晰、正确易 读的有效算法的能力；并为学习操作系统、数据库原理等后续课程和研制开发 各种系统和应用软件打下扎实的理论和实践基础。二、教学基本内容与基本要求1 .基本内容本课程主要教学基本内容包括：线性表、栈与队列、串、数组和广义表、树和二 叉树、图、查找表、内部排序等。每种数据结构都要介绍数据结构的逻辑结构定义和 物理存储实现以及该数据结构的主要应用。2 .基本要求通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关 系；熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握 设计算法的步骤和算法分析方法；掌握数据结构在排序和查找等常用算法中的应用。三、教学内容及学时分配教学内容教学 要求重点 ()难点 ()学时安排备注第一章绪论1、什么是数据结构B2、基本概念和术语B33、抽象数据类型的表示与实现AA4、算法与算法分析AA第二章线性表1、线性表的类型定义AA2、线性表的顺序表示与实现AA63、线性表的链式表示与实现AA4、一元多项式的表示及相加C第三章栈和队列1、栈AA2、栈的应用举例BA53、栈与递归的实现C4、队列AA第四章串1、串类型的定义CA2、串的表示与实现AA33、串的模式匹配算法B4、串操作应用举例第五章数组与广义表1、数组的定义C2、数组的顺序表示与实现BAr3、矩阵的压缩存储AA04、广义表的定义B5、广义表的存储结构BA第六章树和二叉树1、树的定义和基本术语C2、二叉树AAQ3、遍历二叉树和线索二叉树AAO4、树和森林B5、赫夫曼树及其应用AA第七章图1、图的定义和术语BA2、图的存储结构AA3、图的遍历AA94、图的连通性问题BA5、有向无环图及其应用BA6、最短路径BA（教学要求：A一熟练掌握；B一掌握；C了解） 四、建议实验项目及学时分配第八章查找1、静态查找表2、动态查找表3、哈希表ABAAAA5第九章内部排序1、概述2、插入排序3、快速排序4、选择排序5、归并排序6、基数排序CABABBAAAAA6合计55序 号实验项目名称实验学时内容提要实验 要求实验 类型1单链表的建立、插入和 删除3掌握线性表的链式存储结构 操作算法必做验证2栈的建立、入栈和出栈2掌握栈的操作算法必做验证3队列的建立、入队和出 队3掌握队列的操作算法必做验证4模式串的匹配3掌握串的模式匹配算法必做验证5稀疏矩阵的转置2掌握稀疏矩阵转置的操作算 法必做验证6二叉树操作3掌握用指针类型描述、访问和 处理二叉树的操作算法必做验证7图的最小生成树5掌握图的最小生成树算法必做验证8直接插入排序3掌握直接插入排序操作算法必做验证9哈夫曼编码/译码器6完成一个大作业，利用哈夫曼 树的知识来设计，并在Visual C+6.0环境下实现必做综合合计30五、教学方法与教学手段1 .教学方法：在重视课堂讲授的同时，加强实验教学，培养学生的实际应用能力 及实践能力。在课堂教学中采用启发式、讨论式、参与式等教学方法，调动学生的积 极性和学习兴趣，提高教学质量，促进教学相长。2 .教学手段：利用多媒体、CAI课件等现代化教学手段，提高课堂教学水平。采 取讲练结合、理论联系实际等方式，提高课堂教学效果。六、建议教材与参考书目1 .建议教材：数据结构，严蔚敏、吴伟民编著，清华大学出版社，2008年3月。数据结构题集，严蔚敏，吴伟民编著，清华大学出版社，2004年7月。2 .参考书目：数据结构实践教程，胡元义等编著，西安电子科技大学出版社，2002年。数据结构算法设计指导，胡学钢编著，清华大学出版社，1999年2月。数据结构，黄刘生，唐策善编著，中国科学技术大学出版社，2000年8月。数据结构，王晓东编著，电子工业出版社，2007年7月。七、大纲编写的依据与说明本课程教学大纲，是根据数字媒体技术专业培养目标，结合本课程的性质、教学 的基本任务和基本要求，经学院教学委员会审定后编写的。突出了算法和数据结构， 数据结构与算法的关系。培养数字媒体技术专业的学生结合实际应用，设计有效的算 法和数据结构的能力等重点内容。