2010版030531005数据结构教学大纲-.pdf

《2010版030531005数据结构教学大纲-.pdf》由会员分享，可在线阅读，更多相关《2010版030531005数据结构教学大纲-.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构课程教学大纲 课程代码：030531005 课程英文名称：Data Struct 课程总学时：56 讲课：48 实验：8 上机：适用专业：计算机科学与技术 大纲编写（修订）时间：2010.7 一、大纲使用说明（一）课程的地位及教学目标 数据结构课程是计算机及信息相关专业的一门重要的专业基础课,它较详细地阐述了使用计算机解决具体问题时所建立的数学模型的逻辑结构与存储结构的多种类型以及对数据具体进行操作的算法实现。通过本课程的学习，使学生掌握使用高级语言编程时组织数据的基本理论和方法，是学生进一步学习其他专业课程的必备基础。通过本课程的学习，学生将达到以下要求：1掌握数据结构的种类及其特

2、点；2掌握不同数据结构的不同存储结构的定义；3具有在不同存储结构上编写各种操作算法的能力；4运用数据结构知识处理实际问题。（二）知识、能力及技能方面的基本要求 1.知识：掌握几种典型数据结构及其逻辑结构、物理结构、基本操作实现。2.能力：要求学生了解各种形式多样的客观问题中所涉及的数据对象，通过适当的分析，得到数据的逻辑结构、物理结构。提高数据的分析能力、数据结构的物理结构的定义能力、编写算法的能力、算法的分析能力等。3.技能:运用不同的数据结构在不同的存储结构上解决实际问题的技能，能运用高级语言正确定义数据的逻辑结构和选择有效的存储结构。在解决具体问题时，充分考虑其操作的实现算法应注重时间效

3、率和空间效率。对查找与排序技术，应掌握基本的算法，并学会合理使用。（三）实施说明 1教学方法：课堂讲授中要重点对基本概念、基本方法和解题思路的讲解；采用启发式教学，培养学生思考问题、分析问题和解决问题的能力；引导和鼓励学生通过实践和自学获取知识，培养学生的自学能力；增加讨论课，调动学生学习的主观能动性；注意培养学生提高利用标准、规范及手册等技术资料的能力。讲课要联系实际并注重培养学生的创新能力。2教学手段：本课程属于专业基础课，在教学中采用电子教案、CAI课件及多媒体教学系统等先进教学手段，以确保在有限的学时内，全面、高质量地完成课程教学任务。（四）对先修课的要求 本课程的教学必须在完成先修课

4、程之后进行。本课程主要的先修课程有先行课为：c 语言程序设计。（五）对习题课、实践环节的要求 1对重点、难点章节应安排习题课，例题的选择以培养学生消化和巩固所学知识，用以解决实际问题为目的。2课后作业要少而精，内容要多样化，作业题内容必须包括基本概念、基本理论及设计计算方面的内容，作业要能起到巩固理论，掌握计算方法和技巧，提高分析问题、解决问题能力，熟悉标准、规范等的作用，对作业中的重点、难点，课上应做必要的提示，并适当安排课内讲评作业。学生必须独立、按时完成课外习题和作业，作业的完成情况应作为评定课程成绩的一部分。3每个学生要完成大纲中规定的必修实验，通过实验环节，让学生能熟练完成难度一般的

5、习题。实验成绩作为评定课程成绩的一部分。（六）课程考核方式 1考核方式：考试 2考核目标：在考核学生对数据结构基本概念、数据的逻辑结构、数据的物理结构，数据结构的操作算法及其算法分析，重点考核学生的运用所学知识分析问题与解决问题的能力。3成绩构成：本课程的总成绩主要由三部分组成：平时成绩（包括期中考试、作业情况、出勤情况等）占 20%，实验成绩占 15%，期末考试成绩占 65%。平时成绩由任课教师视具体情况按百分制给出；实验成绩由实验老师参照相关规定按百分制给出，实验无成绩或实验不及格或平时成绩不及格，取消期末考试资格，总成绩直接以不及格计。（七）参考书目 数据结构c 语言描述，姜学军编，中国

6、轻工出版社，数据结构c 语言描述 严蔚敏编，清华大学出版社 二、中文摘要 本课程是计算机科学与技术专业及其相关专业学生必修的一门具有实践环境的重要的专业基础课程。课程通过对数据结构基本知识，数据结构分类及数据的逻辑结构、物理结构和算法操作与实现等几个方面的讲授，使学生掌握基本知识、基本方法，并具有分析解决问题的能力。课程主要内容通过从线性结构、树形结构、图和集合几种不同数据结构的逻辑结构与物理结构及算法的实现，教你学会运用解决实际问题的能力从而为数据结构课程设计、毕业设计和其他相关课程奠定重要的基础。三、课程学时分配表 序号 教学内容 学时 讲课 实验 上机 1 绪论 2 2 0 1.1 什么

