nbhkdz.com冰点文库

数据结构教学大纲

时间:2018-08-08

《数据结构与算法》教学大纲 课程编号:030816 适用专业:教育技术学 总学时数:64 学 分:4 编制单位:茂名学院理学院教育与信息技术系 编制时间:2008 年 6 月 20 日

一、课程地位、性质和任务 《数据结构与算法》课程是计算机相关学科专业的基础课程中的一门重要的核心课
程。通过本课程的教学,使学生知道求解非数值类问题的基本模型(表、树、图) ,模型的 特点和适用场合,能够根据问题设计和选择好的算法,为学习后续的操作系统、编译原理和 软件工程等专业课程,设计应用程序打下基础。 本课程以提高学生的计算机应用能力和综合素质为目标, 通过课程教学, 为学生构建数据结 构与算法方面的知识体系, 使学生一方面能够根据问题选择合适的数据结构, 设计高效的算 法,提高程序设计能力,另一方面,在工程应用中,具有甄别好算法的能力,也就是要从建 模、解模和综合等三个方面,提高学生的程序设计能力。

二、与其他课程的关系 先修课:程序设计基础、离散数学、计算机组成原理、计算机文化基础 三、教学内容、课时安排和基本要求 (一)教学部分 第1章 绪论(2 学时) 1.1 什么是数据结构 1.2 1.3 1.4 基本概念和术语 抽象数据类型的表示与实现 算法和算法分析(算法及其设计的要求, 算法效率的度量,算法的存

储空间需求) 1.5 问题求解 基本要求: 了解:抽象数据类型,算法设计方法与算法分析。 掌握:数据与数据结构、算法的基本概念;问题求解的方法与步骤 重点:数据结构和算法的概念,算法的描述形式和评价方法,问题求解的一般步骤
1

难点:评价算法的标准和评价方法,最坏情况和平均情况的区分。 第2章 线性表(8 学时) 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现(线性链表,循环链表,双向链表) 2.4 一元多项式的表示及相加 基本要求: 了解:两种存储结构(顺序存储结构和链式存储结构)及一元多项式的表示 及相加。 掌握:要求熟练掌握处理线性表的各种算法。为后继章节的学习打基础。 重点:各种算法。 难点:链表的理解。 第3章 栈与队列(4 学时) 3.1 栈(定义,栈的表示和实现) 3.2 栈的应用举例(数制转换,括号匹配的检验,行编辑程序,迷宫求解,表 达式求值) 3.3 栈与递归的实现 3.4 队列及其实现(定义,链队列,循环队列) 3.5 *离散事件模拟 教学要求: 熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。栈和 队列是表最基本和重要的数据结构,是数据结构课程的基础。 基本要求: 了解: 栈和队列的定义及其实现。 掌握: 熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。 重点: 栈和队列的算法实现。 难点: 栈和队列的算法实现。 第4章 串(2 学时) 4.1 串类型的定义 4.2 串的表示和实现(定长顺序存储,堆分配存储,串的块链存储) 4.3 串的模式匹配算法(求子串位置的定位函数,模式匹配的一种改进算法) 4.4 串操作应用举例(文本编辑,建立词索引表)

2

基本要求: 了解:串的基本概念及主要操作和运算。 掌握:掌握串的基本概念和运算。 重点:主要操作和运算。 难点:模式匹配及串的应用。 第5章 数组(2 学时) 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储(特殊矩阵,稀疏矩阵) 5.4 广义表的定义 5.5 广义表的存储结构 5.6 m 元多项式的表示 5.7 广义表的递归算法(求广义表的深度,复制广义表,建立广义表的存储结 构) 基本要求: 了解:了解作为抽象数据类型的数组和 C 语言的数组。认识到数组可以作为 顺序存储结构用于顺序表、字符串和稀疏矩阵的实现。也可以采用链 式存储结构。 掌握:掌握基本概念和算法。 重点:算法。 难点:广义表的递归算法。

