数据结构教学大纲54.doc

课程名称（中文/英文）：数据结构（Data Structure）课程编号：9631214课程类别：专业必修课适用专业：信息管理与信息系统、计算机科学与技术（计算机应用、软件工程、网络工程）总学时数：90，其中讲授：54学时；上机：0学时；实验：36学时；课外： 0 学时一、教学大纲说明1.课程的地位、作用和任务本课程是计算机专业的重要基础技术课程，通过讨论数据的各种逻辑结构、物理结构以及相关算法，使学生能根据实际问题的需要选择合适的数据结构和设计算法，并为学习数据库、操作系统等后继课程打下基础。2.课程教学的目的和要求本课程的教学要求是：要求学生学会分析要求计算机加工的数据对象的特性，以便选择适当的数据逻辑结构和存储结构以及相应的算法，并初步掌握算法的时间分析和空间分析的技巧。另一方面，学习本课程的过程也是进行复杂程序设计的训练过程，训练学生应用各种典型算法进行具体应用问题的程序设计，这包括程序中变量设计、函数中参数设计、程序的书写格式等方面的训练，要求学生书写的程序结构清楚，正确易读。3.课程教学改革设想本课程以培养学生实践能力为中心，在教学中针对不同知识点采取不同教学策略，注重培养学生解决实际问题的能力，在实践课中添加大量练习。并开设了数据结构课程设计课程，培养学生解决综合问题的能力。4.课程与其它课程的联系本课程为专业基础课，在一门语言课作为先行课的基础上，作为其他专业主干课程的先行课。5.教材与教学参考书1）数据结构（C语言版本） 严蔚敏 编 清华大学出版社2）数据结构中国轻工业出版社3）使用数据结构题解 清华大学出版社 徐士良 编著6.考试改革设想及成绩计算方法在考试题目类型的选择上，加大对主观知识考核的比例，在传统题型的分值上做调整，并增加与专业、生活有关的应用题。期末成绩由以下几方面组成：期末笔试，期末机试，平时作业和上机作业（包括独立完成情况和理解情况）。第一章 绪论1、掌握各种基本术语的含义、区别与联系。2、掌握基本的数据结构类型和它们的主要特点，并能举例。3、掌握计算语句频度和估算算法时间复杂度、空间复杂度的方法。重点：四种基本的数据结构类型和时间复杂度的分析。难点：数据结构的定义及这门课的知识体系，并了解数据结构和算法的有关问题。第一节 从问题到程序第二节 抽象数据类型第三节 数据结构第四节 算法第二章 线性表1、掌握线性表的逻辑结构特性。2、熟练掌握线性表的两种不同存储结构（顺序存储结构和链式存储结构）的描述方法和各种基本操作的算法。3、掌握单链表和循环链表。重点：两种存储结构的数据类型定义。单链表的结点结构定义，循环链表的几种基本操作。难点：线性数据结构的存储和处理以及应用。第一节 基本概念与抽象数据类型第二节 顺序存储结构第三节 链式存储结构第四节 应用举例第三章 栈和队列1、了解栈和队列的结构特点及其两种存储结构。2、掌握栈和队列在两种存储结构下实现基本操作的算法。3、熟练掌握栈的链式存储结构和循环队列。重点：两种存储结构的栈和队列表示方法。链表表示栈或队列时栈顶指针或队头、队尾指针初始时指向何处。循环队列的使用。难点：栈和队列和处理以及应用。第一节 栈及其抽象数据类型第二节 栈的实现第三节 栈的应用第四节 对列及其抽象数据类型第五节 队列的实现第四章 串1、了解串的概念及其基本操作。2、了解串的两种存储结构并掌握实现串的各种基本操作。3、理解串的模式匹配算法（KMP算法）。4、了解串变量的存储映象。重点：串的压缩存储和串变量的存储映象。串的模式匹配算法（KMP算法）。难点：串的基本操作和实际应用。第一节 字符串及其抽象数据类型第二节 字符串基本操作第三节 模式匹配算法第五章 数组1、了解数组的定义及其基本操作。2、掌握数组的存储结构。3、掌握特殊矩阵的压缩存储。4、了解稀疏矩阵的压缩存储。重点：数组的存储结构、特殊矩阵的存储和处理、稀疏矩阵的三元组表示和在该存储结构下的矩阵运算。广义表基本操作。难点：数组结构在内存空间中的存储方法。另外为了节省空间，将特殊矩阵和稀疏矩阵采用特殊的存储方法来存储。第一节 数组基本概念第二节 矩阵第六章 树1、握树的定义、各个基本术语以及树的各种存储结构。2、握二叉树的基本概念、性质、各种存储结构的特点及其基本操作的实现。3、熟练掌握二叉树各种遍历算法及其应用。4、 了解线索二叉树的实现方法5、 掌握如何建立哈夫曼树，了解哈夫曼树在编码、判定问题中的应用。6、 了解树、森林与二叉树的转换方法。7、 了解树和森林的遍历。重点：二叉树的各种存储结构的特点及适用范围，对二叉树各种遍历方法和二叉树的应用（二叉排序数和哈夫曼树）。难点：熟练掌握二叉数的性质，懂得在实际应用中使用二叉树解决问题。第一节 树及其它基本概念第二节 二叉树的性质第三节 二叉树的表示与实现第四节 二叉树的遍历第五节 树和森林第六节 二叉树的应用第七章 图1、了解图的基本术语。2、掌握图的各种存储结构及使用原则3、掌握图的深度优先搜索和广度优先搜索算法。4、掌握图生成最小生成树的方法，求最短路径的方法。5、拓扑排序的应用实例和排序过程中栈的变化6、了解网络中的关键路径及其求解。7、了解图的若干应用算法。重点：图的各种存储结构，图的深度优先搜索和广度优先搜索，最小生成树，最短路径，拓扑排序，关键路径。难点：掌握图这种基本的数据结构的特点，在实际应用中图解决问题的方法，例如网络的路由选择，拓扑排序等。第一节 基本概念及其抽象数据类型第二节 图的存储表示第三节 图的遍历第四节 最小生成树第五节 最短路径第六节 拓扑排序第七节 关键路径第八章 查找1、了解查找的基本概念。2、熟练掌握顺序查找、二分查找和分块查找的特点及算法。、3、掌握二叉排序树的构造，查找及删除算法。4、了解哈希表的构造方法和处理冲突的基本方法。5、掌握查找成功时平均查找长度的计算方法。重点：二叉平衡树的构造方法和查找过程以及平均查找长度的计算。哈希函数的构造和解决冲突的方法以及查找过程和平均查找长度的计算。难点：各种查找方法和算法。第一节 顺序查找第二节 二叉查找树和二叉平衡树第三节 散列查找第九章 排序1、了解排序的基本概念。2、熟练掌握各种内部排序方法的算法。3、熟悉各种内部排序方法的特点、性能，能根据不同的实际情况比较、分析、选用不同的内部排序方法。4、了解外部排序的概念和特点。重点：希尔排序、快速排序，2路归并排序，堆排序。难点：各种排序方法和算法。第一节 基本概念第二节 插入排序第三节 选择排序第四节 交换排序第五节 归并排序 三、学时分配教学内容各教学环节学时分配备注章节教学基本内容讲授实验讨论习题实践其它小计第