《数据结构》教学大纲.docx

数据结构II
Data Structure II一、课程基本情况
课程类别：学科基础课课程学分：4学分
课程总学时：64学时，其中讲课：44学时，上机：20学时课程性质：必修
开课学期：第3学期先修课程：计算机基础，C语言程序设计
适用专业：信息管理与信息系统教 材：《数据结构》，清华大学出版社，严蔚敏，2011年，C语言版。
开课单位：经济管理学院信息管理系二、课程性质、教学目标和任务
本课程是为了使学生掌握了解数据结构的研究内容及其重要性，掌握常用数据结构，包 括线性表、栈、队列、二叉树和图结构等，并能灵活运用；掌握常用的数据处理各种算法, 并能灵活运用。《数据结构》是一门实践性很强的课程，必须通过上机操作才能掌握所学的 知识，所以要特别强调讲授与上机操作相结合，要保证学生有充分的上机条件。根据实际情 况安排内容，须依据师生之间共同配合与努力情况来决定。
三、教学内容和要求1、数据结构概述（2学时）
（1）了解数据、数据元素、数据结构和抽象数据类型的含义；
（2）理解逻辑结构、物理（存储）结构、顺序存储和链式存储的含义；
（3）掌握算法的定义和特征，算法的描述；算法的时间复杂度，包括最坏和平均时间复杂 度的含义；重点：数据结构相关基本概念
难点：算法的时间复杂度2、线性表（8学时）
（1）了解循环单链表、双向链表和仿真链表的概念；
（2）理解线性结构的概念及线性表上的基本运算；
（3）掌握线性表的顺序存储以及顺序表的元素查找、插入和删除操作；线性表的链式存储 以及单链表上的查找、插入和删除等基本运算的实现； 重点：线性表和顺序表的表示和实现难点：线性表和顺序表的基本运算
3、堆栈和队列（4学时）
（1）了解栈和队列的典型应用；
（2）理解队列的定义及基本运算；循环队列和连队列的实现；
（3）掌握堆栈的定义及基本运算；顺序栈和链栈的实现，熟练掌握入栈和出栈运算的实现 重点：队列和栈的定义及基本运算难点：队列和栈的算法实现
4、数组和广义表（2学时）
（1）了解特殊矩阵的压缩存储及运算；
（2）理解矩阵的压缩存储；
（3）掌握数组的定义、顺序表示和实现重点：数组的顺序表示
难点：特殊矩阵的压缩存储5、数和二叉树（8学时）
（1） 了解二叉树的线索化处理过程；
（2）理解树的孩子表示法和双亲表示法，掌握树的孩子一兄弟表示法；
（3）掌握树和二叉树的定义及基本运算；二叉树的几个重要性质以及二叉树的顺序存储和 链式存储结构的设计；二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法；树与 二叉树的相互转化方法；哈夫曼树的构造和应用；重点：二叉树和树的定义、性质、存储、遍历
难点：哈夫曼树的构造及应用6、图（8学时）
（1）了解求最短路径的迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算；
（2）理解求最小生成树的Prim算法和Kruskal算法；
（3）掌握图的定义以及顶点的度、连通和强连通、生成树等术语；掌握图的邻接矩阵、邻 接链表存储；掌握图的深度优先遍历和广度优先遍历算法；重点：树的存储结构
难点：树的遍历及应用7、查找（6学时）
（1）了解B树的定义及查找过程；
（2）理解二叉排序树的定义、创立、插入、删除和查找算法及查找效率分析；
（3）掌握静态查找、动态查找的定义及平均查找长度的定义；顺序查找算法、二分查找及 查找效率分析；哈希表重点：静态查找表的应用
难点：动态查找表和哈希表的应用8、内部排序（6学时）
（1）了解基数排序方法；
（2）理解归并排序算法及算法效率分析；
（3）掌握基本的插入排序算法、希尔排序算法及算法效率分析；冒泡排序、快速排序算法 及算法效率分析；直接选择排序、堆排序算法及算法效率分析；重点：插入排序、快速排序、选择排序
难点：归并排序、基数排序四、课程考核
（1）作业等：作业：8次；
（2）考核方式：闭卷考试
（3）总评成绩计算方式：实验成绩占20%、期中考试成绩占20%和期末考试成绩占60%五、参考书目
1、数据结构题集（C语言版），清华大学出版社；严蔚敏、吴伟民著，2003年版；2、算法与数据结构--C语言描述，高等教育出版社；张乃孝主编，2006年版；
3、数据结构与算法分析，电子工业出版社；Clifford A Shaffer著、张铭译，1998年版。