《数据结构》课程教学大纲重庆电大远程教育导学中心理工导学部第一部分大纲说明一、课程的性质和任务《数据结构》是专科计算机应用专业的一门统设必修课。开设本课程的目的，是要求学生通过本课程的学习，对课程的基本概念，基本知识和基本技能进行掌握。通过对各种数据结构的逻辑结构，存储结构及有关操作算法的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。《数据结构》是实践性很强的课程,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。二、与相关课程的衔接《数据结构》的先修课主要是《C++语言程序设计》，本课程将以C++语言作为算法描述和上机实践的工具。同时，本课程又是软件开发与设计等课程的基础。三、课程教学的基本要求1、全面了解课程的体系、结构，对课程内容有总体的把握；2、牢固掌握课程的基本概念，基本知识和基本技能；3、通过数据结构理解，提高程序阅读与分析能力，形成一定的数据抽象能力和程序设计的能力。四、教学方法与教学形式以学生为主体，采用个别化自主学习、小组/协作学习、集中学习三种学习组织方式进行。教学中将音像教学与面授辅导相结合，加强实验环节的教学。在教学中注意发挥导学、助学、促学的作用。五、课程教学要求的层次教学要求大体分为三个层次:了解、掌握和熟练掌握。了解就是正确理解概念；掌握就是学会所给的知识；熟练掌握就是会运用所学知识解决实际问题。第二部分多媒体教材一体化设计方案一、课程的基本结构第一部分：绪论第二部分：线性表、稀疏矩阵和广义表、栈和队列、树和二叉树、二叉树的应用、图第三部分：查找、排序二、学时分配比例本课程开设一学期，共90学时（其中授课45学时，实验27学时，大作业18学时），5学分。建议大作业学时可以分配到实验和面授中，不必硬性规定。授课学时分配参考：章节内容学时分配第一章绪论4第二章线性表6第三章稀疏矩阵和广义表3第四章栈和队列6第五章树和二叉树5第六章二叉树的应用4第七章图5第八章查找5第九章排序5复习2合计45本课程要求至少完成一个大作业，18学时。要求学生独立完成，并上机运行，打印结果，同时写出实验报告及程序清单，指导教师要认真评定，给予评语。题目从下列题目中任选其一：（1）带索引文件的插入、删除和查找操作（2）散列文件的插入、删除和查找操作具体内容及要求见本课程的实验指导书。上机实践27学时，从中至少任选7个。序号实验内容上机学时1线性表操作42单链表操作43表达式计算44二叉树操作45二叉搜索树操作46图的运算47散列表操作48外存文件的排序操作49二叉搜索树与文件操作4三、多媒体教材的构成1、印刷媒体。主教材《数据结构》许卓群主编中央广播电视大学出版社出版。实验教材《数据结构实验》徐孝凯编中央广播电视大学出版社出版。辅助教材《数据结构习题解析》徐孝凯编中央电大教育杂志社出版，通过各地电大教材发行部门统一征订发行。2、音像媒体。《数据结构》20讲刘杰主讲中央电大音像出版社出版。3、网络媒体。见电大在线平台。具备电子教案、重难点辅导、平时作业、自检自测等资源。第三部分课程教学内容和教学要求第一章绪论［教学内容］1、数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。2、抽象数据类型。3、描述算法所用的C++语言中的一些有关问题。4、算法时间复杂度和空间复杂度的分析。［教学要求］掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。第二章线性表［教学内容］1、线性表的基本概念和类型定义2、线性表的顺序存储结构3、线性表的链接存储结构（1）单链表的查找、插入和删除（2）循环链表（3）双向链表注：建议将字符串处理作例子加入教学内容。［教学要求］掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法。第三章稀疏矩阵和广义表［教学内容］1、稀疏矩阵的定义、存储和运算2、广义表的定义、存储和运算［教学要求］掌握稀疏矩阵的定义和各种存储结构，掌握广义表的定义、存储结构和求广义表的长度及深度的算法，掌握稀疏矩阵的转置和相加的方法并了解其算法，掌握建立广义表和输出广义表的方法并了解其算法。第四章栈和队列［教学内容］1、栈的类型定义2、栈的顺序存储和链