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

《《数据结构与算法》教学大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江大学远程教育学院课程教学大纲课程名称数据结构与算法课程代码适用专业计算机科学与应用03年1月05日课程名称数据结构与算法课程代码5课程英文名称DataStructureandAlgorithms课程性质（公共必修/公共选修/专业必修/专业选修）专业必修适用层次（本科/研究生）本科适用专业（不分专业/XX专业）计算机科学与应用总学分5理论学分4实验学分1设计学分一、课程性质和任务本课程为专业基础课，也是专业主干课程（学位课程），本课程是计算机科学的算法理论基础和软件设计的技术基础,主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。课程的任务是学会

2、分析研究计算机加工的数据结构的特性；培养数据抽象的能力；训练学生进行复杂程序设计的技能和培养良好程序设计的习惯；初步掌握算法的时间分析和空间分析的技术。二、课程的基本要求掌握数据、数据结构、存储结构和抽象数据类型等的基本概念；熟悉算法的时间分析和空间分析的方法；熟练掌握线性表（包括栈和队列）的逻辑结构定义的各种存储结构的描述方法；熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；掌握串的类型定义、表示与实现，理解串的KMP模式匹配算法;掌握数组的两种存储表示方法及地址计算；熟悉特殊矩阵和稀疏矩阵的压缩存储表示方法、下标变换公式及适用范围

3、；掌握树（包括二叉树和森林）的定义、性质；熟练掌握二叉树的结构特性、遍历的算法及若干典型的应用；熟悉图（包括网络）的定义、性质；掌握图的各种存储结构、两种遍历策略及若干典型的应用；掌握顺序表和有序表的查找方法,掌握静态查找树和二叉排序树的构造和查找方法；掌握排序的定义和各种排序方法的特点；了解各种排序方法的排序过程及相应的时间复杂度分析方法；一般了解排序方法“稳定”的含义。5三、课程内容、掌握程度和课时安排（共60学时理论课）（一）绪论（4学时）1．回顾C语言：函数、指针和类型等的定义与使用、结构的定义、动态内存的申请等；2．掌握数据、数据元素、数据对象、

4、数据结构、存储结构和数据类型的概念和术语；3．熟悉抽象数据类型的定义、表示与实现；4．掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。（二）线性表（8学时）1．掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系；2．掌握线性表的顺序存储结构和链式存储结构的描述方法；3．熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；4．能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。（三）栈和队列（8学时）1．熟练掌握栈和队列的结构特性；2．熟练掌握栈类型在两种存储结构表示时的基本操作实现方法；3．熟练

5、掌握循环队列和链队列的基本操作实现算法；4．掌握栈和队列的典型应用，如：数制转换、迷宫求解、表达式求值等。(四)串（4学时）1．熟悉串的基本操作的定义，并利用它们实现串的其他操作；2．熟练掌握串在定长结构上的表示与实现各种操作的方法；3．理解串匹配的KMP算法，熟悉next函数的定义和手工计算next函数值。（五）数组（6学时）1．掌握数组的两种存储表示方法及以行为主的存储结构中的地址计算；2．熟悉对特殊矩阵进行压缩存储时的下标变换公式；3．掌握稀疏矩阵的三元组压缩存储表示方法，了解行逻辑链接的顺序表及适用范围；（六）树和二叉树（10学时）1．熟练掌握二叉

6、树的结构特性，了解证明方法；2．熟悉二叉树的各种存储结构特点及适用范围；3．熟悉三种遍历二叉树的递归算法；4．掌握二叉树线索化的实质及线索化的过程；5．熟悉树的有关术语和概念，掌握树和森林与二叉树的转换；6．了解最优树的特性，掌握Huffman树及其应用。（七）图（8学时）1．掌握图的定义和术语；2．掌握图的两种主要存储结构：数组表示法、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；3．掌握图的两种遍历策略：深度优先搜索和广度优先搜索；4．掌握图的最小生成树、AOE网络的关键路径、网络的最短路径等的应用。（八）查找（4学时）1．熟练掌握

7、顺序表和有序表的查找方法；2．熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；3．熟练掌握二叉排序树的构造和查找方法；4．掌握二叉平衡树的概念和维护平衡的方法。（九）内部排序（4学时）1．掌握排序的定义和各种排序方法的特点；2．了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法可以分为插入排序、交换排序、选择排序、归并排序和基数排序；3．能够进行各种排序方法的时间复杂度分析；4．一般了解排序方法“稳定”的含义。(十)复习（4学时）在期中考试和期末考试前分别安排2学时的复习课。5四、作业内容《数据结构题集》对应

8、各章的习题。第一章：1.1,1.2,1.5,1.6,1.8,1.9