加入收藏  || English Version 
 
《数据结构与算法》教学大纲

  发布日期:2015-03-11  浏览量:507


《数据结构与算法》课程是计算机相关专业高等教育的专业基础课程。是计算机程序设计的重要理论技术基础,它对理论和实践的要求都相当高,且内容较多。作为数学与计算科学学院信息与计算专业的必修课,基本内容以计算机系的专业技术基础课--《数据结构》的内容为主,根据信息专业的特点,在内容和难度上有所取舍。学习本课程所讨论的常识内容和提倡的技术方法和思路,无论对进一步学习计算机领域的其他课程,还是对从事App工程的开发,都有着不可替代的作用。 

 

本课程设置的目的是:要培养学生的数据抽象能力,学会分析研究计算机加工的数据结构的特性,以便为信息的加工和处理选择适当的逻辑结构、存储结构及实现应用的适当算法,并掌握分析算法的时间和空间复杂度的技术。

 

学习本课程的要求是:通过本课程的学习,要求学生了解数据结构及其分类、数据结构与算法的密切关系;熟悉各种基本数据结构及其操作,学会根据实际问题要求来选择数据结构;掌握设计算法的基本步骤和算法分析方法;掌握数据结构在排序和查找等常用算法中的应用。

先修课程要求:计算机基础、C语言、离散数学

 

本课程计划总学时90学时,4学分,其中理论54学时,实验课36学时。

 

选用教材:

[1] 严蔚敏、吴伟民编著,数据结构(C语言版),清华大学出版社,1999

[2] 严蔚敏、吴伟民编著,数据结构题集,清华大学出版社

教学手段:多媒体教学

考核方法:考试

 

 

教学进程安排表

 

周次

周学时

教学主要内容

教学

环节

备注

1

3

第一章绪论

2.1 线性表的类型定义

讲课

 

 

2

3

2.2线性表的顺序存储结构

讲课

 

3

3

2.3线性表的链式表示和实现

讲课

 

4

3

3.1

3.2栈的应用举例

讲课

 

 

5

3

3.4队列

习题

讲课

习题课

 

6

3

第四章

5.1 数组的定义
5.2
数组的顺序表示和实现

讲课

 

 

7

3

5.3 矩阵的压缩存储

5.4广义表的定义

6.1 树的定义和基本术语

6.2二叉树

讲课

 

 

8

3

6.3遍历二叉树和线索二叉树

讲课

 

9

3

6.4树和森林

6.6哈夫曼树及其应用

讲课

 

 

10

3

7.1图的定义和术语

7.2图的存储结构

讲课

 

 

11

3

7.3图的遍历

7.4图的连通性问题

讲课

 

 

12

3

7.5有向图五环图及其应用

习题

讲课

习题课

 

13

3

9.1静态查找表

9.2动态查找表

讲课

 

 

14

3

9.3哈希表

讲课

 

15

3

10.1概述

10.2插入排序

10.3快速排序

讲课

 

 

16

3

10.4选择排序

10.5归并排序
10.7
各种排序方法综合比较

讲课

 

 

17

3

习题

习题课

 

18

3

复习

讨论

 

 


第一章  绪论

 

一、学习目的

 

本章主要先容了数据结构的一些基本概念和算法分析的一般方法。具体包括数据、数据元素、数据的逻辑结构、物理结构、算法等和类C语言的书写规范。

通过本章的学习,使学生领会数据、数据元素和数据的概念及气相互关系,掌握数据结构的逻辑结构、存储结构的联系与区别,了解算法时间复杂度和空间复杂度的分析。掌握类C语言的书写要求。

本章计划理论2学时。

 

二、课程内容

 

1.1-1.2 数据结构的基本概念和术语

数据、数据结构、数据的物理结构、数据的逻辑结构、数据类型、抽象数据类型
1.3
抽象数据类型的表示与实现

C语言的书写规范与应用
1.4
算法描述和算法分析

算法

算法设计的要求

算法效率的度量

时间复杂度分析、语句频度

算法的存储空间的要求

 

三、重点、难点提示和教学手段

 

重点难点:数据结构相关的基本概念尤其是数据的逻辑结构、存储结构和算法之间的关系;抽象数据类型的定义、表示和实现;计算语句频度和估算算法时间复杂度。教学手段讲授

 

四、思考与练习

 

习题集1.11.21.3 1.81.91.10

 

 

 

第二章 线性表

 

一、学习目的

 

通过本章的学习,要求学生掌握线性表的逻辑结构特性及这种关系在计算机中的不同表示形式。熟练掌握顺序存储的线性表和单链表的算法设计及其程序实现结构上实现的基本操作,熟练掌握线性表在链式存储结构上基本操作的实现。掌握循环链表和双向循环链表的基本操作。能够从时间和空间的角度结合比较线性表两种存储结构的不同特点及在不同的应用中选择合适存储形式。计划理论7学时。

 

二、课程内容

 

