数据结构与算法“检索”教学设计 北京大学信息科学技术学院张铭 1.检索在课程中的定位和前测知识点 检索是各种数据结构中必不可少的运算,也是许多计算机应用程序的核心功能。在数据 处理中,经常涉及到信息存储和信息检索,即对所存储的数据进行快速有效的检索操作 检索一章主要介绍了一些检索的基本知识,侧重于基于线性表的检索和基于散列表的 检索。基于线性表的检索介绍了顺序检索和二分检索,并简单讨论了算法中的分支策略。基 于散列表的检索是本章的重点,也是难点。散列函数和冲突解决技术是散列算法的核心 前测知识点要求如下,可以根据需要给学生补充: (1)基于数组和链表的线性表相关算法、排序算法 (2)掌握概率的基本概念,理解等概率假设; (3)集合的基本概念和相关性质。 2.学习目标 (1)理解检索的基本概念,熟练掌握各种主要检索算法; (2)能根据概率知识衡量检索算法的效率,理解各种算法的优缺点 (3)理解分治算法的思想,会设计一般的分治算法 4)重点掌握基于散列的检索算法,掌握各种散列函数、散列探查方法 (5)了解集合检索相关知识。 3.知识点和学时分配 理论授课4学时,建议安排实验10学时 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉 猎面 各知识点建议授课时间如下: 检索的基本概念0.5小时 基于线性表的检索1小时 基于集合的检索 0.5小时 散列方法 2小时 4.重点和难点 检索重点如下: (1)衡量检索算法的效率,评价各种算法的优缺点 (2)基于线性表的检索算法,即顺序检索、二分检索、分块检索: (3)二分检索与分治算法的思想 (4)基于散列的检索算法,各种散列函数、散列探查方法。 检索难点如下: (1)散列方法,包括各种散列函数以及碰撞的处理方法;数据结构与算法“检索”教学设计 北京大学信息科学技术学院 张铭 1. 检索在课程中的定位和前测知识点 检索是各种数据结构中必不可少的运算，也是许多计算机应用程序的核心功能。在数据 处理中，经常涉及到信息存储和信息检索，即对所存储的数据进行快速有效的检索操作。 检索一章主要介绍了一些检索的基本知识，侧重于基于线性表的检索和基于散列表的 检索。基于线性表的检索介绍了顺序检索和二分检索，并简单讨论了算法中的分支策略。基 于散列表的检索是本章的重点，也是难点。散列函数和冲突解决技术是散列算法的核心。 前测知识点要求如下，可以根据需要给学生补充： （1）基于数组和链表的线性表相关算法、排序算法； （2）掌握概率的基本概念，理解等概率假设； （3）集合的基本概念和相关性质。 2．学习目标 （1）理解检索的基本概念，熟练掌握各种主要检索算法； （2）能根据概率知识衡量检索算法的效率，理解各种算法的优缺点； （3）理解分治算法的思想，会设计一般的分治算法； （4）重点掌握基于散列的检索算法，掌握各种散列函数、散列探查方法； （5）了解集合检索相关知识。 3. 知识点和学时分配 理论授课 4 学时，建议安排实验 10 学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉 猎面。 各知识点建议授课时间如下： 检索的基本概念 0.5 小时 基于线性表的检索 1 小时 基于集合的检索 0.5 小时 散列方法 2 小时 4．重点和难点 检索重点如下： （1）衡量检索算法的效率，评价各种算法的优缺点； （2）基于线性表的检索算法，即顺序检索、二分检索、分块检索； （3）二分检索与分治算法的思想； （4）基于散列的检索算法，各种散列函数、散列探查方法。 检索难点如下： （1）散列方法，包括各种散列函数以及碰撞的处理方法；