《数据结构》课程教学大纲
数据结构课程教学大纲Data Structures一、课程说明课程编码：045523001，课程总学时 51、周学时 3、学分 2.5，开课学期：第 4 学期。1课程性质：数据结构课程是计算机科学与技术、软件工程、教育技术学专业的核心专业课程，为选修课。2适用专业：适用于教育技术学专业。3课程教学目的与要求重视培养基本的理论分析能力和综合设计实现能力，掌握数据结构与算法中的概念技术，合理组织数据，高效处理数据的典型算法，培养学生面对实际问题时选择恰当数据结构和相应算法的能力，通过创新的变通、组合，提高学生上机协作解决较大规模问题的能力，进一步提高程序设计技能，为进一步的应用开发打下良好基础。4本门课程与其它课程关系本课程的先修课程为C 语言程序设计 和离散数学 。5推荐教材及参考书推荐教材：1 E.Horowitz, S.Sahni, S.Anderson-Freed 著, 朱仲涛译. 数据结构基础 (C 语言版)(第2 版). 清华大学出版社, 2009.参考书：2 严蔚敏,吴伟民. 数据结构 (C 语言版). 北京: 清华大学出版社 ,1997.3 Mark Allen Weiss, 冯舜玺译. 数据结构与算法分析 (C 语言描述). 北京: 机械工业出版社, 20046课程教学方法与手段本课程采用课堂教学与实践教学相结合的方式进行教学，其实践教学环节在课程内完成。教学方法如下：课堂教学：课堂教学应在讲解的同时，采用引导式教学方法，让学生融入课堂思考，把握好课堂节奏，同时对程序设计方法（如何实现）予以足够的重视。实践性作业:课程实验通常为中小型程序程序设计题目，共完成 5 个。要求用 Word 排版完成相应的实验报告。辅助教学手段：提供网络教学手段，所有的课件、作业、答案、以往试卷全部上网供下载。提供专门的网上讨论区和答疑 Email，为学生进行答疑。7课程考试方法与要求该课程是考试（选修）课程，成绩由 3 部分组成：平时作业、上课情况成绩（20%）实验成绩（20%）期末考试（卷面，闭卷考试） （60%）二、教学内容与学时分配教 学 内 容 与 时 间 安 排 表序号 内 容 总课时 理论课时 实践课时一 绪论：基本概念、算法及复杂度分析 4 4 0二 线性结构：线性表、栈、队列 12 6 6三树形结构：树与森林、二叉树逻辑结构及其存储结构、Huffman 树13 8 5四图：图的基本概念、图的存储结构、图的遍历、最小生成树、有向无环图6 6 0五查找：查找的基本概念、顺序查找、折半查找、二叉搜索树、散列表查找7 4 3六内部排序：基本概念、插入排序、希尔排序、快速排序、堆排序、归并排序、排序算法分析9 6 3（一） 绪论（4 学时）1主要内容课程介绍；数据、数据结构、数据类型等基本概念，算法、算法描述、算法分析，对数级复杂度算法举例。2基本要求理解基本概念，熟练掌握数据的逻辑结构与存储结构，掌握 ADT 概念并会写 ADT，掌握时间和空间复杂度分析方法，并能通过实际编程测量算法运行时间比较算法，掌握顺序查找和折半查找算法。（二） 线性结构 （12 学时） 1主要内容线性表：顺序表、单链表、双链表、循环链表、各种表示下操作的实现及应用，栈：顺序栈、链栈、栈和递归、栈的应用，队列：链队列、循环队列、队列应用实验一：线性表实验实验二：栈和队列实验2基本要求 熟练掌握顺序表、单链表、双向循环链表，熟练掌握顺序栈和链栈及应用，理解栈和递归，熟练掌握链队列和循环队列，能用队列解决排队问题。（三） 树形结构 （13 学时） 1主要内容 二叉树：概念和性质、存储结构、遍历、线索二叉树、二叉树的应用，树的存储结构，树与森林的定义、遍历与转换方法，哈夫曼树树实验三：二叉树实验2基本要求 熟练掌握二叉树的基本概念和性质，熟练掌握二叉树的存储结构，掌握二叉树的先序、中序、后序和层次遍历方法，掌握二叉树的非递归中序遍历算法，了解线索化二叉树的概念，熟练掌握二叉树的应用，掌握树的存储结构，掌握树与森林的定义、转换方法和遍历。（四） 图 （6 学时）1主要内容 图的概念，图的存储结构，图的遍历，有向无环图，最小生成树。2基本要求掌握图的基本概念，熟练掌握图的邻接矩阵和邻接表表示，了解逆邻接表、十字链表和邻接多重表表示，熟练掌握图的深度和广度优先遍历算法，掌握拓扑排序和关键路径，掌握图的最小生成树。（五） 查找 （7 学时）1主要内容 查找的基本概念，顺序查找，折半查找，二叉搜索树，散列查找：散列函数、处理冲突方法、散列表查找实验四：查找实验2基本要求掌握查找的基本概念，熟练掌握顺序查找和折半查找算法，熟练掌握二叉搜索树的定义、查找、插入和删除操作。熟练掌握散列函数的定义、处理冲突的方法及散列表的查找。（七）内部排序 （9 学时）1主要内容基本概念，插入排序，希尔排序，快速排序，堆排序，归并排序，基数排序，排序算法分析实验五：排序实验2基本要求 掌握基本概念，熟练掌握插入排序、希尔排序、快速排序，掌握堆排序、归并排序，理解基数排序，掌握排序算法的分析。
