友情提示:本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案,部分学校更新至2012年,2013年;均提供收费下载。 下载流程: 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
《数据结构》课程教学大纲 学时:68 学分:4 理论学时:34 实验学时:34 适用专业:计算机科学与技术 大纲执笔人:陈凤祥 大纲审定人:齐学梅 一、课程的教学目的: 《数据结构》 是计算机教育专业的一门必修的基础课,教学中将介绍数据、数据结 构和抽象数据类型等基本概念及基本类型的数据结构及其应用。本课程将突出抽象数据 类型的概念,对每一种数据结构,将给出抽象数据类型规范说明和实现方法,培养学生 的数据抽象能力,提高软件设计和编程水平。本课程不仅为后继软件课程提供必要的知 识基础,也为计算机及其应用的专业人员提供必要的技能训练。 二、课程的基本要求: 1. 学会分析研究计算机加工的数据结构的特性; 2. 为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法; 3. 初步掌握算法的时间分析和空间分析的技术。 三、讲授内容: 第一章 绪论 (2 学时) 1.1 数据结构有关概念及术语 1.2 抽象数据类型的表示与实现 1.3 算法描述与分析 了解:数据结构基本概念,数据结构的抽象层次,抽象数据类型。 掌握:算法的性能分析与度量方法。 第二章 线性表 (5 学时) 2.1 线性表的定义及其运算 2.2 线性表的顺序存储结构 2.3 线性表的链表存储结构 2.4 线性表的实现举例 熟练掌握:单链表、循环链表及双向链表的定义及实现 第三章 栈和队列(5 学时) 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 列队 熟练掌握:栈的定义及实现 熟练掌握:队列的定义及实现 第四章 串(4 学时) 4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 熟练掌握:串的定义和实现 了解: 模式匹配算法 第五章 数组和广义表(4 学时) 5.1 数组的定义、顺序表示和实现 5.2 矩阵的压缩存储 5.3 广义表的定义、存储结构 了解:稀疏距阵的定义及其数组实现 掌握:广义表的定义及其实现方法 第六章 树 (10 学时) 6.1 树的基本概念和术语 6.2 遍历二叉树和线索二叉树 6.3 树和森林 6.4 树的应用 6.5 回溯法与树的遍历、树的计数 了解:树和森林的概念 掌握:二叉树的概念、性质及二叉树的表示 掌握:线索化二叉树及寻找某结点的前驱和后继的方法 掌握:树与森林的实现和遍历方法 掌握:霍夫曼树的实现方法 熟练掌握:二叉树的遍历方法 第七章 图(8 学时) 7.1 图的基本概念和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及应用 7.6 最短路径 掌握:图的基本概念和图的存储表示 掌握:构造最小生成树的 Prim 和 Kruskal 方法 掌握:求解关键路径的方法 熟练掌握:活动网络的拓扑排序方法 熟练掌握:图的两种遍历方法与求解连通性问题的方法 第八章 动态存储管理(可放入操作系统课程中讲解) 第九章 查找(8 学时) 9.1 静态查找表 9.2 动态查找表 9.3 哈希表及其查找 熟练掌握:静态搜索表的顺序查找 熟练掌握:二叉搜索树的表示、查找、插入、删除算法及其性能分析方法 熟练掌握:B—树、B+树的查找和构造方法 第十章 排序 (8 学时) 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 内部排序方法的比较讨论 掌握:排序的基本概念和性能分析方法 掌握:插入排序、交换排序、选择排序、归并排序等内部排序的方法及其性能分析 方法 了解:基数排序方法及其性能分析方法 第十一章 外部排序(2 学时) 11.1 外存信息的存取 11.2 外部排序的方法、基本思想 11.3 多路平衡归并的实现 11.4 转换一选择排序 11.5 最佳归并树 了解:外部排序的基本概念和基本方法 掌握:最佳归并树的建立方法 第十二章 文件(2 学时) 12.1 文件的概念和术语 12.2 顺序文件 12.3 索引文件 12.4 散列文件 掌握:文件的基本概念;顺序文件,索引文件和散列文件的组织方法和操作方法。 机动: 2 学时 四.实验开设内容、要求、时间安排: 一、时间安排 序 号 实验名称 课 时 必(选)做 实验一 线性表及其应用 2 必做 实验二 树及其应用 4 必做 实验三 图及其应用 自定 选做 实验四 查找技术 4 必做 二、实验内容 实验一 线性表及其应用 实验目的:1.深入了解线性表的各种存储结构。 2.熟练掌握在各种存储结构上进行插入、删除等操作的算法。 3.通过线性表结构解决现实中的一些问题。 实验内容:1.线性表的各种存储结构。 2.各种存储结构上进行插入、删除等操作的算法。 3.通过线性表结构解决现实中的一些问题。 实验二 树及其应用 实验目的:1.熟悉树的各种存储结构的特性。 2.应用树的结构解决具体问题。 实验内容:1.树的各种存储结构。 2.应用树的结构解决具体问题。 实验三 图及其应用 实验目的:1.熟悉图的各种存储结构的特性。 2.应用图的结构解决具体问题 实验内容:1.图的各种存储结构。 2.应用图的结构解决具体问题 实验四 查找技术 实验目的:1.熟练掌握常用的一些查找算法。 2.深入理解各种查找算法的结构特点及各算法之间的区别。 3.能通过所学的查找算法解决一些实际问题。 实验内容:1.常用的一些查找算法。 2.各种查找算法的结构特点及各算法之间的区别。 3.能通过所学的查找算法解决一些实际问题。 五.教学参考书目 1.严蔚敏 吴伟民 数据结构 清华大学出版社 1997 年 4 月。 2.严蔚敏、吴伟民编著,数据结构题集,清华大学出版社,1999.2,第一版。 3.张晓莉等编著,数据结构与算法,机械工业出版社,2002.9,第一版。 4.李春葆编著,数据结构(C 语言篇)习题与解析,清华大学出版社,2002.4。, 5.李春葆编著,数据结构考研指导,清华大学出版社,2003.1,第一版。
免责声明:本文系转载自网络,如有侵犯,请联系我们立即删除,另:本文仅代表作者个人观点,与本网站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
|