《数据结构》教学大纲 (1).doc

数据结构 课程教学大纲开课系信息技术系课程类别修订时间2010年12月学分4总学时72理论56实验/上机16课 程 简 介课程简介 数据结构是信息管理与信息系统专业、计算机科学与技术专业的一门专业基础课，也是计算机科学与技术专业的核心课程。它涉及数学、计算机硬件、计算机软件等学科，它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统等系统程序和大型应用程序的基础。课 程 大 纲一、课程的性质与任务数据结构是信息管理与信息系统专业、计算机科学与技术专业的一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的目的和任务是使学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，提高运用数据结构解决实际问题的能力。二、课程的目的与基本要求1. 从数据结构的逻辑结构、存储结构和数据的运算三个方面去掌握线性表、栈、队列、串、数组、树、图等常用的数据结构。2掌握在各种常用的数据结构上实现的排序和查找运算。3. 对算法的时间和空间复杂性有一定的分析能力。 4. 针对简单的应用问题，应能选择合适的数据结构及设计有效的算法解决。三、面向专业计算机科学与技术、信息管理与信息糸统。四、先修课程离散数学和高级语言程序设计五、本课程与其它课程的联系本课程的先修课程为离散数学和高级语言程序设计，后续课程为操作系统等。数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的实例均是用C/C+语言实现的，故要求较熟练地掌握C/C+语言。六、教学内容安排、要求、学时分配及作业第一章 绪论 （2学时，作业1 次）教学内容： 1.2 有关概念和术语 (B) 1.3 算法及算法分析 (A)本章重点： 算法分析中的时间复杂度和空间复杂度。第二章 线性表 (6学时，作业1次)教学内容：21 线性表的逻辑结构 (B) (2学时)22 线性表的顺序存贮及操作实现 (A) (2学时)23 线性表的链式存贮及操作实现。 （A）（2 学时）本章重点： 链式存贮和各种操作实现 。第三章 栈和队列 (6学时，作业1次)教学内容：311 栈的定义及基本运算 (B) (2学时)312 栈的存贮结构和运算实现。 （A）313 栈的应用举例 (A) (2学时)321 队列的定义及基本运算 (B) 322 队列的存贮结构和基本运算的实现. (A) (2学时)本章重点： 掌握栈和队列在两种存储结构上实现的基本运算，及循环队列。第四章 串和数组 (4学时，作业1次)教学内容：41 串 （A） (2学时)42 数组 （B） （2学时）本章重点： 串的基本运算。第五章 树与二叉树 (8学时，作业1次)教学内容：51 树的概念与基本操作 (B) (4 学时)52 二叉树 （A）53 树与森林 (B) (4学时)54 最优二叉树 (A)本章重点： 二叉树的基本操作与哈夫曼树。第六章 图 (10学时，作业1次)教学内容： 61 图的定义和术语 (B) (2学时) 621 邻接矩阵 (A) 622 邻接表 (A) (2学时) 63 图的遍历 (B) 641 最小生成树 (A) (2学时) 642 最短路径 (A) (2学时) 643 拓扑排序 （B） 课程设计 (2学时)本章重点： 图的存贮表示和最小生成树、最短路径。第七章 查找 (8学时，作业1次)教学内容：71 基本概念与术语。（B）（2 学时）72 静态查找表 （A）73 动态查找表 (A) (2学时)741 哈希表与哈希方法 (A) (2学时)742 常用的哈希函数构造方法 (A)743 处理冲突的方法式 （B） （2学时）744 哈希表的查找算法 (A)本章重点： 静态查找算法，动态查找算法和哈希方法。第八章 排序 （8学时，作业1 次）教学内容： 81 基本概念 (B) (2学时) 821 直接插入排序 (A) 822 冒泡排序 (A) 823 简单选择排序 (A) (2学时) 83 快速排序 (A) 84 堆排序 (A) (2 学时) 85 归并排序 (A) 86 基数排序 （A） （2学时） 87 排序方法的比较 (B)本章重点： 各种排序算法的实现.本课程总复习： （4学时）七、实验名称与类别:序号实验名称学时实验类别1单链表的应用约瑟夫环问题2综合型2栈的应用括号匹配2综合型3串的各种操作算法设计2综合型4二叉树的建立及遍历2综合型5最小生成树的实现2综合型6最短路径应用： 社区医院建立2综合型7查找算法设计2综合型8排序算法设计2综合型注:实验类别指:演示型、操作型、验证型、综合型、设计型、研究创新型八、实验目的、内容与要求实验1实验目的：熟悉循环链表的建立，删除等算法设计、及应用。实验内容：课本9.2 综合应用实例：约瑟夫环问题。实验要求：问题的分析、程序设计、调试、运行。在此基础上编写实验报告实验2实验目的：熟悉栈的特点，和顺序存贮的算法设计。实验内容：栈的初始化、入栈、出栈和主函数算法设计。实验要求：理解课本中栈的有关算法。准备验证的表达式。并对实验结果分析。实验3实验目的： 熟悉串的各种算法设计。实验内容： 求串长、串的连接运算、串的比较、串的插入、串的删除等实验要求： 设计各种算法，并以菜单方式调用各个子函数。实验4实验目的： 熟悉二叉树的链式存贮和访问方式。实验内容： 二叉树的建立、前序、中序、后序遍历，结点数和叶子结点数统计。实验要求： 理解二叉树的存贮方式，遍历规则。设计算法，分析计算结果。实验5实验目的： 熟悉最小生成树的定义和建立最小生成树的方法。实验内容： prim算法设计。实验要求：理解生成树的规则，设计算法，分析结果。实验6实验目的： 综合应用图的存贮方法，最短路径。实验内容： 根据例6.2算法，确定社区医院的最佳位置。实验要求：设计算法，调试运行，分析结果，完成实验报告。实验7实验目的： 理解查找算法的原理，熟悉算法设计。实验内容： 顺序查找、折半查找、哈希查找。实验要求：熟悉查找方法、设计算法、分析结果。实验8实验目的： 理解排序算法原理，熟悉算法设计。实验内容： 冒泡排序、选择排序、快速排序。实验要求：设计算法、分析结果，比较不同方法的优缺点.九、教材与参考书本课程选用教材:数据结构C语言版，邓文华主编，电子工业出版社出版,2009年.本课程推荐参考书:1、数据结构教程，王艳春主编，北京航空航天大学出版社，2004年.2、数据结构习题与解析，李春葆主编，清华大学出版社,2008年.十、本课程理论课及实验课的考核方式理论课考核方式：闭卷实验课考试方式：根据算法的运行结果和实验报告评分。执笔: 刘吉林2010-11-14审核:批准人: