《数据结构》教学大纲课件.doc

《《数据结构》教学大纲课件.doc》由会员分享，可在线阅读，更多相关《《数据结构》教学大纲课件.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件开发与应用、计算机网络与维护等专业数据结构教学大纲第一部分 大纲说明1课程性质、任务与目的数据结构课程是浙江广播电视大学软件开发与应用、计算机网络与维护等专业的一门核心课程，主要任务是讨论各种数据组织中的数据逻辑结构，存储结构以及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。2与其他课程的关系数据结构的先修课主要是C+语言程序设计，本课程将以C+语言作为算法描述和上机实践的工

2、具。同时，本课程又是软件开发与设计等课程的基础。3课程特点数据结构是实践性很强的课程,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。4教学要求教学要求在每章教学内容之后给出,大体分为三个层次:了解、掌握和熟练掌握。它们的含义大致为:了解就是正确理解概念,掌握就是学会所给的知识,熟练掌握就是会运用所学知识解决实际问题。第二部分 媒体使用和教学过程建议1学时分配本课程共72学时,4 学分。面授和实验各占54和18学时。学时分配如下：(1) 录像媒体教学36学时:章号内容时数一绪论1二线性表3三稀疏矩阵和广义表2四栈和队列2五树和二叉树3六二叉树的应

3、用2七图3八查找2九排序2 (2)上机实践18学时，从中至少任选6个。 序号实验内容上机学时1线性表操作32单链表操作33表达式计算34二叉树操作35二叉搜索树操作 36图的运算37散列表操作38外存文件的排序操作39二叉搜索树与文件操作3 2多种媒体教材的说明及教学环节文字教材、实验教材及电视讲课均由中央广播电视大学统一提供。文字教材应系统、完整而又深入浅出，适合自学，音像教材应突出重点和难点，二者可以相互补充配合，但电视讲课仍应以文字教材为主要依据。面授应指导和帮助学生掌握重点，突破难点，分析算法的思路与方法，指出常见的错误。上机实践，应有实验教师指导和辅导。3考核本课程考核采用期末考核与

4、形成性考核相结合的方式形成性考核：视平时作业和实验等情况给分，占考核总成绩的20%。形成性考核成绩由所在教学点评定。期末考核：采用笔试，占总成绩的80%，由浙江广播电视大学统一命题，考试方式为一纸开卷，答卷时限为90分钟。实验不占学分，但必须实验合格者方可参加笔试，合格标准由所在教学点参照该教学大纲制定。第三部分 教学内容和教学要求第一章 绪论(一) 教学内容1. 数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。2. 抽象数据类型。3. 描述算法所用的C+语言中的一些有关问题。4. 算法时间复杂度和空间复杂度的分析。(二) 教学要求掌握数据结构的一些基本概

5、念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。第二章 线性表(一) 教学内容1. 线性表的基本概念和类型定义2. 线性表的顺序存储结构3. 线性表的链接存储结构(1) 单链表的查找、插入和删除(2) 循环链表(3) 双向链表注：建议将字符串处理作例子加入教学内容。 (二) 教学要求掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法。第三章 稀疏矩阵和广义表(一) 教学内容1稀疏矩阵的定义、存储和运算2广义表的定义、存储和运算(二) 教学要求掌握稀疏矩阵的定

6、义和各种存储结构，掌握广义表的定义、存储结构和求广义表的长度及深度的算法，掌握稀疏矩阵的转置和相加的方法并了解其算法，掌握建立广义表和输出广义表的方法并了解其算法。第四章 栈和队列(一)教学内容1. 栈的类型定义2. 栈的顺序存储和链接存储的表示3. 在栈的顺序存储和链接存储上进行各种栈操作的算法4. 栈的应用举例(1)表达式求值(2)迷宫求解5. 队列的类型定义6. 队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法(二) 教学要求掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现，掌握表达式求值和逼宫求解的方法并了解其算法。第五章 树和二叉树(一)教学

7、内容1. 树的定义、性质和表示方法 2. 二叉树的定义、性质和存储结构3. 二叉树的各种遍历方法及实现4. 建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现5. 树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法(二)教学要求掌握树的定义、性质、存储结构及遍历算法，熟练掌握二叉树的各种遍历方法及其实现，掌握二叉树的其他操作方法及实现，了解树和二叉树的转换方法。第六章 二叉树的应用(一)教学内容1. 二叉搜索树的定义及运算2. 堆的定义、存储结构及运算3. 哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的方法(二)教学要求掌握二叉搜索树的定义、熟练掌握对二

8、叉搜索树进行插入和查找的方法和实现、熟练掌握对堆进行查找和删除的方法和实现，掌握哈夫曼树的定义和构造哈夫曼树的方法，了解二叉搜索树的删除方法，了解哈夫曼树编码的方法。第七章 图(一)教学内容1. 图的定义和术语2. 图的邻接矩阵、邻接表和边集数组表示3. 图的深度和广度优先搜索遍历4. 图的生成树和最小生成树5. 拓扑排序(二)教学要求掌握图的定义和术语；熟练掌握图的存储结构及深度和广度优先搜索方法及其实现；掌握图的生成树的概念，掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；掌握拓扑排序的方法并了解其实现算法。第八章 查找(一)教学内容1. 顺序查找和二分查找2索引查找和分

9、块查找3. 散列查找4. B树查找(二)教学要求熟练掌握顺序查找和二分查找的方法及实现；掌握索引表的定义、索引查找的方法及实现，掌握分块查找的方法及实现；掌握散列表的定义，利用除留余数法构造散列函数的方法，利用线性探查法和链接法处理冲突的方法；了解B树的定义，查找、插入和删除元素的方法；了解构造散列函数的其他方法，了解进行散列表查找、插入和删除的算法描述。第九章 排序(一)教学内容1.排序的概念2.直接插入排序2.冒泡排序和快排序3.直接选择排序和堆排序4.归并排序(二)教学要求掌握直接插入排序、直接选择排序、冒泡排序的方法及其实现，熟练掌握快排序、堆排序、二路归并排序的方法及其实现，掌握各种排序方法的稳定性、时间复杂度和空间复杂度。第四部分 实验一、实验内容实验内容应遵照实验教材中的安排去做，每个学生至少选做6个实验。二、实验要求要把每次实验的程序文本和运行结果存入到本人的用户目录下或专用软盘上供实验老师检查或上级部门抽查。三、对实验室要求1. 必须保证学生上机时人手一机;2. 必须保证满足课程要求的上机时数;3. 必须配备专职的数据结构课程的实验指导老师。浙江广播电视大学计算机科学与技术系2006年9月