第6章 树与二叉树(15 学时) 6.1 树的定义和基本术语 6.2 二叉树(二叉树的定义,二叉树的性质,二叉树的存储结构) 6.3 遍历二叉树和线索二叉树(遍历二叉树,线索二叉树) 6.4 树和森林(树的存储结构,森林与二叉树的转换,树和森林的遍历) 6.5 树与等价问题 6.6 赫夫曼树及其应用(最优二叉树(赫夫曼树),赫夫曼编码) 6.7 回溯法与树的遍历 6.8 树的计数 基本要求:

3

了解:理解树与森林的定义与术语。 掌握:熟练掌握二叉树性质和遍历算法,掌握树与森林的孩子兄弟存储表示 和遍历。掌握哈夫曼树构造的方法和算法。 重点: 树的存储结构和遍历算法。 难点:哈夫曼树构造的方法和算法 第7章 图(11 学时) 7.1 图的定义和术语 7.2 图的存储结构(数组表示法,邻接表,十字链表,邻接多重表) 7.3 图的遍历(深度优先搜索,广度优先搜索) 7.4 图的连通性问题(无向图的连通分量和生成树,有向图的强连通分量,最 小生成树,关节点和重连通分量) 7.5 有向无环图及其应用(拓扑排序,关键路径) 7.6 最短路径 (从某个源点到其余各项点的最短路径,每一对顶点之间的最短 路径) 基本要求: 了解:图的基本概念和相关术语。 掌握:图的两种主要存储结构及遍历算法。掌握最小生成树、最短路径和活 动网算法的思想。 重点:图的两种主要存储结构及遍历算法。 难点:图的遍历算法,最短路径算法。

第8章 查找(8 学时) 9.1 静态查找表(顺序表,有序表,静态树表,索引顺序表) 9.2 动态查找表(二叉排序树和平衡二叉树,B_树和 B+树,键树) 9.3 哈希表(定义,构造方法,处理冲突的方法,查找及其分析) 基本要求: 了解: 各种查找法的基本概念及实现的基本思想。 掌握:熟练掌握搜索结构的折半查找、二叉搜索树、平衡二叉树主要搜索算 法。掌握哈希表查找算法。 重点:各种算法的基本思想及实现。 难点:哈希表查找算法。

4

第9章

内部排序(8 学时)

10.1 概述 10.2 插入排序(直接插入,其他插入,希尔) 10.3 交换排序(冒泡排序、快速排序) 10.4 选择排序(简单,树形,堆) 10.5 归并排序 10.6 基数排序(多关键字,链式) 10.7 排序算法分析 基本要求: 了解:基数排序,排序算法分析方法 掌握:排序的基本概念,插入排序,交换排序,选择排序,归并排序 重点:内部排序算法 难点:基数排序(多关键字,链式) 第10章 *外部排序(2 学时)

11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树 基本要求: 了解:外部排序的基本概念和相关术语。 掌握:基本掌握外排算法的基本思想,不同排序方法的比较。 重点:外部排序算法 难点:多路平衡归并的实现 第 11 章 算法设计的一般方法(2 学时)
1.重点 (1)有效算法的概念,问题固有难度的概念; (2)递归法;分治法;平衡原则;贪心法;动态规划的基本原理; (3)搜索-回溯法的基本原理和本质. 2.难点 (1)问题固有难度的概念; (2)递归分治法的效率分析(写出时间耗费的递推式,并求解) ; (3)动态规划法中的状态转移方程的确定。

5

(二)实验、实习部分 课程安排五个类别的实验,实验时数为 12 课时,其中: 实验一、线性链表及运算 2 课时 实验二、栈和队列 2 课时 实验三、树和二叉树 4 课时 实验四、图及其应用 2 课时 实验五、查找与排序 2 课时 四、课程考核方式 闭卷考试 70%、平时作业与实验 30%