2.1 线性表的类型定义
2.2
线性表的顺序存储结构

顺序表

顺序表上的基本运算

2.3线性表的链式表示和实现

线性链表

循环链表

双向链表

 

三、重点、难点提示和教学手段

 

重点难点提示:线性表这种抽象数据结构的定义及其逻辑上的特点;顺序表上插入、删除和定位运算的实现;单链表的结构特点及其类型说明;头指针和头结点的作用;定位、删除、插入运算在单链表上的实现;循环链表和双链表的结构特点,尤其是链表定义及其操作。顺序表和链表的比较和在不同应用环境下的选择是教学难点。讲课辅以算法演示,另加实验。

 

四、思考与练习

 

2.22.32.42.52.62.72.82.92.102.132.132.172.192.202.212.242.252.262.31

 

 

第三章 栈和队列

 

一、    学习目的

本章主要先容了两种常用的操作受限的线性表,内容包括这两种线性表的定义和在两种存储结构上操作的实现。通过本章学习要求理解栈和队列的定义,掌握栈和队列在两种存储结构中的基本操作的实现。能够在简单的应用中,为数据选择合适的逻辑结构和存储结构,并实现要求的操作。计划理论6学时。

 

二、课程内容

 

3.1

抽象数据类型栈的定义和基本操作

栈的顺序存储结构

栈的链式存储结构

3.2栈的应用举例

数制转换

括号匹配

迷宫求解

表达式求值

3.3 栈与递归(选讲)

3.4队列

抽象数据类型队列的定义

链队列——队列的链式表示和实现

循环队列——队列的顺序表示和实现

 

三、重点、难点提示和教学手段

重点难点:栈上的基本运算;栈的顺序存储结构及运算实现;栈的链式存储结构;入栈、出栈等运算在链栈上的实现;队列上的基本运算;队列的顺序存储结构及其上的运算实现;队列的链式存储结构;入队、出队等运算在链式队列上的实现是本章教学的重点。顺序栈的溢出判断条件,循环队列的队空、队满判断条件;循环队列上的插入和删除操作,为实际的应用选择合适的数据结构是本章的难点。讲课加实验。

 

四、思考与练习

 

题集3.13.33.43.73.193.283.29

 

第四章 串

 

一、学习目的

 

通过本章学习,要求学生掌握串类型的抽象数据类型定义和有关基本概念,理解串的模式匹配思想,了解串的表示和实现和串的模式匹配算法。计划理论2学时。

 

二、课程内容

 

4.1串的定义
4.2
串的表示和实现

定长顺序存储

堆分配存储表示

串的块链存储表示

4.4串的应用举例

 

三、重点、难点提示和教学手段

 

重点和难点:串的表示和实现,熟练掌握串的定长顺序表示和实现串的基本操作。串的堆存储是本章的难点。讲授。

 

四、思考与练习

 

题集4.34.44.9

 

第五章 数组和广义表

 

一、    学习目的

 

通过本章学习了解数组的定义和表示方式,掌握特殊矩阵和压缩矩阵的压缩存储方法;理解广义表的逻辑结构。本章计划2学时

 

二、课程内容

 

5.1 数组的定义
5.2
数组的顺序表示和实现

5.3 矩阵的压缩存储

5.3.1特殊矩阵

5.3.2稀疏矩阵

5.4广义表的定义

三、重点、难点提示和教学手段

 

重点和难点:数组在以行为主的存储结构中的地址计算方法,广义表的逻辑结构。特殊矩阵的压缩存储时的下标变换公式是其难点。讲课辅以算法演示。

 

四、思考与练习

 

题集5.15.65.75.85.105.135.21

 

第六章 树和二叉树

 

一、    学习目的

 

通过本章的学习要求,要求学生掌握以下内容:树的定义、性质、存储结构;熟练掌握二叉树的遍历,哈夫曼树的构造和编码方法;了解二叉树的线索化,树与森林的转化和树的应用。能够运用二叉树的遍历解决相关的应用问题。计划理论学时8学时。

二、课程内容

 

6.1 树的定义和基本术语

树的定义

基本操作

6.2二叉树

二叉树的定义和基本操作

二叉树的性质

普通二叉树、完全二叉树、满二叉树

二叉树的存储结构

6.3遍历二叉树和线索二叉树

遍历二叉树

先序遍历二叉树、中序遍历二叉树、后序遍历二叉树

线索二叉树

中序线索化二叉树

6.4树和森林

树的存储结构

森林与二叉树的转换

树和森林的遍历

6.6哈夫曼树及其应用

最优二叉树的定义

哈夫曼树的构造和哈夫曼编码

 

二、    重点、难点提示和教学手段

 

重点和难点:本章是本课程的教学重点。其中二叉树的定义、逻辑特点及其五种基本形态;二叉树的五个性质;二叉树上的基本运算;二叉树的链式存储结构及其类型说明;二叉树的顺序存储结构及其类型说明;二叉树的三种遍历方法及在此基础上的应用;哈夫曼树和哈夫曼编码是本章的教学重点。二叉树的递归定义;二叉树链式存储结构和组织形式;三种遍历的主要区别是教学难点。讲课辅以算法演示,另加实验。

 

