授课教案 2010～ 2011 学年 1 学期 开课单位：数学计算机科学学院 课程名称：数据结构 课程性质：专业基础课 学分：3 总学时：51 理论学时：51 实验学时：0 机动学时：0 授课专业：计算机科学技术/地理信息系统 授课年级：2009 级/2008 级 学生人数：80/37 多媒体授课时数比例：100% 主讲教师：左开中 职 称：副教授 《数据结构》授课教案 周次 第1 周 第1 次 章节名称 第一章：绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法与算法分析 授课方式 多媒体教室课堂讲授 教具准备 自制PPT 电子课件 教 学 目 的 1．了解学习掌握数据结构的意义及数据结构的基本内容； 2．掌握数据结构及数据、数据元素等相关概念； 2．掌握抽象数据类型ADT的定义、表示与实现 4．理解时间复杂度概念和基本的估算方法。 教 学 重 点 1．数据结构的基本概念 2．算法分析 教 学 难 点 1．抽象数据类型ADT的定义、表示与实现 2．算法时间复杂度及其计算 授课要点 1 .1 什么是数据结构 用 3 个引例： 1．图书书目自动检索 2．人机对奕 3．交通灯管理 引出《数据结构》的研究内容 1 .2 基本概念和术语 1. 数据 2. 数据元素、数据项 3. 数据对象、数据结构 4. 四类基本逻辑结构：集合、线性结构、树形结构、图形结构或网状结构。 5. 数据结构一般包括三方面的内容： 逻辑结构、存储结构(物理结构)和数据的运算 算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。 6. 数据的两种存储结构： 顺序存储结构和链式存储结构 1.3 抽象数据类型的表示与实现 ADT 的概念和类C 语言 1.4 算法和算法分析 1.4.1 算法 算法的定义 算法具有五个重要特性： 有穷性、确定性、可行性、输入、输出 1.4.2 算法设计的要求 正确性，可读性，健壮性，高效率低存储 1.4.3 算法效率的度量 时间复杂度 1.4.4 算法的存储空间需求 空间复杂度 课堂讨论 与练习 1．什么是数据结构？数据、数据对象、数据元素、数据项等术语的关系和区别？ 2．数据类型和抽象数据类型是如何定义的，二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 3．按照阶由低到高的顺序排列下列时间复杂度： 作业 1．分析并计算下面各程序段的最大语句频度和算法的时间复杂度。 1） for (i=0;i
