浙 江 大 学 远 程 教 育 学 院 课 程 教 学 大 纲 课程名称 数据结构与算法  课程代码   适用专业 计算机科学与应用   03 年 1 月 05 日   课 程 名 称 数据结构与算法 课程代码   课程英文名称 Data Structure and Algorithms  课程性质（公共必修/公共选修/专业必修/专业选修） 专业必修  适用层次（本科/研究生） 本科  适用专业（不分专业/XX专业） 计算机科学与应用  总学分 5 理论学分 4 实验学分 1 设计学分   一、课程性质和任务 本课程为专业基础课，也是专业主干课程（学位课程），本课程是计算机科学的算法理论基础和软件设计的技术基础, 主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。 课程的任务是学会分析研究计算机加工的数据结构的特性；培养数据抽象的能力；训练学生进行复杂程序设计的技能和培养良好程序设计的习惯；初步掌握算法的时间分析和空间分析的技术。  二、课程的基本要求 掌握数据、数据结构、存储结构和抽象数据类型等的基本概念；熟悉算法的时间分析和空间分析的方法；熟练掌握线性表（包括栈和队列）的逻辑结构定义的各种存储结构的描述方法；熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；掌握串的类型定义、表示与实现，理解串的KMP模式匹配算法;掌握数组的两种存储表示方法及地址计算；熟悉特殊矩阵和稀疏矩阵的压缩存储表示方法、下标变换公式及适用范围；掌握树（包括二叉树和森林）的定义、性质；熟练掌握二叉树的结构特性、遍历的算法及若干典型的应用；熟悉图（包括网络）的定义、性质；掌握图的各种存储结构、两种遍历策略及若干典型的应用；掌握顺序表和有序表的查找方法, 掌握静态查找树和二叉排序树的构造和查找方法；掌握排序的定义和各种排序方法的特点；了解各种排序方法的排序过程及相应的时间复杂度分析方法；一般了解排序方法“稳定”的含义。   三、课程内容、掌握程度和课时安排（共60学时理论课） （一）绪论（4学时） 回顾C语言：函数、指针和类型等的定义与使用、结构的定义、动态内存的申请等； 掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型的概念和术语； 3．熟悉抽象数据类型的定义、表示与实现； 4．掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。 （二）线性表（8学时） 掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系； 掌握线性表的顺序存储结构和链式存储结构的描述方法； 熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法； 4．能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。 （三）栈和队列（8学时） 熟练掌握栈和队列的结构特性； 熟练掌握栈类型在两种存储结构表示时的基本操作实现方法； 熟练掌握循环队列和链队列的基本操作实现算法； 掌握栈和队列的典型应用，如：数制转换、迷宫求解、表达式求值等。 (四) 串（4学时） 熟悉串的基本操作的定义，并利用它们实现串的其他操作； 熟练掌握串在定长结构上的表示与实现各种操作的方法； 理解串匹配的KMP算法，熟悉next函数的定义和手工计算next函数值。 （五）数组（6学时） 掌握数组的两种存储表示方法及以行为主的存储结构中的地址计算； 熟悉对特殊矩阵进行压缩存储时的下标变换公式； 掌握稀疏矩阵的三元组压缩存储表示方法，了解行逻辑链接的顺序表及适用范围； （六） 树和二叉树（10学时） 熟练掌握二叉树的结构特性，了解证明方法； 熟悉二叉树的各种存储结构特点及适用范围； 熟悉三种遍历二叉树的递归算法； 掌握二叉树线索化的实质及线索化的过程； 熟悉树的有关术语和概念，掌握树和森林与二叉树的转换； 了解最优树的特性，掌握Huffman树及其应用。 （七） 图（8学时） 掌握图的定义和术语； 掌握图的两种主要存储结构：数组表示法、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系； 掌握图的两种遍历策略：深度优先搜索和广度优先搜索； 掌握图的最小生成树、AOE网络的关键路径、网络的最短路径等的应用。 （八） 查找（4学时） 1．熟练掌握顺序表和有序表的查找方法； 2．熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系； 3．熟练掌握二叉排序树的构造和查找方法； 掌握二叉平衡树的概念和维护平衡的方法。 （九）内部排序（4学时） 掌握排序的定义和各种排序方法的特点； 了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法可以分为插入排序、交换排序、选择排序、归并排序和基数排序； 能够进行各种排序方法的时间复杂度分析； 一般了解排序方法“稳定”的含义。 (十) 复习（4学时）在期中考试和期末考试前分别安排2学时的复习课。  四、作业内容 《数据结构题集》对应各章的习题。 第一章： 1.1, 1.2, 1.5, 1.6, 1.8, 1.9, 1.10, 1.11 第二章： 2.2, 2.10, 2.11； 2.1, 2.3, 2.4, 2.6, 2.7, 2.8 第三章： 3.2, 3.3, 3.4, 3.5, 3.15；3.7, 3.11, 3.13, 3.18 第四章：4.3, 4.4, 求4.7, 4.8的next函数值 第五章：5.1, 5.2, 5.3, 5.6，5.8； 5.6, 5.7, 5.9 第六章：6.1-6.7； 6.12-6.16,6.23 第七章：7.1, 7.2, 7.4, 7.5 7.7； 7.10, 7.11 第九章：9.1, 9.2, 9.3, 9.10, 9.11 第十章：10.1, 10.3,10.7, 10.12  五、实验内容 本课程计划安排七个实验。每个实验通常有A实验和B实验。A实验是为实现教材中的算法而设计的，B实验是为了进一步使用教材中的算法和自我设计新算法而设计的。 实验0：C语言中函数定义与调用、 指针和类型的定义与使用、结构的定义、动态内存的申请等预备知识。 实验1：线性表的顺序表示与链式表示的插入与删除 A实验:　算法调试　　　　　　　　　　　　 B实验: 练习2.11 实验2：顺序栈与链式栈的实现与插入删除操作 A实验: 栈的基本算法调试及数制转换　　　　B实验: 练习3.15 实验3 ：链式队列与循环队列的实现与插入删除操作 A实验: 循环队列的实现算法 B实验: 练习3.28 实验4 ：稀疏矩阵的三元组表示与矩阵加法运算 A实验: 算法5.1,5.2的实现与调试 B实验: 练习5.21 实验5：二叉树的二叉链表示与三种遍历 A实验: 算法6.1,6.4的实现与调试 B实验: 算法6.2 实验6：图的邻接矩阵表示及其深度（广度）优先搜索 A实验: 算法7.1,7.2,7.4,7.5的调试 B实验: 算法7.6与习题7.5   六、推荐教材和课件  教 材 名 称 作 者 出 版 社 版本  （C语言版）数据结构 严蔚敏、吴伟民 清华大学出版社   （C语言版）数据结构题集 严蔚敏、吴伟民 清华大学出版社   课 件 名 称 作 者 出 版 社 版本  数据结构与算法 徐镜春 浙大远程教育        七、参考教材和课件  教 材 名 称 作 者 出 版 社 版本            课 件 名 称 作 者 出 版 社 版本            专业教学委员会意见： 主任（签字）： 年 月 日  学院审核意见： 主管领导（签字）： 单位公章 年 月 日