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

《《数据结构与算法》教学大纲(本科64).doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、，着重理解查找和内部排序。初步掌握算法的时间分析及空间分析的方法。进一步提高程序设计和实现能力。三、课程内容（含实验内容和各章的教学要求、重点、难点和教学建议）1.绪论了解数据结构的发展及所处的地位，并掌握数据结构的基本概念和术语、算法的描述及算法分析的方法。2.线性表熟练掌握线性数据结构的基本操作所对应的算法并能灵活使用线性表这类基本数据结构。线性表及其基本操作。线性表的顺序存贮结构顺序存贮结构、类型描述、插入、删除、查找操作的实现算法描述。线性表的链式存贮结构顺序存贮的优缺点，线性链表、循环链表、双向链表、静态链表及其基本操作的算法。重点：单链表实验：单链表的

3、建立、插入及删除等基本操作的算法3.堆栈和队列掌握栈和队列的基本概念及其应用。注意这类数据结构与线性表的异同点。栈：定义及其在两种存贮结构下的进栈出栈算法栈的应用：进制转换、表达式的求值队列：定义及进队出队算法，链队列、循环队列重点：栈及其操作1.串了解串的概念、定义及存贮结构2.数组和广义表掌握数组的定义及地址公式，掌握特殊矩阵的存贮方式，了解广义表的概念数组的定义及运算存贮结构：地址计算公式矩阵的压缩存贮：特殊矩阵：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵、三元组表、十字链表广义表的基本概念重点：特殊矩阵的存贮方式难点：矩阵转置3.树和二叉树掌握树及二叉树的基本

4、概念，掌握二叉树的遍历、线索化及其应用树的定义二叉树：定义、性质、存贮结构遍历二叉树及线索二叉树：先序、中序、后序遍历，线索二叉树树和森林：存贮结构、森林与二叉树的转换、树的遍历、哈夫曼树、哈夫曼编码重点：二叉树的遍历及其应用难点：线索二叉树、哈夫曼树的算法4.图掌握图的有关术语、存贮结构、及图的各类应用图的定义及术语存贮结构：数组表示法、邻接表图的遍历：深度优先搜索、广度优先搜索最小生成树：掌握普里姆算法有向无环图及其应用：拓扑排序、关键路径、最短路径（Dijkstra,Floyd算法）重点：存贮结构难点：无向图的遍历、最短路径、拓扑排序算法1.查找掌握各类查找

5、方法，掌握一般查找方法及树表查找的概念及算法，了解哈希表的特点顺序表的查找：顺序、折半及分块查找树表查找：二叉排序树哈希表：定义、函数构造、冲突处理方法重点：一般查找方法及树表查找的概念及算法难点：二叉排序树算法2.排序掌握内排序的概念，掌握内部排序各种方法的算法思想，了解各种不同排序方法的适用场合。概述内部排序：掌握插入排序、快速排序、选择排序、归并排序、基数排序的算法。重点：插入排序、快速排序、选择排序及基数排序的算法。难点：快速排序、堆排序、归并排序算法四、本课程与其它课程关系（写明先修后续的课程与本课程的关系）：本课程是一门综合的专业基础课。它的研究不仅涉

6、及到计算机硬件的研究范围，而且与计算机软件的研究有密切的关系。本课程中的“线性链表”等内容与“C语言”课程中的有关内容有联系，而无论是“编译原理”还是“操作系统”都涉及到数据元素在存贮器中的分配问题。在研究信息检索时也必须考虑如何组织数据以便查找和存取更为方便。它是介于数学、计算机硬件、软件三者之间的一门核心课程。先修课程：C语言程序设计、离散数学后续课程：编译原理、操作系统、软件工程、数据库原理等课程五、学时分配章次教学内容总学时讲课实验（上机）习题课或讨论课课程设计（大作业）一绪论33二线性表11722三堆栈和队列541四串11五数组和广义表541六树1282

7、2七图11722八查找551九排序11721小计6446810六、教材及参考书《数据结构》（C语言版）严蔚敏、吴伟民编著清华大学出版社　1997年4月第1版