数据结构课程教学大纲.doc

数据结构课程教学大纲课程名称中文：数据结构英文：（Data Structure）课程编号学分/学时3/51所属教研室信息管理与信息系统前后课程先修课程：计算机文化基础、C+程序设计；并行课程：计算机网络、操作系统；后续课程：SQL Server数据库、C#与.NET或Java设计等课程。课程类型专业基础课考核方式考试授课对象05信管AB教学目的具体教学目的：掌握数据组织存储和处理的常用方法和常用的算法思想及在实际中的应用技巧，为今后学习后续专业课和进行软件开发打下良好的基础。教学重点、难点：第一章：（重点）数据结构的基本概念；数据的逻辑结构、存储结构以及二者之间的关系；算法及特性等（难点）抽象数据类型的定义和使用；算法的时间复杂度分析。 第二章：（重点）线性表的顺序存储结构、线性表的链式存储结构；（难点）单链表上的算法设计；双链表操作的实现。 第三章：（重点）栈的存储结构及其基本操作、队列存储结构及其基本操作；（难点）模式匹配KMP算法。 第四章：（重点）特殊矩阵的的压缩存储广义表的定义、术语、存储结构、运算；（难点）递归算法设计。 第五章：（重点）二叉树的遍历、线索算法、哈夫曼树及其应用；（难点）线索算法、哈夫曼树及其应用。 第六章：（重点）图的基本术语、存储结构和图的遍历操作；（难点）图的几个典型应用问题。 第七章：（重点）线性查找、索引查找、动态查找表及查找算法：二叉排序树；（难点）哈希表及查找算法、二叉排序树。 第八章：（重点）各种排序算法的基本思想、执行过程、设计、时间复杂度的分析以及它们之间的比较；（难点）快速排序、堆排序、归并排序等算法的设计。教材和主要参考资料：教 材：数据结构（C+语言描述）（第1版），清华大学出版社、北京交通大学出版社，丁芝芳、刘杰主编，2004年7月参考书：1 数据结构教程（C语言版），希望电子工业出版社，王庆瑞编著， 2数据结构与算法：C+，清华大学出版社，Drozdek A.著， 教学内容学时基本要求课程介绍1了解课程教学大纲等第一章 绪论第一节程序=算法+数据结构第二节数据结构的基本内涵第三节时间复杂度和空间复杂度第四节数据结构与面向对象编程42（上机）1了解程序的概念2熟悉数据的逻辑结构和存储结构3掌握算法的时间复杂度计算第二章 线性表第一节 线性表的逻辑特点第二节 线性表的顺序存储结构循序表第三节 线性表的链式存储过程链表52（上机）1了解线性表的逻辑特点和基本操作2理解顺序存储和链式存储的异同和有缺点3掌握顺序表和单链表的实现第三章 栈和队列第一节栈的概念第二节顺序栈栈的顺序存储表示第三节栈的链式存储结构链栈第四节 队列的基本概念第五节 队列的链式存储结构链队列第六节 队列的顺序存储结构第七节 优先级队列 104（上机）1了解栈和队列逻辑特点和基本操作2理解顺序存储和链式存储下的实现3掌握队列和栈特别是栈在程序设计中的各种应用第四章数组和广义表第一节数组的逻辑特点第二节数组的存储结构第三节特殊矩阵的压缩存储第四节稀疏矩阵的压缩存储第五节稀疏矩阵运算的 实现第六节广义表第七节递归21了解数组和广义表的概念2理解递归算法设计第五章 树和二叉树第一节树的逻辑结构第二节二叉树第三节二叉树遍历第四节线索二叉树第五节堆第六节树和森林第七节哈夫曼树及其应用82（上机）1了解二叉树的定义和特性2理解二叉树的各种遍历算法和重构3掌握二叉树的简单实现4应用哈夫曼树第六章 图第一节图的定义和术语第二节图的存储结构第三节图的遍历第四节图的应用21了解图的概念2了解图的若干应用第七章 查找第一节查找的基本概念第二节线性表查找第三节索引表查找第四节树表查找第五节散列表查找84（上机）1了解查找的概念和原理2理解二叉排序树的原理和查找算法3掌握线性表的查找原理和算法，算法复杂度的计算第八章 排序第一节排序的基本概念第二节插入排序第三节交换排序第四节选择排序第五节归并排序第六节基数排序第七节各种排序方法的比较104（上机）1了解排序的基本概念和基本原理2理解常见的几种排序算法和时间