金陵科技学院·信息技术学院《数据结构与算法》教学大纲DataStructureandAlgorithm适用专业：计算机科学与技术（软件工程）专业课程编号：0601006前修课程：高级语言程序设计、离散数学学分：4.5总学时：72一、课程性质、目的与要求课程性质：专业基础必修课、主干课课程目的：本课程是计算机专业的主干课、专业基础课。主要介绍用计算机解决一系列问题、特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。本课程是编译技术、操作系统、数据库原理等课程的重要基础。教学要求：通过教学，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用。培养、训练学生选用合适的数据结构和编写质量高、风格好的算法设计和程序设计应用程序的能力，并为后续课程的学习打下良好的理论基础和实践基础。二、教学内容理论总学时：56学时第一章绪论2学时基本要求：了解《数据结构》所研究的问题，理解数据结构的基本概念，及抽象数据类型和软件构造方法，掌握算法的概念、算法设计的要求和算法效率的度量方法。了解算法的书写规范。重点：数据的逻辑结构和存储结构。算法时间复杂度的计算难点：算法的时间复杂度的计算。第二章线性表8学时基本要求：掌握线性表的类定义、抽象数据类型；掌握顺序表的逻辑及存储结构、插入、删除等操作实现。掌握单链表的结构、各操作的实现。了解循环单链表、双向链表、静态链表的概念及特点。重点：线性表结构的类定义和特点；顺序表和单链表的组织方法、特点和操作实现算法。附件二金陵科技学院·信息技术学院难点：顺序表的插入、删除操作的实现算法；单链表的各操作的实现算法。第三章堆栈和队列8学时基本要求：了解堆栈的基本概念、抽象数据类型。掌握顺序堆栈的存储结构、类定义及实现；掌握链式堆栈的存储结构、类定义及实现；掌握应用堆栈解决问题的方法。了解队列的基本概念、抽象数据类型；掌握顺序队列及其实现、了解链式队列的存储结构、实现及应用。重点：顺序堆栈、链式堆栈的存储结构、类定义及实现；应用堆栈解决问题的方法；顺序队列及其实现。难点：应用堆栈解决问题的方法；顺序循环队列的基本原理、队空和队满的判断问题。第四章串2学时基本要求：了解串的基本概念、抽象数据类型；掌握串函数的功能、串的存储结构；掌握顺序串的类定义及实现；掌握串的模式匹配算法。重点：顺序串的类定义及实现；掌握串的模式匹配算法。难点：串的模式匹配算法。第五章数组2学时基本要求：了解数组的基本概念；掌握动态数组类的定义和实现；了解特殊矩阵和稀疏矩阵的定义、压缩存储。重点：动态数组类的定义和实现。难点：动态数组类的定义和实现；特殊矩阵和稀疏矩阵的定义及压缩存储。第六章递归算法2学时基本要求：掌握递归的概念、递归算法的执行过程；掌握递归算法的设计方法，递归过程和运行时栈；了解递归算法的效率分析方法；了解递归算法到非递归算法的转换思想。重点：递归算法的执行过程；递归算法的设计方法；递归过程和运行时栈。难点：递归算法的执行过程；递归算法的设计方法；递归过程和运行时栈；递归算法到非递归算法的转换思想。第七章树和二叉树8学时基本要求：理解树的定义、表示方法、抽象数据类型、存储结构；掌握二叉树的定义、抽象数据类型、性质、存储结构；掌握二叉树的结点类定义和实现；掌握二叉树的遍历方法、实金陵科技学院·信息技术学院现及应用、二叉树类的设计；了解线索二叉树的概念和实现思想；掌握哈夫曼树的构造及哈夫曼编码的设计方法；掌握树与二叉树的转换、树的遍历方法。重点：二叉树的遍历；哈夫曼树的构造及哈夫曼编码的设计；树与二叉树的转换。难点：二叉树的遍历；线索二叉树的概念。第八章图8学时基本要求：了解图的基本概念、相关术语和抽象数据类型；掌握图的存储结构；了解领结矩阵图类的设计和实现；掌握图的遍历及函数实现；掌握最小生成树的概念，单源点、多源点的最短路径构造方法；掌握最短路径的概念及构造方法。重点：图的存储结构；图的遍历；最小生成树的构造方法；最短路径的构造方法。难点：图的遍...
