《数据结构与算法》教学大纲(本科64)

1、院 ( 系 ) 教 研 室：软件适 用 专 业 ：计算机科学与技术上 海 第 二 工 业 大 学计算机科学与技术专业数据结构与算法教学大纲（64 学时）一、课程的性质和任务性质：本课程是计算机科学与技术专业的一门主要专业技术基础课程。任务：学会分析研究计算机的数据对象的特性，以便选择适当的数据结构和存贮结构以及相应的算法，并初步掌握算法的时间分析及空间分析的方法。二、课程的基本要求（通过本课程学习应使学生了解、理解、掌握、熟练掌握的知识和技能）（表、树、图，熟炼掌握各类数据结构的基本操作及其应用。在此基础上，着重理解查找和内部排序。初步掌握算法的时间分析及空间分析的方法。进一步提高程序设计和实

2、现能力。三、课程内容（含实验内容和各章的教学要求、重点、难点和教学建议）绪论了解数据结构的发展及所处的地位，并掌握数据结构的基本概念和术语、算法的描述及算法分析的方法。线性表熟练掌握线性数据结构的基本操作所对应的算法并能灵活使用线性表这类基本数据结构。线性表及其基本操作。线性表的顺序存贮结构顺序存贮结构、类型描述、插入、删除、查找操作的实现算法描述。线性表的链式存贮结构顺序存贮的优缺点，线性链表、循环链表、双向链表、静态链表及其基本操作的算法。重点：单链表实验：单链表的建立、插入及删除等基本操作的算法堆栈和队列掌握栈和队列的基本概念及其应用。注意这类数据结构与线性表的异同点。栈：定义及其在两种

3、存贮结构下的进栈出栈算法栈的应用：进制转换、表达式的求值队列：定义及进队出队算法，链队列、循环队列重点：栈及其操作串了解串的概念、定义及存贮结构数组和广义表掌握数组的定义及地址公式，掌握特殊矩阵的存贮方式，了解广义表的概念数组的定义及运算存贮结构：地址计算公式矩阵的压缩存贮：特殊矩阵：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵、三元组表、十字链表广义表的基本概念重点：特殊矩阵的存贮方式难点：矩阵转置树和二叉树掌握树及二叉树的基本概念，掌握二叉树的遍历、线索化及其应用树的定义二叉树：定义、性质、存贮结构遍历二叉树及线索二叉树：先序、中序、后序遍历，线索二叉树树和森林：存贮结构、森林与二叉树的转换、树

4、的遍历、哈夫曼树、哈夫曼编码重点：二叉树的遍历及其应用难点：线索二叉树、哈夫曼树的算法图掌握图的有关术语、存贮结构、及图的各类应用图的定义及术语存贮结构：数组表示法、邻接表图的遍历：深度优先搜索、广度优先搜索最小生成树：掌握普里姆算法有向无环图及其应用：拓扑排序、关键路径、最短路径（Dijkstra, Floyd算法）重点：存贮结构难点：无向图的遍历、最短路径、拓扑排序算法查找哈希表的特点顺序表的查找：顺序、折半及分块查找树表查找：二叉排序树哈希表：定义、函数构造、冲突处理方法重点：一般查找方法及树表查找的概念及算法难点：二叉排序树算法排序掌握内排序的概念，掌握内部排序各种方法的算法思想，了解

5、各种不同排序方法的适用场合。概述的算法。重点：插入排序、快速排序、选择排序及基数排序的算法。难点：快速排序、堆排序、归并排序算法四、本课程与其它课程关系（写明先修后续的课程与本课程的关系：本课程是一门综合的专业基础课。它的研究不仅涉及到计算机硬件的研究范围，而且与计算机软件的研究有密切的关系。而无论是“编译原理”还是“操作系统”都涉及到数据元素在存贮器中的分配问题。在研究信息检索时也必须考虑如何组织数据以便查找和存取更为方便。它是介于数学、计算机硬件、软件三者之间的一门核心课程。先修课程：C 语言程序设计、离散数学后续课程：编译原理、操作系统、软件工程、数据库原理等课程章章教学内容次总学时讲 （实题（课课 ）验大 论 课 设课 或 计一绪论二线性表三堆栈和队列四串五数组和广义表六树七图八查找九排序小计五、学时分配）331172