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

《数据结构与算法》理论教学大纲Data Structureand Algorithm课程代码0610009总学时80学时其中讲课50学时、实验30学时先修课程《C语言程序设计》

一、课程的性质、目的与任务《数据结构与算法》是数字媒体技术专业的一门重要专业基础课，是计算机及相关学科的公认主干课计算机科学各领域及有关的系统和应用软件都要用到各种数据结构本课程是计算机科学与技术专业、信息管理和信息系统专业的专业课，主要介绍用计算机解决一系列问题，特别是非数值计算类问题时所用的各种数据组织方法、存储结构，以及在各种结构上执行的主要操作通过本课程的学习，要使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法存储结构，以及有关基本操作的算法实现；熟悉它们在计算机科学中的基本应用；培养和训练学生结合实际应用，根据求解的问题合理选择数据结构、应用高级语言编写和实现结构清晰、正确易读的有效算法的能力；并为学习《操作系统》、《数据库原理》等后续课程和研制开发各种系统和应用软件打下扎实的理论和实践基础

二、教学基本内容与基本要求

1.基本内容本课程主要教学基本内容包括线性表、栈与队列、串、数组和广义表、树和二叉树、图、查找表、内部排序等每种数据结构都要介绍数据结构的逻辑结构定义和物理存储实现以及该数据结构的主要应用

2.基本要求通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序和查找等常用算法中的应用

三、教学内容及学时分配教学要重点难点学时教学内容备注求☆△安排第一章绪论

1、什么是数据结构B☆

2、基本概念和术语B

33、抽象数据类型的表示与实现A A

4、算法与算法分析A☆A第二章线性表

1、线性表的类型定义A☆A

2、线性表的顺序表示与实现A A

63、线性表的链式表示与实现A A

4、一元多项式的表示及相加C第三章栈和队列

1、栈A☆A

2、栈的应用举例B A

53、栈与递归的实现C

4、队列A☆A第四章串

1、串类型的定义C A

2、串的表示与实现A☆A

33、串的模式匹配算法B☆

4、串操作应用举例第五章数组与广义表

1、数组的定义C

2、数组的顺序表示与实现B Ar

03、矩阵的压缩存储A☆A

4、广义表的定义B

5、广义表的存储结构B A第六章树和二叉树

1、树的定义和基本术语C

2、二叉树A AQ O

3、遍历二叉树和线索二叉树A☆A

4、树和森林B

5、赫夫曼树及其应用A A第七章图

1、图的定义和术语B A

2、图的存储结构A A

3、图的遍历A A

94、图的连通性问题B☆A

5、有向无环图及其应用B☆A

6、最短路径B☆A第八章查找

1、静态查找表A A B

52、动态查找表A

3、哈希表A A☆第九章内部排序C

1、概述A

2、插入排序A B

3、快速排序A6A

4、选择排序☆AB A

5、归并排序BA

6、基数排序☆合计55（教学要求A一熟练掌握；B一掌握；C—了解）

四、建议实验项目及学时分配实验实验实验序实验项目名称内容提要号学时要求类型单链表的建立、插入和掌握线性表的链式存储结构13必做验证删除操作算法2栈的建立、入栈和出栈2掌握栈的操作算法必做验证队列的建立、入队和出33掌握队列的操作算法必做验证队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月

七、大纲编写的依据与说明本课程教学大纲，是根据数字媒体技术专业培养目标，结合本课程的性质、教学的基本任务和基本要求，经学院教学委员会审定后编写的突出了算法和数据结构，数据结构与算法的关系培养数字媒体技术专业的学生结合实际应用，设计有效的算法和数据结构的能力等重点内容。