nbhkdz.com冰点文库

数据结构教学大纲

时间:2015-11-23

数据结构教学大纲
课程编号:090010 课程名称:数据结构 英文名称:Data Structure 学分:5 学时:102,其中讲授 68 学时,实验 34 学时 适用年级专业(学科类) :二年级 数学类、数电类

一、课程概述 (一)课程性质 《数据结构》是计算机及相关专业的一门综合性的专业基础课,是介于数学、计算机硬件和计算机 软件之间的一门计算机科学与技术专业的核心课程,同时数据结构技术也被广泛应用于信息科学、系统 工程、应用数学以及各种工程技术领域。本课程主要介绍如何合理的组织和表示数据、如何有效的存储 和处理数据、如何正确的设计算法以及对算法的优劣作出分析和评价。 (二)教学目标与要求 通过本课程的学习,使学生深透理解各种常用数据结构的逻辑结构、存储结构及相关算法的实现; 全面掌握处理数据的理论和方法,培养学生选用合适的数据结构,编写质量高、风格好的程序及初步评 价算法的能力;使学生系统的科学的受到分析问题和解决问题的训练,提高运用数据结构解决实际问题 的能力,为后续的软件课程奠定良好的基础。 (三)重点和难点 本课程的重点是:从数据结构的逻辑结构、存储结构、数据的运算三个方面去掌握线性表、栈、队 列、串、数组、树、图等常用的数据结构;掌握常用的各种查找方法和排序算法;并培养对算法的时间 空间复杂性的分析能力。 本课程的难点有:逻辑结构与存储结构的关系,顺序表和链表的区别与联系,栈和队列的特点,模 式匹配,矩阵的压缩存储,二叉树的性质,二叉树的各种遍历算法,哈夫曼树,最小生成树,关键路径, 折半查找,二叉排序树,平衡二叉树,B-树,哈希表,各种排序方法及性能分析。 (四)与其他课程的关系 数据结构的先修课程有计算机导论、C 语言程序设计、离散数学;后继课程有操作系统、编译原理、 数据库原理、人工智能等。数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经 验及能力,本课程的算法用 C 语言实现,因此要求学生较熟练地掌握 C 语言。 (五)教材及教学参考书的选用 1、 《数据结构》 ,刘振鹏,中国铁道出版社,2003 年 9 月; 2、 《数据结构与算法》 ,张晓莉,机械工业出版社,2002 年 9 月; 3、 《数据结构(C 语言版) 》 ,严蔚敏,清华大学出版社,1997 年 4 月; 4、 《Data Structures,Algorithms,and Applications in C++》 , (美)Sartaj Sahni,机械工
-1-

业出版社,1999 年。 5、 《数据结构与算法》 ,许卓群,高等教育出版社,2004 年 7 月

二、学时分配

章 1 2 3 4 5 6 7 8 9 10

课程内容 绪论 线型表 栈和队列 串 数组、特殊矩阵和广义表 二叉树 树和森林 图 查找 排序

学时 2 8 4 4 4 10 4 12 10 10

三、课程内容 第一章 绪论 教学目的和要求: 本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义,要求了解本章介绍 的各种基本概念和术语,掌握算法描述和分析的方法。 重点和难点: 1、教学重点:了解数据结构的逻辑结构、存储结构及数据运算等三方面的概念及相互关系,算法 的性能评价。 2、教学难点:抽象数据类型的概念的理解,算法时间复杂度的分析方法。 主要内容: 1、数据结构的概念; 2、抽象数据类型; 3、算法和算法分析。 主要教学环节的组织: 课堂讲授。 思考题: 1、试举一个数据结构的例子,叙述其逻辑结构、存储结构、运算这三方面的内容。 2、比较逻辑结构和存储结构的关系。 3、比较数据结构的概念与程序设计语言中数据类型的概念的区别与联系。

-2-