7、是数据结构 2 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 2 线性表 10 8 2 2.1 线性表的类型定义 2 2.2 线性表的顺序表示和实现 2 2.3 线性表的链式表示和实现 2 2.4 一元多项式的表示及相加 2 线性表实验 2 3 栈和队列 6 6 0 3.1 栈 2 3.2 栈的应用举例 2 3.3 队列 2 4 数组和广义表 2 2 0 4.1 数组的定义 2 4.2 数组的顺序表示和实现 4.3 矩阵的压缩存储 5 树和二叉树 12 10 2 5.1 树的定义和基本术语 2 5.2 二叉树 2 5.3 遍历二叉树和线索二叉树 2 5.4

8、树和森林 2 5.5 赫夫曼树及其应用 2 树和二叉树实验 2 6 图 10 8 2 6.1 图的定义和术语 2 6.2 图的存储结构 6.3 图的遍历 2 6.4 图的连通性问题 2 6.5 有向无环图及其应用 2 图实验 2 7 查找 6 6 0 7.1 静态查找表 2 7.2 动态查找表 2 7.3 哈希表 2 8 排序 8 6 2 8.2 插入排序 2 8.3 快速排序 1 8.4 选择排序 2 8.5 归并排序 1 排序实验 2 合计 56 48 8 四、教学内容及基本要求 第 1 部分 绪论 总学时(单位：学时):2 讲课：2 实验：0 上机：0 第 1.1部分 什么是数据结构(讲

9、课学时 0.5)具体内容:1)明确本课程的学习目的；2)明确本课程的内容、性质和任务。第 1.2部分 基本概念和术语(讲课学时 0.5)具体内容:1)掌握数据结构学习的重点及学习方式；2)掌握数据结构及相关术语。重 点:数据结构的种类、抽象数据类型概念。第 1.3 部分 抽象数据类型的表示与实现(讲课学时 0.5)具体内容:1)掌握 C 语言表示方式 2)掌握几种语句、三种程序流程、函数表示方式。第 1.4 部分 算法和算法分析(讲课学时 0.5)具体内容:1)掌握算法表示 2)掌握算法效率分析 第 2 部分 线性表 总学时(单位：学时):10 讲课:8 实验:2 上机:第 2.1部分 线性表

10、的类型定义(讲课学时 2)具体内容:1)掌握线性结构的特点 2)掌握线性表的逻辑结构及基本操作 第 2.2部分 线性表的顺序表示和实现(讲课学时 2)具体内容:1)掌握线性结构顺序存储结构的表示 2)掌握线性表顺序存储结构上基本操作的实现 重 点:线性表的顺序存储结构上插入、删除操作的实现。第 2.3部分 线性表的链式表示和实现(讲课学时 2)具体内容:1)掌握线性结构链式存储结构的表示 2)掌握线性表链式存储结构上基本操作的实现 重 点:线性表的链式存储结构上插入、删除操作的实现。难 点:双向链表插入、删除操作的实现。习 题:1）线性表的合并。2）线性表的逆置。第 2.4部分 一元多项式的表

11、示及相加(讲课学时 2)线性表实验（2 学时）第 3 部分 栈和队列 总学时(单位：学时):6 讲课:6 实验:0 上机:0 第 3.1 部分 栈(讲课学时 2)具体内容:1)掌握栈的特点；2)掌握栈在顺序和链式存储结构上操作的实现。重 点:进栈、出栈操作的实现。第 3.2 部分 栈的应用举例(讲课学时 2)具体内容:1)掌握利用栈实现表达式求值的过程；2)掌握递归调用过程；难 点:利用栈实现递归过程。习 题:火车调度过程的实现。第 3.3 部分 队列(讲课学时 2)具体内容:1)掌握队列的特点；2)掌握队列在顺序和链式存储结构上操作的实现。重 点:入队、出队操作的实现。难 点:循环队列操作实

12、现。第 4 部分 数组 总学时(单位：学时):2 讲课:2 实验:0 上机:0 第 4.1 部分 数组的定义(讲课学时 0.5)具体内容:1)掌握 n 维数组的存储结构；2)掌握数组的线性结构特点。第 4.2 部分 数组的顺序表示和实现(讲课学时 1)具体内容:定义数组后，数组中任意数据元素的存取。第 4.3 部分 矩阵的压缩存储(讲课学时 0.5)具体内容:1)掌握特殊矩阵的存储方式（上三角、下三角、三对角、对称矩阵）；2)掌握稀疏矩阵的三元组转置操作的实现 习 题:求三维数组对应存储的一维空间的地址。第 5 部分 树和二叉树 总学时(单位：学时):12 讲课:10 实验:2 上机:第 5.