四、思考与练习

 

6.16.46.146.196.216.226.236.266.276.336.436.63

 

 

第七章 图

 

一、    学习目的

 

通过学习本章要求学生掌握以下内容:理解图的基本概念和术语;掌握图的两种存储结构方法;掌握图的两种遍历的算法思想、步骤,并能列出在两种存储结构上按上述两种遍历算法得到的序列;理解最小生成树的概念,能够运用普里姆或库鲁索方法生成图的最小生成树;领会拓扑排序、最短路径的思想,能够列出一个图的拓扑排序序列。本章是本课程的又一个教学的重点和难点章节。计划理论学时9学时。

 

 

二、课程内容

 

7.1图的定义和术语

7.2图的存储结构

数组表示

邻接表

7.3图的遍历

深度优先遍历

广度优先遍历

7.4图的连通性问题

无向图的连通分量和生成树

最小生成树

7.5有向图五环图及其应用

拓扑排序

最短路径

 

三、重点、难点提示和教学手段

 

重点和难点:理解图的定义、术语与含义;掌握各种图的邻接矩阵表示法及其类型说明;理解并掌握图的两种遍历方法;领会生成树和最小生成树的概念,并能够选用一种方法得到图的最小生成树;强化拓扑有序的概念,可以根据相应的算法和步骤得到图的拓扑排序序列;了解关键路径的思想和最短路径的思想。图的术语的理解和区分;图的两种存储结构的不同点及其应用场合是教学的难点。讲课辅以算法演示,另加实验。

 

三、    思考与练习

习题集:7.17.77.67.11

 

第九章 查 找

 

一、    学习目的

 

通过本章的学习,要求掌握静态查找表的查找算法和实现,掌握二叉排序树的查找、插入算法及其实现;掌握哈希表的构造方法;深刻理解哈希表与其他结构表的实质性的差别。了解三类函数和处理冲突的方法,能够对各种查找方法,根据定义在等概率下的平均查找长度。本章是本课程的重点。计划理论8学时.

 

二、课程内容

 

9.1静态查找表

顺序表查找

有序表的查找

静态树表的查找

索引顺序表的查找

9.2动态查找表

二叉排序树的查找、插入、删除

平衡二叉树、B-树、B+树的思想

9.3哈希表

哈希表的概念

哈希表的构造方法

处理冲突的方法

哈希表的查找及其分析

 

三、重点、难点提示和教学手段

 

重点和难点:查找表的基本概念及查找原理,查找运算在静态表有序表上的实现,动态查找表的概念,二叉排序树的定义和二叉排序树的查找算法和基本思想;哈希表的概念和散列的思想;简单的构造哈希表的方法和解决冲突的方式;平均查找长度的概念和计算是本章的教学重点。二叉排序树上的插入和删除;构造散列表中的冲突的处理方式是本章的教学难点。讲课辅以算法演示,另加实验。

 

四、思考与练习

 

题集:9.99.199.219.259.269.31

 

第十章 内部排序

 

一、    学习目的

 

本章主要是先容常用的内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。通过本章的学习要求理解各种内部排序方法,插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。在每种排序方法中,重点掌握先进的高效方法。本章是本课程的重点和难点章节。计划理论8学时。

 

二、课程内容

 

10.1概述

10.2插入排序

直接插入排序

希尔排序

10.3快速排序

10.4选择排序

简单选择排序

树刑选择排序

堆排序

10.5归并排序
10.7
各种排序方法综合比较

三、重点、难点提示和教学手段

 

重点和难点:排序基本概念及稳定排序和非稳定排序的区别;各种排序方法的基本思想和步骤和时间复杂度的分析是教学的重点。希尔排序、快速将排序、堆排序和归并排序方法等高效方法是本章的学习重点和难点。讲课辅以算法演示,另加实验。

 

四、思考与练习

 

10.110.710.1210.2510.2610.2710.33

 

阅读书目(或参考文献)

 

[1] 周岳山,《数据结构》,华中科技大学出版社, 2003

[2] 刘遵仁。《数据结构》,人民邮电出版社,  2000

[3] 朱战立,《数据结构》,西安交通大学出版社, 20041

[4] Mark Allen Weiss(美)著, 陈越译,《数据结构与算法分析》,人民邮电出版社,2005

打印此页】【顶部】【关闭
   
版权所有 2019 澳门赌搏网站大全 All rights reserved 皖ICP备05018241号
地址:安徽省合肥市九龙路111号澳门新莆京娱乐网站磬苑校区理工楼H楼 邮编:230601 E-mail:math@ahu.edu.cn
访问统计:自2013年9月1日以来总访问:1000  后台管理


XML 地图 | Sitemap 地图