计算机专业（本科）《数据结构》教学大纲

《计算机专业（本科）《数据结构》教学大纲》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》教学大纲课程名称：数据结构课程编号：104300063总学时：54/18适用对象：计算机科学与技术本科专业一、教学目的与任务1、教学目的：《数据结构》是计算机应用专业的一门专业基础课，主要任务是讨论各种数据组织中的数据逻辑结构、存储结构以及相关操作的算法。目的是使学生学会分析研究计算机加工的数据的结构特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。2、教学任务：《数据结构》是实践性很强的课程，不仅要

2、学习基本理论知识，更要注重上机实践，通过上机实践验证算法的正确性，掌握和巩固所学理论知识。通过本课程的学习，要求学生熟练地掌握各种数据组织中的数据逻辑结构、存储结构以及相关操作的算法，掌握排序、查找的程序设计算法。二、教学基本要求教学要求在每章教学内容之后给出。大体分为三个层次：·了解内容：正确理解概念。·掌握内容：学会所讲知识。·熟练掌握内容：会运用所学知识解决实际问题。三、教学内容及要求第一章绪论（一）教学内容1．数据结构的一些基本概念：数据、数据元素、数据记录、数据的逻辑结构、数据的物理结构、数据对象、数据类型、抽象数据类型、算法等2．算法描述中所用的C语

3、言中的一些相关知识3．算法的时间复杂度和空间复杂度分析（二）教学重点与难点算法的时间复杂度和空间复杂度的分析方法。（三）教学要求掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。第二章线性表（一）教学内容1．线性表的基本概念和类型定义2．线性表的顺序存储结构及其算法实现3．线性表的链接式存储结构及其算法实现（包括单链表、双链表和循环链表）4．一元多项式的表示及相加（二）教学重点与难点顺序表和单链表的基本操作算法及其程序实现；多项式求和的算法实现。（三）教学要求掌握线性表的基本概念和类型定义；

4、熟练掌握对顺序表和单链表的基本操作算法及其程序实现；掌握循环链表和双向链表的定义及其插入、删除等算法的实现；掌握一元多项式的表示及相加算法。第一章栈和队列（一）教学内容1．栈的概念和类型定义2．栈的顺序存储结构及其算法实现3．栈的链接式存储结构及其算法实现（包括双栈）4．栈的应用举例（表达式求值）5．队列的概念和类型定义6．队列的顺序存储结构及其算法实现（循环队列）7．队列的链接式存储结构及其算法实现8．队列的应用举例（打印杨辉三角）（二）教学重点与难点顺序栈和链栈、顺序队列和链队列的基本操作算法及其程序实现；利用堆栈实现表达式求值的算法；利用队列实现打印杨辉三

5、角的算法。（三）教学要求掌握栈和队列的定义；熟练掌握顺序和链接存储的栈和队列的各种基本操作算法及其程序实现；掌握在表达式求值和打印杨辉三角的方法中堆栈和队列所起的作用，并了解其算法。第二章串（一）教学内容串的定义、存储结构及其基本算法（二）教学重点与难点串的存储结构及其相应算法的实现；串的模式匹配。（三）教学要求掌握串的定义、存储结构及其相应算法的实现。第三章数组和广义表（一）教学内容1．数组的定义和运算2．数组的顺序存储和实现3．特殊矩阵的压缩存储（1）三角矩阵（2）带状矩阵（3）稀疏矩阵4．广义表（二）教学重点与难点数组的顺序存储结构算法实现；特殊矩阵的压缩

6、存储。（三）教学要求掌握数组的基本概念、顺序存储结构的算法实现；掌握特殊矩阵的压缩存储结构；了解广义表的定义、存储结构和求广义表的长度及深度的算法；了解建立广义表和输出广义表的方法。第四章树和二叉树（一）教学内容1．树的基本概念、性质和表示方法2．二叉树的定义、性质和存储结构3．二叉树的各种遍历方法及其算法实现4．树、森林和二叉树的关系5．哈夫曼树及其应用（1）哈夫曼树（2）哈夫曼编码（3）哈夫曼编码算法的实现6．树的计数（二）教学重点与难点二叉树的基本概念、性质、存储结构及各种遍历算法；哈夫曼树的定义及构造方法；树、森林及二叉树间相互转换的方法；树的计数方法。

7、（三）教学要求掌握树的基本概念、性质、存储结构及遍历算法；熟练掌握二叉树的基本概念、性质、存储结构及各种遍历算法；掌握二叉树的其它操作算法及实现；掌握哈夫曼树的定义及构造方法；了解哈夫曼编码的方法；了解树与二叉树相互转换的方法。第二章图（一）教学内容1．图的定义与基本术语2．图的存储结构（1）邻接矩阵（2）邻接表（3）十字链表表示3．图的遍历（1）深度优先搜索（2）广度优先搜索4．图的连通性问题（1）无向图的连通分量（2）最小生成树5．有向无环图的应用（1）拓扑排序（2）关键路径6．最短路径问题（二）教学重点与难点图的存储结构及遍历算法；图的连通性问题；有向无环

8、图的应用；最短路径问题。