数据结构教学大纲(新).doc

集美大学数据结构课程教学大纲 第1 页共 5页课程名称中文：数据结构英文：data structure 课程编号8027410学分/学时3.5/72所属教研室信息教研室先修课程C语言 课程类型必修考核方式闭卷考试开课专业信息管理与信息系统教学目的和要求数据结构是计算机专业的必修课，在整个计算机软件体系中有重要的作用，但同时也是一门较难理解的课程。通过这门课的学习，希望学生能掌握链表，树，图，排序和查找的基础知识，从而为以后的工作和学习打下基础。通过学习,学生应达到如下要求:1 本课程要求学生具有良好的编程能力和程序调试能力。2 掌握一些常见的数据结构和非数值算法,并要求灵活应用教学内容和基本要求（分章节）第一章 绪言（一）关于数据结构的基本概念和术语（二）算法和算法分析，包括时间复杂度和空间复杂度本章基本要求：掌握基本概念，熟练计算算法的时间复杂度本章的重点：算法的时间复杂度的计算。本章的难点：算法的时间复杂度的计算 第二章 线性表（一）线性表的类型定义（二）线性表的顺序表示和实现（三）线性表的链式表示 本章的基本要求：了解线性表的性质，熟练使用数组和链表的基本操作 本章的重点：链表的基本操作 本章的难点：链表的灵活应用第三章 栈和队列（一）栈的定义，表示和应用（二）递归的定义和编程，递归和非递归的转换（三）队列的定义，表示和应用 本章基本要求：熟练掌握栈和递归的性质，和应用 本章的重点：栈的应用 本章的难点：递归和非递归的转换第四章 串（一）串类型的定义（二）串的表示和实现，KMP算法 本章基本要求：串的基本操作，串的模式匹配算法 本章的重点：串的模式匹配算法 本章的难点:KMP算法第五章 数组和广义表（一）稀疏矩阵的定义和表示（二）三元组的基本操作， 本章基本要求：掌握稀疏矩阵的表示方法，和三元组的基本算法 本章的重点：三元组的基本算法 本章的难点：三元组的转置 第六章 树和二叉树（一）树的定义和概念，二叉树的定义和性质（二）二叉树的遍历（三）哈夫曼树的定义，性质和应用本章的基本要求：二叉树的遍历，性质，哈夫曼树的定义，性质和应用本章重点：二叉树的遍历本章难点：二叉树的非递归遍历第七章 图（一）图的定义和性质，图的存储方法（二）图的遍历（三）最小生成树的定义和算法（四）简单介绍其他常见的图的算法本章基本要求：掌握图的基本性质，图的遍历，最小生成树本章重点：图的遍历本章的难点：图的存储和遍历第八章 动态存储管理（略）第九章 查找（一）顺序查找，二分查找，索引查找（二）哈希表的定义，解决冲突的基本方法（三）二叉排序树的基本算法 本章基本要求：掌握基本的查找算法 本章的重点：哈希表，二分查找，二叉排序树 本章的难点：二叉排序树的删除算法第十章 内部排序（一）内部排序的基本概念（二）插入排序（三）快速排序（四）选择排序（五）归并排序（六）基数排序（七）各种算法的比较 本章基本要求：熟练掌握各种排序算法 本章重点：堆排序，快速排序，各种算法的比较 本章难点：堆排序，快速排序，基数排序 第十一章（略） 第十二章 （略）集美大学数据结构课程教学大纲 课程实验大纲1.实验项目与学时分配序号实验项目学时必开/选开实验类型备注1线性表在顺序存储结构上的插入和删除操作2必开设计2单链表的插入和删除2必开设计34567装箱问题的BFD算法建立二叉树并遍历对以邻接矩阵为存储结构的图进行DFS和BFS遍历几种基本排序算法的实现8222公开必开公开公开设计设计设计设计 （备注：实验类型包括演示、验证、综合、设计等，可填写开展实验教学的特殊要求）2.实验教学大纲实验一：线性表在顺序存储结构上的插入和删除操作实验目的：熟练掌握数组的插入和删除操作,更深刻的理解数组插入和删除中的缺陷实验内容：给出一组数据,用数组存储,随机的进行插入和删除操作实验要求：熟练掌握数组的插入和删除操作实验二: 单链表的插入和删除实验目的：熟练掌握链表的插入和删除的操作,更深刻的理解链式存储在插入和删除中的优点,同时能对双链表,循环链表有所了解实验内容：给出一组数据,用链表存储,随机的实现插入和删除操作实验要求：熟练使用链表的插入和删除,并能了解双链表,循环链表的基本操作实验三: 装箱问题的BFD算法实验目的：通过对BFD算法的实现,能够独立设计链表,并学会链表在现实的应用实验内容:：给出一组物体重量的数据,要求对这些物体装箱,最终使箱子的数目最小,这里要求使用两个链表,一个存放物体的信息,一个存放已经使用的箱子的信息,做完可以实现栈的一些操作，这里要求学生独立设计数据结构和实现算法.实验要求:：要求学生独立设计数据结构和实现算法,熟练使用链表的插入和删除实验四: 建立二叉树并遍历实验目的:：通过实验,要求学生更深刻的理解二叉树的含义,并熟练使用一些基本操作实验内容：随机给出一棵二叉树,把相关信息输入,要求分别采用二叉树的递归和非递归遍历算法实现遍历实验要求：要求学生独立建立二叉树,并可以实现二叉树的递归和非递归遍历算法实验五: 对以邻接矩阵为存储结构的图进行DFS和BFS遍历实验目的：通过实验,要求学生更深刻的理解图的存储方式,和DFS和BFS遍历实验内容：随机给出一副图,把相关信息输入,要求分别使用DFS和BFS遍历算法实现实验要求：:要求学生独立实现DFS和BFS遍历算法,这里要求学生对链式存储和顺序存储均很熟悉实验六: 几种排序算法的实现实验目的：通过实验，要求学生掌握一些性能较好的内排序算法的基本思想实验内容：由于C语言中已经讲解了几种简单的排序方法，这里主要要求学生上机实现堆排序，快速排序