算法与数据结构教学大纲.docx
- 文档编号:10302571
- 上传时间:2023-05-24
- 格式:DOCX
- 页数:17
- 大小:21.45KB
算法与数据结构教学大纲.docx
《算法与数据结构教学大纲.docx》由会员分享,可在线阅读,更多相关《算法与数据结构教学大纲.docx(17页珍藏版)》请在冰点文库上搜索。
算法与数据结构教学大纲
数据结构与算法B教学大纲
课程编号:
CST-0-502
课程名称:
数据结构与算法B
课程性质:
理科本科生必修课
学时:
4(课堂教学)+2(教学实验)/周
学分:
3
先修课程:
计算引论(通过学习计算引论,学生要有一定的程序设计能力,能熟
练掌握运用C的控制结构,函数定义与调用,数组,结构,指针。
)
基本要求:
1.从每个数据结构的逻辑结构、相应的一组基本运算和实现三个方面去掌握线性表、栈、队列、串*、数组*、树、图、字典和文件*等常用的数据结构。
2.掌握在顺序存储结构上实现的重要的排序算法。
3.对算法的时间和空间复杂性有一定的分析能力。
4.针对简单的应用问题,应能选择合适的数据结构及设计有效的算法解决之。
课程内容与考核目标:
第1章概论
(一)课程内容
1.1基本概念和术语
1.2学习数据结构的意义
1.3算法的描述和分析
(二)学习目的与要求
本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义,要求了解本章介绍的各种基本概念和术语,掌握算法描述和分析的方法。
本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系,难点是算法复杂度的分析方法。
(三)考核知识点与考核要求
1.数据结构的基本概念和术语,要求达到“识记”层次。
1.1数据、数据元素、数据项、数据结构等基本概念。
1.2数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。
1.3逻辑结构:
线性、树、图和集合。
1.4存储结构:
顺序、链接、索引和散列。
。
2.数据结构在程序设计中的作用,要求达到“领会”层次。
2.1数据结构在程序设计中所起的作用。
2.2选择合适的数据结构是解决应用问题的关键步骤。
3.算法的描述和分析,要求达到“领会”层次。
3.1算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。
大欧表示法。
3.2算法描述和算法分析的方法,对于一般算法能分析出时间复杂度。
第2章线性表
(一)课程内容
2.1线性表的逻辑结构
2.2线性表的顺序存储结构
2.3线性表的链式存储结构
2.4顺序表和链表的比较
2.5*串
2.6*数组
(二)学习目的与要求
本章目的是介绍线性表的逻辑结构和各种存储表示方法,以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。
要求在熟悉这些内容的基础上,能够针对具体应用问题的要求和性质,选择合适的存储结构设计出相应的有效算法,解决与线性表有关的实际问题。
本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析,难点是能够使用本章所学到的基本知识设计有效算法解决与线性表有关的应用问题。
本章还包含串和数组的逻辑结构及存储的实现。
(三)考核知识与考核要求
1.线性表的逻辑结构,要求达到“领会”层次。
1.1线性表的逻辑结构特征。
1.2线性表上定义的基本运算,并能利用基本运算构造出较复杂的运算。
2.线性表的顺序存储结构,要求达到“综合应用”层次。
2.1顺序表的含义及特点,即顺序表如何反映线性表中元素之间的逻辑关系。
2.2顺序表上的插入、删除操作及其平均时间性能分析。
2.3利用顺序表设计算法解决简单的应用问题。
3.线性表的链式存储结构的单链表,要求达到“综合应用”层次。
3.1单链表如何表示线性表中元素之间的逻辑关系。
3.2单链表中头指针和头结点的使用。
3.3单链表上实现的建表、查找、插入和删除等基本算法,并分析其时间复杂度。
3.4利用单链表设计算法解决简单的应用问题。
4.线性表的链式存储结构的循环链表和双链表,要求达到“简单应用”层次。
4.1循环链表上尾指针取代头指针的作用,以及单循环链表上的算法与单链表上相应算法的异同点。
4.2双链表的定义及其相关的算法。
4.3单链表、双链表、循环链表链接方式上的区别。
5.顺序表和链表的比较,要求达到“领会”层次。
5.1顺序表和链表的主要优缺点。
5.2针对线性表上所需要执行的主要操作,知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。
6*.串的有关知识,要求达到“领会”层次。
6.1串的有关概念及基本运算。
6.2串与线性表的关系。
6.3串的存储结构,要求达到“简单应用”层次。
6.4串的两种存储表示。
6.5串的匹配算法
7*.多维数组,要求达到“领会”层次。
4.1多维数组的逻辑结构。
4.2多维数组的顺序存储结构及地址计算公式。
4.3数组是一种随机存取结构的原因。
第3章栈和队列
(一)课程内容
3.1栈
3.2队列
3.3栈和队列的应用
(二)学习目的与要求
本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。
要求在掌握栈和队列的特点的基础上,懂得在什么样的情况下选择使用栈或队列。
本章重点是掌握栈和队列在两种存储结构上实现的基本运算,难点是循环队列中对边界条件的处理。
(三)考核知识与考核要求
1.栈的逻辑结构、存储结构及其相关算法,要求达到“综合应用”层次。
1.1栈的逻辑结构特点,栈与线性表的异同。
1.2顺序栈和链栈上实现的进栈、退栈等基本算法。
1.3栈的“上溢”和“下溢”的概念及其判别条件。
1.4利用栈设计算法解决简单的应用问题。
2.队列的逻辑结构、存储结构及其相关的算法,要求达到“综合应用”层次。
2.1队列的逻辑结构特点,队列与线性表的异同。
2.2顺序队列(主要是循环队列)和链队列上实现的入队、出队等基本算法。
2.3队列的“上溢”和“下溢”的概念及其判别条件。
2.4使用顺序实现的循环队列取代普通的顺序队列的原因。
2.5循环队列中对边界条件的处理方法。
2.6利用队列设计算法解决简单的应用问题。
3.栈和队列的应用选择,要求达到“简单应用”层次。
3.1栈和队列的特点,什么样的情况下选择使用栈或队列。
第4章树
(一)课程内容
4.1树的概念
4.2二叉树
4.3二叉树的遍历
4.4*线索二叉树
4.5树和树林
4.6哈夫曼树及其应用
(二)学习目的与需求
本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化,树的定义、存储结构、遍历、树和树林与二叉树的转换,哈夫曼树及哈夫曼编码等内容。
要求在熟悉这些内容的基础上,重点掌握二叉树的遍历算法及其有关应用,难点是使用本章所学到的有关知识设计出有效算法,解决与树或二叉树相关的应用问题。
(三)考核知识点与考核要求
1.树的概念,要求达到“领会”层次。
1.1树的逻辑结构特征。
1.2树的不同表示方法。
1.3树的常用术语及含义。
2.二叉树,要求达到“简单应用”层次。
2.1二叉树的递归定义及树与二叉树的差别。
2.2二叉树的性质,了解相应的证明方法。
2.3二叉树的存储方法:
顺序和链接,它们的特点及适用范围。
3.二叉树的遍历,要求达到“综合应用”层次。
3.1二叉树的三种遍历(递归和非递归)算法,理解其执行过程。
3.2确定三种遍历所得到的相应的结点访问序列。
3.3以遍历算法为基础,设计有关算法解决简单的应用问题。
4*.线索二叉树,要求达到“领会”层次。
4.1二叉树线索化的目的及实现。
4.2在中序线索树中查找给定结点的中序前趋和中序后继的方法。
5.树和树林,要求达到“领会”层次。
5.1树和树林与二叉树之间的转换。
5.2树和树林的存储表示:
双亲表示法、子表表示法和长子-兄弟表示法。
5.3树和树林的遍历方法:
先根、中根、后根和层次。
6.哈夫曼树及其应用,要求达到“简单应用”层次。
6.1哈夫曼树的定义。
6.2哈夫曼算法的思想。
6.3根据给定的叶结点及其权值构造出相应的哈夫曼树。
6.4根据哈夫曼树给出对应的哈夫曼编码。
第5章图
(一)课程内容
5.1图的概念
5.2图的存储结构
5.3图的遍历
5.4生成树和最小生成树
5.5*最短路径
5.6*拓扑排序
5.7*关键路径
(二)学习目的与要求
本章目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法,要求在熟悉这些内容的基础上,重点掌握在图的两种存储结构上实现的遍历算法。
本章难点是图的应用算法;求最小生成树,求最短路径,求关键路径以及拓扑排序等。
(三)考核知识与考核要求
1.图的概念,要求达到“领会”层次。
1.1图的逻辑结构特征。
1.2图的常用术语及含义。
2.图的存储结构,要求达到“简单应用”层次。
2.1图的邻接矩阵和邻接表表示法。
2.2根据应用问题的特点和要求选择合适的存储结构。
3.图的遍历,要求达到“简单应用”的层次。
3.1连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。
3.2确定两种遍历所得到的顶点访问序列。
3.3两种遍历所使用的辅助数据结构(栈或队列)在遍历过程中所起的作用。
4.生成树和最小生成树,要求达到“领会”层次。
4.1生成树和最小生成树的概念。
4.2对遍历给定的图,画出深度优先和广度优生成树或生成树林。
4.3Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。
4.4要求对给定的连通图,根据Prim和Kruskal算法构造出最小生成树。
5*.最短路径,要求达到“领会”层次。
5.1最短路径的含义。
5.2求单源最短路径的Dijkstra算法的基本思想和时间性能。
6*.拓扑排序,要求达到“领会”层次。
6.1拓扑排序的基本思想和步骤。
6.2拓扑排序不成功的原因。
6.3对给定的有向图,若拓扑序列存在,则要求写出一个或多个拓扑序列。
7*关键路径,要求达到“领会”层次。
7.1用AOE网表示工程计划。
7.2关键路径的定义。
7.3求关键路径的算法。
7.4求关键路径的算法的时间复杂性。
第6章字典与检索
(一)课程内容
6.1基本概念
6.2线性表表示
6.3二叉树表示
6.4散列表表示
6.5*AVL树,B-树和B+树
(二)学习目的与要求
本章目的是介绍字典的线性表表示、二叉树表示和散列表表示。
要求在熟悉这些内容的基础上,重点掌握顺序查找、二分查找,二叉排序树上查找以及散列表上查找的基本思想和算法实现。
本章难点是二叉查找树的删除算法。
(三)考核知识点与考核要求
1.基本概念,要求达到“领会”层次
1.1字典的定义
1.2查找在数据处理中的重要性。
1.3查找算法效率的评判标准。
2.线性表的查找,要求达到“综合应用”层次。
2.1顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。
2.2二分查找对存储结构及关键字的要求。
2.3通过比较线性表上三种查找方法的优缺点,能根据实际问题的要求和特点,选择出合适的查找方法。
3.二叉排序树,要求达到“简单应用”层次。
3.1二叉排序树的定义、特点以及用途。
3.2二叉排序树的插入、删除、建树和查找算法及时间性能。
3.3建立一棵二叉排序树的过程实质上是对输入实例的排序过程,输入实例对所建立的二叉排序树形态的影响。
4.散列技术,要求达到“简单应用”层次。
4.1散列表、散列函数、散列地址和装填因子等有关概念。
4.2散列函数的选取原则及产生冲突的原因。
4.3几种常用的散列函数构造方法。
4.4两类解决冲突的方法及其优缺点。
4.5产生“堆积”现象的原因。
4.6采用线性探测法和拉链法解决冲突时,散列表的插入、查找算法以及实现和以及对一个具体散列表查找的性能分析。
4.7散列表和其它查找表的区别。
5*.AVL树表示,要求达到“领会”层次。
5.1AVL树定义。
5.2调整平衡模式。
5.3插入一个结点的算法。
6*.B-树表示,要求达到“领会”层次。
6.1B-树的定义。
6.2B-树的插入、删除及查找方法。
6.3B-树的查找效率。
7*.B+树表示,要求达到“领会”层次。
7.1B+树的定义。
7.2B+树的插入、删除及查找方法。
7.3用B+树组织索引顺序文件。
第7章排序
(一)课程内容
7.1基本概念
7.2插入排序
7.3交换排序
7.4选择排序
7.5归并排序
7.6*分配排序
7.7各种排序方法的比较和选择
(二)学习目的与要求
本章目的是介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。
要求在熟悉这些内容的基础上,重点掌握快速排序、堆排序、归并排序和分配排序的基本思想及排序过程,本章难点是这四个排序算法的实现。
(三)考核知识点与考核要求
1.基本概念,要求达到“识记”层次。
1.1排序在数据处理中的重要性。
1.2排序方法的“稳定”性含义。
1.3排序方法的分类及算法好坏的评判标准。
2.插入排序,要求达到“综合应用”层次。
2.1直接插入排序的基本思想和算法实现,以及在最好、最坏和平均情况下的时间性能分析。
2.2直接插入排序中哨兵的作用。
2.3针对给定的输入实例,要能写出直接插入排序的排序过程。
3.交换排序,要求达到“综合应用”层次。
3.1冒泡排序的基本思想。
3.2快速排序的基本思想和算法实现,以及在最坏和平均情况下的时间性能分析,了解算法的稳定性。
3.3基准元素(划分元)对划分是否平衡的影响。
3.4针对给定的输入实例,能写出快速排序的排序过程。
4.选择排序,要求达到“简单应用”层次。
4.1堆、小根堆、大根堆、堆顶等有关概念和定义。
4.2堆性质及堆与完全二叉树的关系。
4.3直接选择排序和堆排序的基本思想和算法实现,以及时间性能分析。
4.4针对给定的输入实例,写出堆排序的排序过程。
5.二路归并排序,要求达到“领会”层次。
5.1二路归并排序的基本思想和算法实现,以及时间性能分析。
5.2针对给定的输入实例,能写出二路归并排序的排序过程。
6.分配排序,要求达到“领会”层次。
6.1分配排序和基数排序的基本思想和算法实现,以及时间性能分析。
6.2针对给定的输入实例,能写出分配排序和基数排序的排序过程。
6.3分配排序与其它几类排序的区别。
7.各种排序方法的比较和选择,要求达到“简单应用”层次。
7.1通过对被排序的记录数目、记录信息量的大小、关键字的结构及初始状态、稳定性要求、辅助空间的大小、各种时间性能等方面的比较掌握各种排序的优缺点。
7.2根据实际问题的特点和要求选择合适的排序方法。
第8章*文件
(一)课程内容
8.1文件的基本概念
8.2顺序文件
8.3索引文件
8.4索引顺序文件
8.5散列文件
8.6多关键字文件
(二)学习目的与要求
本章目的是介绍存储在外存上的数据结构(即文件)的有关概念、各种文件的特点、组织方法及查询和修改操作,要求对这些内容做一般性的了解。
(三)考核知识点与考核要求
1.文件的基本概念,要求达到“识记”层次。
1.1文件的有关概念。
1.2文件的逻辑结构及其操作。
1.3物理记录与文件的的读写过程(领会层次)。
1.4文件的存储结构(组织方式)分类。
1.5评价文件组织效率的标准。
2.顺序文件,要求达到“识记”层次。
2.1顺序文件的特点及外存种类的适应性。
2.2顺序文件上各种查找方法的基本思想及对外存种类的要求。
3.索引文件,要求达到“识记”层次。
3.1索引文件的组织方式和特点。
3.2索引文件的查询和修改操作的基本思想。
4.索引顺序文件,要求达到“识记”层次。
4.1索引顺序文件是最常用的一种文件组织方式的原因。
4.2两种最常用的索引顺序文件(ISAM文件和VSAM文件)的组织方式和特点。
4.3在ISAM文件和VSAM文件上查询和修改操作的基本思想。
5.散列文件,要求达到“识记”层次。
5.1散列文件的组织方式和特点。
5.2散列文件的查询和修改操作的基本思想。
6.多关键字文件,要求达到“识记”层次。
6.1多关键字文件与其它文件的区别。
6.2多重表文件和倒排文件的组织方式和特点。
实践环节:
(一)类型
课程实验
(二)目的与要求
通过上机实验加深对课程内容的理解,增加感性认识,提高算法设计、程序编写及调试的能力。
要求所编的程序能正确运行,并提交实验报告。
实验报告的基本要求为:
1.需求分析:
陈述程序设计的任务,强调程序要做什么,明确规定:
(1)输入的形式和输入值的范围;
(2)输出的形式;
(3)程序所能达到的功能;
2.概要设计:
说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。
3.详细设计:
提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。
4.调试分析:
(1)调试过程中所遇到的问题及解决方法;
(2)算法的时空分析;
(3)经验与体会。
5.测试结果:
列出对于给定的输入所产生的输出结果。
若可能,测试随输入规模的增长所用算法的实际运行时间的变化。
(三)内容
1.单链表
(a)用单链表实现一元多项式的四则运算。
(b)用单链表实现集合的并、交、差运算。
注:
(a)和(b)由教员选一。
2.栈
利用栈,计算简单算术表达式的值。
3.二叉树操作
(a)要求采用二叉链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作等。
(b)利用栈,把简单算术表达式翻译成二叉树(用二叉链表表示),然后,按后根次序遍历这棵二叉树,输出算术表达式的后缀表示。
注:
(a)和(b)由教员选一。
4.图的遍历操作
可采用邻接矩阵或邻接表作为存储结构,完成有向图和无向图的DFS和BFS操作。
5.捡索
实现顺序查找、折半查找及二叉排序树上的查找算法,比较它们的查找效率。
实验时所输入的数据可按有序和随机产生组织。
6.排序
实现直接插入、冒泡、直接选择、快速、堆、归并等排序算法。
比较各种排序算法的运行速度。
建议用菜单组织以上各种操作。
(四)与课程考试之关系
本课程的实验必须和课堂教学同步进行,在期末考试前完成,教员要加强辅导,认真检查,学生实验的成绩应做为学生平时成绩的一部份。
鼓励教员根据各系各专业的实际情况,使实验的内容更联系实际,使学生更有兴趣。
教员对学生的成绩评定:
1.平时成绩(书面作业+实验+上课):
40分
2.期末考试:
60分
注:
1.打星号的章节是可选内容。
2.关于“课程内容与考核目标”中的有关提法的说明:
大纲在“考核知识点与考核要求”中提出了“识记”、“领会”、“简单应用”和“综合应用”四个能力层次要求,四个能力层次之间是递进等级关系,各能力层次的含义是:
(1)识记:
要求能够识别和记忆有关知识点的主要内容(如定义、术语、概念、重要结论、方法、步骤及特征、特点等),并能够从不同的角度做出正确的表述、选择和判断。
(2)领会:
要求能够领悟和理解本课程中规定的有关知识点的内涵与外延,熟悉其内容要点和它们之间的区别和关系,并能做出正确的解释、说明和陈述。
(3)简单应用:
要求能够运算本课程中规定的少量知识点,分析和解决一般的应用问题,例如,简单的算法设计和时间性能分析。
(4)综合应用:
要求能够运用本课程中规定的多个知识点,分析和解决较复杂的应用问题,例如,设计较复杂的算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 教学大纲