第二章 线性表 教学目的和要求: 本章目的是介绍线性表的逻辑结构和各种存储表示方法,以及定义在逻辑结构上的各种基本运算在 相应的存储结构上的实现。要求在熟悉这些内容的基础上,能够针对具体的应用问题的要求和性质,选 择合适的存储结构设计出相应的有效算法,解决与线性表相关的实际问题。 重点和难点: 1、教学重点:顺序表和单链表上实现的各种基本算法及相关的时间性能分析。 2、教学难点:用本章所学到的基本知识设计算法解决与线性表相关的实际应用问题。 主要内容: 1、线性表的逻辑结构; 2、线性表的顺序存储及运算实现; 3、线性表的链式存储及运算实现; 4、顺序表和链表的比较。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、请比较顺序表与链表的优缺点。 2、单链表具有随机存取的性质吗?顺序表呢?为什么?

第三章 栈和队列 教学目的和要求: 本章的目的是介绍栈和队列的逻辑结构定义及其在两种存储结构上如何实现栈和队列的基本运算。 要求在掌握栈和队列的特点的基础上,懂得在什么样的情况下使用栈或队列,掌握在不同的存储结构上 实现栈和队列的方法。 重点和难点: 1、教学重点:栈和队列在两种存储结构上基本操作的实现。 2、教学难点:循环队列中对边界条件的处理及栈和队列的应用。 主要内容: 1、栈及其性质; 2、栈的应用举例; 3、队列及其性质; 4、队列的应用举例。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、栈和队列各有什么特点,什么情况下用到栈,什么情况下用到队列?
-3-

2、循环队列是如何实现“循环”的?

第四章 串 教学目的和要求: 本章目的是介绍串的逻辑结构、存储结构及其字符串上的基本运算,要求掌握串的各种存储结构、 串的常用运算及模式匹配算法。 重点和难点: 1、教学重点:串的存储结构及基本运算。 2、教学难点:模式匹配。 主要内容: 1、串及其基本运算; 2、串的定长顺序存储及基本运算; 3、串的堆存储结构。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、KMP 算法与朴素的模式匹配算法相比有何优越性? 2、求模式串的 next 函数值有什么意义?

第五章 数组、特殊矩阵和广义表 教学目的和要求: 本章的目的是介绍多维数组的逻辑结构特征及存储方式,特殊矩阵和稀疏矩阵的压缩存储方法及广 义表的概念及存储实现方法。 重点和难点: 1、教学重点:多维数组的存储方式、矩阵的压缩存储方法、广义表的定义及基本运算。 2、教学难点:特殊矩阵的压缩方法,稀疏矩阵的压缩存储及其运算的实现。 主要内容: 1、多维数组; 2、特殊矩阵的压缩存储; 3、稀疏矩阵; 4、广义表。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、如何用一维的空间表示多维的数组? 2、为什么要对矩阵进行压缩存储?
-4-

3、广义表和一般的线性表有和异同?

第六章 二叉树 教学目的和要求: 本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化及二叉树的应用等内容,要求掌握 二叉树的性质、存储结构,掌握二叉树的各种遍历算法及其应用,哈夫曼树等。 重点和难点: 1、教学重点:二叉树的性质,二叉树的遍历算法及其应用,哈夫曼树。 2、教学难点:二叉树性质的证明,基于二叉树遍历解决实际问题,哈夫曼编码。 主要内容: 1、二叉树的定义与性质; 2、二叉树的存储实现基本操作的实现; 3、二叉树的遍历; 4、线索二叉树; 5、二叉树的应用。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、一棵度为 2 的树与一棵二叉树有何区别?树与二叉树之间有何区别? 2、在结点数多于 1 的哈夫曼树中存在度为 1 的结点吗? 3、遍历二叉树的方法有哪些?遍历二叉树的实质是什么?

第七章 树和森林 教学目的和要求: 本章介绍树和森林的定义、存储结构、和二叉树之间的转换、遍历及树的应用等内容,要求掌握树 与二叉树之间的转换及其树的应用等。 重点和难点: 1、教学重点:树和森林的存储结构、遍历,树、森林和二叉树之间的转换。 2、教学难点:树和森林的遍历及由遍历序列恢复树或森林,用相关知识解决与树的实际应用问题。 主要内容: 1、树的概念与表示; 2、树的基本操作与存储; 3、树、森林与二叉树的转换; 4、树或森林的遍历; 5、树的应用。 主要教学环节的组织:
-5-

课堂教学与实践。 思考题: 1、树、森林和二叉树之间有什么关系? 2、已知一棵度为 m 的树中有 n1 个度为 1 的结点,n2 个度为 2 的结点,??,nm 个度为 m 的结点, 问该树中共有多少个叶子结点?有多少个非终端结点?

