山东轻工业学院 教师授课教案 课程名称： 数据结构（计科） 课程代码： 0 3 0 1 3 0 6 学 分： 4 .5 课程类别： 必修 开课单位: 信息科学与技术学院 授课班级： 授课教师： 杨春花 山东轻工业学院教务处制 授课时间 年 月 日 星期 第 节 年 月 日 星期 第 节 年 月 日 星期 第 节 授课内容概要 第八章 查找 第一节 静态查找表 查找的基本概念和术语；静态查找表的存储结构表示；顺序查找的过程、算法和性能分析；折半查找的过程、算法和性能分析；分块查找的过程和分析。 第二节 动态查找表 二叉排序树的定义；二叉排序树的查找、插入和删除；二叉排序树的查找分析；平衡二叉树的定义和平衡化的方法；B -树的定义、查找和查找分析、插入和删除，B +树的概念。 第三节 哈希表 哈希表、哈希函数、哈希地址、同义词等概念；哈希函数的构造方法；处理冲突的方法；哈希表的构造；哈希表的存储结构、查找算法和分析。 目的要求 目的：理解查找的基本方法。 基本要求：了解平衡二叉树的平衡化方法、B树的插入和删除和键树的概念；理解分块查找的基本思想、哈希表的基本概念、哈希函数的构造方法和处理冲突的方法；掌握查找的基本概念、顺序查找和折半查找的基本思想和算法、二叉排序树的概念和基本操作和哈希表的构造方法。 重 点 顺序查找和折半查找的思想、算法和分析；二叉排序树的概念、构造、插入和删除；B-树的插入和删除方法；哈希表的基本概念和哈希表的构造方法。 难 点 折半查找的算法和分析；二叉排序树的插入和删除；平衡二叉树的平衡化方法；B-树的插入和删除方法；哈希表的构造方法。 作业布置 习题 9 参考书 1. 数据结构题集(C语言版), 严蔚敏，清华大学出版社，2002。 3. 数据结构、算法与应用－C++语言描述，(美)Sartaj Sahni著，汪诗林等译，机械工业出版社，2002。 课 型 理论课 学 时 分 配 复 习 分钟 主要教具 投影、黑板 讲 授 分钟 教学方法 讲解、提问、示例 指 导 分钟 教学手段 板书、课件 总 结 分钟 备注 共 10学时，其中 2学时为习题课 注：课型一栏填写理论课、实验课、习题课等 授 课 内 容 备 注 第9 章 查找 9 .1 基本概念和术语 1 数据项 (也称项或字段): 是具有独立含义的标识单位，是数据不可分割的最小单位。 2 组合项 由若干项、组合项构成。 3 数据元素（记录） 是由若干项、...