13、1 部分 树的定义和基本术语(讲课学时 2)第 5.2 部分 二叉树(讲课学时 2)具体内容:1)掌握二叉树的定义及相关术语；2)掌握二叉树的基本形式；3）掌握二叉树的性质；4）掌握二叉树的存储结构。重 点:二叉树的性质 第 5.3 部分 遍历二叉树和线索二叉树(讲课学时 2)具体内容:重 点:1)掌握二叉树链式存储结构上的遍历实现；2)掌握二叉树上如何加线索；3)对于线索二叉树如何操作前驱、后继结点。难 点:二叉树线索操作 第 5.4 部分 树和森林(讲课学时 2)具体内容:1)掌握树的三种存储结构 2)掌握树和二叉树间如何相互转换。重 点:树转换二叉树。第 5.5 部分 赫夫曼树及其应用(

14、讲课学时 2)具体内容:1)掌握哈夫曼树；2)掌握哈夫曼算法；3）掌握哈夫曼编码实现。重 点:哈夫曼编码。难 点:哈夫曼算法的实现。习 题:已知字符及使用频率求哈夫曼编码。实 验:树和二叉树实验（2 学时）第 6 部分 图 总学时(单位：学时):10 讲课:8 实验:2 上机:第 6.1 部分 图的定义和术语(讲课学时 1)具体内容:1)掌握图的基本术语；2)掌握图抽象数据类型的表示；3）掌握图的基本操作；第 6.2 部分 图的存储结构(讲课学时 1)具体内容:1)掌握图的邻接矩阵存储结构；2)掌握图的邻接表存储结构；重 点:邻接表和邻接矩阵存储结构的定义实现。第 6.3 部分 图的遍历(讲课

15、学时 2)具体内容:1)掌握图在两种存储结构上深度遍历算法实现；2)掌握图在两种存储结构上广度遍历算法实现；3）掌握图的深度、广度两种遍历的生成树。重 点:深度遍历和广度遍历两种算法。难 点:Firstadj（）、Nextadj操作实现 第 6.4 部分 图的连通性问题(讲课学时 2)具体内容:1)掌握图的连通分量；2)掌握图的最小生成树；重 点:普利姆算法实现最小生成树 难 点:连通图的最小生成树算法实现。习 题:对于指定的带权图求最小生成树。第 6.5 部分 有向无环图及其应用(讲课学时 2)具体内容:1)掌握 AOV网的拓扑排序；2)掌握 AOE网的关键路径；重 点:拓扑排序、关键路径。

16、难 点:拓扑排序、关键路径生成算法。习 题:1）对已知的 AOV网求拓扑有序序列。2）对已知的 AOD网求关键路径。实 验:图实验（2 学时）第 7 部分 查找 总学时(单位：学时):6 讲课:6 实验:0 上机:0 第 7.1 部分 静态查找表(讲课学时 2)具体内容:1）顺序表的查找。2）有序表的查找。3）索引表的查找。重 点:折半查找 习 题:对于给定的序列画出折半查找树。第 7.2 部分 动态查找表(讲课学时 2)具体内容:1）掌握二叉排序树及其查找。2）掌握平衡二叉树。3）了解 b 树及 b+树。重 点:二叉排序树 难 点:平衡的二叉排序树 第 7.3 部分 哈希表(讲课学时 2)具

17、体内容:1）掌握哈希函数的构造。2）掌握哈希表的构造。习 题:建立哈希表 第 8 部分 排序 总学时(单位：学时):8 讲课:6 实验:2 上机:第 8.1 部分 概述 第 8.2 部分 插入排序(讲课学时 2)具体内容:1）掌握直接插入排序。2）掌握折半插入排序。3）掌握其他的插入排序。重 点:直接插入排序 第 8.3 部分 快速排序(讲课学时 1)具体内容:1）掌握快速排序过程及算法实现。2）掌握一般交换排序过程及算法实现。重 点:快速排序 第 8.4 部分 选择排序(讲课学时 2)具体内容:1）掌握简单选择排序算法。2）掌握堆的概念。3）掌握堆排序算法的实现。重 点:简单选择排序 堆排序 难 点:堆排序的实现。第 8.5 部分 归并排序(讲课学时 1)具体内容:1）掌握两个有序序列的归并过程。2）掌握归并算法的实现。实 验:排序实验（2 学时）编写人：李筠 姜学军 虞闯 审核人：姜学军 批准人：张焕君