本章的基本内容是：线性表的顺序查找、对分查找、分块查找、二叉排序树查找以及哈希表查找。
查找又称为检索，是一种经常用到的运算，即从一批记录的集合中，按照某个关键字查找特定的记录过程。
本章首先介绍了常用的3种基本查找方法。顺序查找对记录在表中存放的次序没有任何要求，查找的基本思路是从表的一端开始，顺序将各个单元数据与给定值进行比较，直至找到与给定值相同的数据，则查找成功，返回记录在表中的位置序号；若进行到表的另一端仍未找到与之相等的数据，则查找失败，返回0。对分查找比顺序查找速度快，但它要求表中数据有序，这是一个递归的过程，每次以查找范围中间的元素与给定值进行比较，这样即使此次没有查找到，也把下一步查找范围缩小了一半。分块查找是在顺序表基础上建立一个索引表，查找时，首先用给定值在索引表中查找，因为索引表是按关键字有序排列的，可以采用对分查找或顺序查找以确定待查记录在哪一块中，然后在已确定的块中进行顺序查找。
树形查找是利用二叉排序树存放原始数据，树的每个节点对应一条记录。查找过程是一种递归过程，首先以根节点数据与给定值进行比较，如果相等，则查找成功，否则转向其左子树或右子树继续进行树形查找。定义二叉树中每一节点的左子树高度减去右子树高度为该节点的平衡因子，任一节点的平衡因子只能为+1、0、-1三种取值的二叉树为平衡树。
散列查找是将每条记录的地址与该记录的关键字之间建立某种函数关系，可直接由关键字查找到该记录，不仅查找速度快，而且查找时间与记录条数无关。根据关键字求存储地址的函数称为散列函数。不同关键字计算出相同地址的情况称为产生了冲突。采用散列查找的关键是选择怎样的散列函数和出现了冲突如何处理。处理冲突的方法有开放地址法和链接表法。
在实际应用中，应根据各种查找方法的优缺点并结合具体情况来选择合适的查找方法。
1．选择题
（1）顺序查找法适合于存储结构为 的线性表。
A．散列存储 B．顺序存储或链接存储
C．压缩存储 D．索引存储
（2）对线性表进行对分查找时，要求线性表必须 。
A．以顺序方式存储
B．以顺序方式存储，且节点按关键字有序排列
C．以链接方式存储
D．以链接方式存储，且节点按关键字有序排列
（3）采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 。
A．n B．n/2 C．(n+1)/2 D．(n-1)/2
（4）采用对分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 。
A．O(n2) B．O(nlog2n) C．O(n) D．O(log2n)
（5）有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，当对分查找值为82的节点时， 次比较后查找成功。
A．1 B．2 C．4 D．8
（6）设哈希表长m=14，哈希函数H(key)=key%11。表中有4个节点：
addr(15)=4
addr(38)=5
addr(61)=6
addr(84)=7
其余地址为空。
如用二次探测再散列处理冲突，关键字为49的节点地址是 。
A．8 B．3 C．5 D．9
（7）有一个长度为12的有序表，按对分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为 。
A．35/12 B．37/12 C．39/12 D．43/12
（8）采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定节点所在的块时，每块应分 个节点最佳。
A．10 B．25 C．6 D．625
（9）如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用
查找方法。
A．分块 B．顺序 C．二分 D．散列
2．填空题
（1）顺序查找法的平均查找长度为 ；对分查找法的平均查找长度为
；分块查找法（以顺序查找确定块）的平均查找长度为 ；分块查找法（以对分查找确定块）的平均查找长度为 ；哈希表查找法采用链接法处理冲突时的平均查找长度为 。
（2）在各种查找方法中，平均查找长度与节点个数n无关的查找方法是 。
（3）对分查找的存储结构仅限于 ，且是 。
（4）在分块查找方法中，首先查找 ，然后再查找相应的 。
（5）长度为255的表，采用分块查找法，每块的最佳长度是 。
（6）在散列函数H(key)=key%p中，p应取 。
（7）假设在有序线性表A[1..20]上进行对分查找，则比较1次查找成功的节点数为
，则比较2次查找成功的节点数为 ，则比较3次查找成功的节点数为 ，则比较4次查找成功的节点数为 ，则比较5次查找成功的节点数为 ，平均查找长度为 。
（8）对于长度为n的线性表，若进行顺序查找，则时间复杂度为 ；若采用对分法查找，则时间复杂度为 ；若采用分块查找（假设总块数和每块长度均接近n1/2），则时间复杂度为 。
3．问答题
（1）叙述顺序查找、对分查找和分块查找3种方法的优缺点。
（2）有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99}，当采用对分查找法查找关键字为82的元素时，进行多少次比较后查找成功？
（3）试问在n个数据中，用顺序查找法查找某一个数据（假设这个数据是存在的）的平均时间是多少？
（4）假设哈希函数h(x)等于第一个英文字母顺序减1，所以A～Z相当于0～25。现有下列几个标识符，依次为GA，DA，B，G，L，A2，A3，A4及E，请利用上述哈希函数将它们置于哈希表，溢出时（Overflow）请分别利用线性探测和链接表进行处理（假设此处的哈希表格的槽（Slot）只有1个）。
4．上机操作题
（1）设二叉树用二叉链表表示，且每个节点的键值互不相同，请编写判断该二叉树是否为二叉排序树的非递归算法。
（2）设二叉排序树用二叉链表表示，请编写一个非递归算法，实现从大到小输出所有不小于x的节点的键值。
（3）设散列表HT[m]，用链地址法处理冲突，请编写一个算法，实现不用公式计算查找成功和查找失败的平均查找长度。