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

《数据结构与算法》理论教学大纲(DataStructureandAlgorithm)课程代码：0610009总学时：80学时(其中：讲课50学时、实验30学时)先修课程：《C语言程序设计》、《离散数学》一、课程的性质、目的与任务《数据结构与算法》是数据科学与大数据技术、计算机科学与技术专业的一门重要专业基础课，是计算机及相关学科的公认主干课。计算机科学各领域及有关的系统和应用软件都要用到各种数据结构。本课程是数据科学与大数据技术、计算机科学与技术专业的专业课，主要介绍用计算机解决一系列问题，特别是非数值计算类问题时所用的各种数据组织方法、存储结构，以及在各种结构上执行的主要操作。通过本课程的学习，要使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法(存储结构)，以及有关基本操作的算法实现；熟悉它们在计算机科学中的基本应用；培养和训练学生结合实际应用，根据求解的问题合理选择数据结构、应用高级语言编写和实现结构清晰、正确易读的有效算法的能力；并为学习《操作系统》、《编译原理》、《数据库原理》等后续课程和研制开发各种系统和应用软件打下扎实的理论和实践基础。二、教学基本内容与基本要求.基本内容本课程主要教学基本内容包括：线性表、栈与队列、串、数组和广义表、树和二叉树、图、查找表、内部排序等。每种数据结构都要介绍数据结构的逻辑结构定义和物理存储实现以及该数据结构的主要应用。.基本要求通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序和查找等常用算法中的应用。三、教学内容及学时分配

教学内容教学要求重点(☆)难点(△)学时安排备注第一章绪论1、什么是数据结构B☆2、基本概念和术语B33、抽象数据类型的表示与实现AA4、算法与算法分析A☆A第二章线性表1、线性表的类型定义A☆A2、线性表的顺序表示与实现AA63、线性表的链式表示与实现AA4、一元多项式的表示及相加C第三章栈和队列1、栈A☆A2、栈的应用举例BA53、栈与递归的实现C4、队列A☆A第四章串1、串类型的定义CA2、串的表示与实现A☆A33、串的模式匹配算法B☆4、串操作应用举例第五章数组与广义表1、数组的定义C2、数组的顺序表示与实现BAr3、矩阵的压缩存储A☆Au4、广义表的定义B5、广义表的存储结构BA第六章树和二叉树1、树的定义和基本术语C2、二叉树AAQ3、遍历二叉树和线索二叉树A☆AO4、树和森林B5、赫夫曼树及其应用AA

（教学要求：A一熟练掌握；B一掌握；C—了解）四、建议实验项目及学时分配第七章图1、图的定义和术语BA2、图的存储结构AA3、图的遍历AA94、图的连通性问题B☆A5、有向无环图及其应用B☆A6、最短路径B☆A第八章查找1、静态查找表AA52、动态查找表B☆A3、哈希表AA第九章内部排序1、概述C2、插入排序AA3、快速排序B☆A64、选择排序AA5、归并排序B☆A6、基数排序BA合计55序a实验项目名称实验学时内容提要实验要求实验类型1单链表的建立、插入和删除3掌握线性表的链式存储结构操作算法必做验证2栈的建立、入栈和出栈2掌握栈的操作算法必做验证3队列的建立、入队和出队3掌握队列的操作算法必做验证4模式串的匹配3掌握串的模式匹配算法必做验证5稀疏矩阵的转置2掌握稀疏矩阵转置的操作算法必做验证6二叉树操作3掌握用指针类型描述、访问和处理二叉树的操作算法必做验证7图的最小生成树5掌握图的最小生成树算法必做验证8直接插入排序3掌握直接插入排序操作算法必做验证9哈夫曼编码/译码器6完成一个大作业，利用哈夫曼树的知识来设计，并在VisualC++6.0环境下实现必做综合合计30五、教学方法与教学手段.教学方法：在重视课堂讲授的同时，加强实验教学，培养学生的实际应用能力及实践能力。在课堂教学中采用启发式、讨论式、参与式等教学方法，调动学生的积极性和学习兴趣，提高教学质量，促进教学相长。.教学手段：利用多媒体、CAI课件等现代化教学手段，提高课堂教学水平。采取讲练结合、理论联系实际等方式，提高课堂教学效果。六、建议教材与参考书目.建议教材：①《数据结构》，严蔚敏、吴伟民编著，清华大学出版社，2008年3月。②《数据结构题集》，严蔚敏，吴伟民编著，清华大学出版社，2004年7月。.参考书目：①《数据结构实践教程》，胡元义等编著，西安电子科技大学出版社，2002年。②《数据结构算法设计指导》，胡学钢编著，清华大学出版社，1999年2月。③《数据结构》，黄刘生，唐策善编著，中国科学技术大学出版社，2000年8月。④《数据结构》，王晓东编著，电子工业出版社，2007年7月。七、大纲编写的依据与说明本课程教学大纲，是根据数据科学与大数据技术专业培养目标，向计算机软件方向拓展的要求，结合本课程的性