五、建议教材和教学参考书 参考教材: 1、 《数据结构》 (C 语言描述)高等教育出版社 耿国华主编 2、 《数据结构》 (C 语言版) 清华大学出版社 严蔚敏,吴伟民编者 高一 3、 《数据结构题集》 (C 语言版)清华大学出版社 严蔚敏,吴伟民编者 4、 《数据结构》算法实现及解析(第二版) 西安电子科技大学出版社 凡 六、说明 1、因课时安排少,教学内容多。建议采用多媒体教学。 2、由于本课程内容较多,在实际教学中可根据大纲内容,进行适当调整。

6


《数据结构》课程教学大纲.doc

数据结构课程教学大纲 - 数据结构课程是计算机相关专业的专业基础课、必修课程

数据结构课程教学大纲.doc

数据结构课程教学大纲一、课程基本概况 课程名称:数据结构 课程名称(英文) :D

数据结构教学大纲.doc

数据结构教学大纲 - XX 师范学院大学本科专业教学大纲 中文课程名称:数据结构

《数据结构》课程教学大纲(三套).doc

数据结构课程教学大纲(三套) - 数据结构是计算机及应用专业中一门重要的专业基础课程,在计算机软件的各个领域中均会使用到数据结构的有关知识。当用计算机来...

数据结构课程教学大纲_图文.doc

数据结构课程教学大纲 - 湖南涉外经济学院数据结构课程教学大纲... 《数据结构教学大纲课程性质 课程名称 适用专业 总学时 64 专业必修课 数据结构 计算机科学与技术...

新版《数据结构》教学大纲.doc

新版《数据结构教学大纲 - 新版《数据结构课程 教学大纲 一、课程名称 《数据结构》 二、教学目的 数据结构是高等教育计算机信息管理专业中的一门专业基础课, ...

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

数据结构教学大纲 - 《数据结构教学大纲 Data Structure 课

数据结构与算法教学大纲.doc

数据结构与算法教学大纲 - 《数据结构教学大纲 一、课程基本信息 课程名称:数据结构 总学时:64(理论课内学时48,上机课内学时16) 课程设计:24 课程类型:必修...

数据结构课程教学大纲..doc

数据结构课程教学大纲. - 数据结构课程教学大纲 【课程编码】 【课 【学时】

数据结构教学大纲 - 百度文库.doc

数据结构教学大纲 - 数据结构 学时数: 64 学分数: 4.0 编写日期:20

数据结构教学大纲.doc

数据结构教学大纲 - 《数据结构与算法》教学大纲 课程编号:030816 适用专

数据结构教学大纲.doc

数据结构教学大纲 - 数据结构教学大纲 课程编号:090010 课程名称:数据结

《数据结构与算法》教学大纲.doc

数据结构与算法》教学大纲 - 《数据结构与算法》教学大纲,数据结构c语言版知识点,数据结构c语言版严蔚敏,数据结构严蔚敏pdf下载,大数据查找算法,数据结构c语言版 ...

《数据结构》课程教学大纲.doc

数据结构课程教学大纲 - 《数据结构》课程简介 课程名称 英译名称 课程代码

数据结构教学大纲.doc

数据结构教学大纲 - 数据结构教学大纲 (56学时) 一、课程性质、适用专业及层

数据结构及算法教学大纲.pdf

数据结构及算法教学大纲 - 中山大学信息科学与技术学院计算机科学系 《数据结构与算法》 数据结构与算法》课程教学大纲 课程名称: 数据结构 授课对象: 本科生 类别:...

《数据结构》课程教学大纲.doc

数据结构课程教学大纲 - 课程教学大纲 课程代号: 07021021 学时数

数据结构教学大纲.doc

数据结构教学大纲 - 《数据结构》教学大纲 执笔人:张力 课程名称:数据结构 专

《数据结构课程设计》教学大纲2016.doc

数据结构课程设计》教学大纲2016 - 《数据结构课程设计》 任务书 专业:

数据结构课程教学大纲.doc

数据结构课程教学大纲 - 本文档为书记结构课程基本情况... 数据结构课程教学大纲_理学_高等教育_教育专区。本文档为书记结构课程基本情况 《数据结构课程教学大纲 一...