第八章 教学目的和要求: 教学目的和要求:本章的目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的 应用算法,在熟悉这些内容的基础上, 重点和难点: 1、教学重点:图的存储结构,图的遍历算法,图的几种应用算法。 2、教学难点:最小生成树,最短路径,拓扑排序,关键路径。 主要内容: 1、图的基本概念 ; 2、图的存储表示; 3、图的遍历; 4、生成树与最小生成树; 5、最短路径; 6、有向无环图及其应用。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、比较 Prim 算法和 Kruskal 算法,当边数较少时用哪一个方法较好? 2、用哪些方法可以判断有向图中有环路存在? 3、加快一个关键活动,一定能缩短工期吗?

第九章 查找 教学目的和要求: 本章目的是介绍各种存储方式下的查找表的查找方法,以及各种查找方法的时间性能分析, 重点和难点: 1、教学重点:顺序查找、二分查找、二叉树排序树、平衡二叉树,B-树以及哈希表上的查找思想、 算法实现及查找性能的分析。 2、教学难点:二叉排序树的删除,平衡二叉树的调整,B-树的插入和删除,哈希表中处理冲突的 方法。 主要内容:
-6-

1、基本概念; 2、静态查找表; 3、动态查找表; 4、哈希表查找(杂凑法) 。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、试推导含有 12 个结点的平衡二叉树的最大深度,并画出一棵这样的树。 2、含有 9 个叶子结点的 3 阶 B–树中至少有多少个非叶子结点?含有 10 个叶子结点的 3 阶 B–树 中至少有多少个非叶子结点? 3、比较哈希查找方法与其他查找方法的区别。

第十章 排序 教学目的和要求: 本章目的介绍 5 类内部排序方法的基本思想、排序过程、算法事现、时间和空间性能的分析以及各 种排序方法的比较和选择。 重点和难点: 1、教学重点:各种排序的思想、算法实现、稳定性、适用情况、时间空间复杂度分析。 2、教学难点:希尔排序,快速排序,堆排序。 主要内容: 1、基本概念; 2、插入排序; 3、交换排序; 4、选择排序; 5、二路归并排序; 6、基数排序; 7、外排序。 主要教学环节的组织: 课堂教学与实践。 思考题: 1、如果只想得到一个序列中第 k 小元素前的部分排序序列,最好采用什么排序方法?为什么? 2、有 n 个不同的英文单词,它们的长度相等,均为 m,若 n>>50,m<5,试问采用什么排序方法时间 复杂度最佳?为什么?

四、教学方式 课堂讲授、课堂讨论、上机实验等。
-7-

五、课程考核 考核类型:考试 计分办法:平时成绩占 30-40%,考试成绩占 60-70%。

-8-


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

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

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

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

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

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

数据结构教学大纲.doc

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

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

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

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

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

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

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

数据结构A教学大纲.doc

数据结构A教学大纲 - 数据结构 A 教学大纲 (Data Structures

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

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

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

数据结构教学大纲 - 课程名称 英文名称 课程编号 预修课程 大纲撰写人 不填

数据结构-教学大纲.doc

数据结构-教学大纲 - 江苏大学 数据结构A 教学大纲... 江苏大学教学大纲数据结构 A (Data Structures A) 课程编号: 06311360 学学分: 5.0 时: 75 (其中:讲课学...

数据结构教学大纲.doc

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

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

数据结构与算法》课程教学大纲 - 《数据结构与算法》课程教学大纲 课程代码:1

数据结构教学大纲48学时.pdf

数据结构教学大纲48学时 - 西南交通大学希望学院 课程教学大纲 课程编号: 课

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

新版《数据结构教学大纲 - 专业资料整理分享 新版《数据结构课程 教学大纲 完美 WORD 格式编辑 专业资料整理分享 一、课程名称 《数据结构》 二、教学目的 ...

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

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

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

数据结构课程设计教学大纲 - 《数据库原理及应用》课程设计教学大纲 课程名称:数

数据结构教学大纲.doc

数据结构教学大纲 - 《数据结构》教学大纲 一. 教学目的和要求 数据结构是介于

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

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

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

数据结构课程教学大纲 - 《综合化学实验(一)》实验课程教学大纲 一、课程基本信