第八章   查找
一．填空题
1．采用二分法进行查找的查找表，应选择____________________方式的存储结构
2．设在有序表A[0……9]中进行二分查找，比较一次查找成功的结点数为_____，比较二次查找成功的结点数为______，比较三次查找成功的结点数为_____，比较四次查找成功的结点数为_____，比较五次查找成功的结点数为_____，平均查找长度为______。
二．选择题
1．对线性表进行二分查找时，要求线性表必须（　）
A．键值有序的链接表  　　　　　　B．键值有序的顺序表
C．链接表但键值不一定有序  　　　D．顺序但键值不一定有序
2．有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分查找法查找键值为84的结点时，经（　）比较后查找成功。
A．2  　　　　 B． 3   　　　　C．4 　　　　 D．12
3．顺序检索一个具有n个数据元素的线性表，其时间复杂度为（  ），二分检索一个具有n个数据元素的线性表，其时间复杂度为（　）
A． O(n)   　　B．O(log2n)  　　C．O(n2)  　　 D．O(nlog2n)
4．在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是(　)。
A. -11          B. -22           C. 12           D. 01
5．设散列表长度为m，散列函数为H（key）=key%p，为了减少发生冲突的可能性，p应取（　）
A．小于m的最大奇数   　　　 　 B．小于m的最大素数
C．小于m的最大偶数   　　　　　D．小于m的最大合数
6．若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为(　)。
A. 4             B. 8              C. 12             D. 13
三．解答题
1．给定表{19,14,22,01,66,21,83,27,56,13,10}
①试按元素在表中的顺序构造一棵二叉排序树；
②判断该二叉排序树是否平衡，若不平衡，调整其为平衡二叉树。
2．设一组关键字为（7，15，20，31，48，53，64，76，82，99），Hash函数H（key）= key  % 11，Hash表表长m=11，用线性探测法解决冲突，试构造Hash表，并分别计算查找成功和查找失败情况下的平均查找长度。
 
参 考 答 案
第八章   查找
一．填空题
1．顺序
2．1  2  4  3  0   （1+2*2+3*4+4*3）/10=2.9
二．选择题
1． B
2． C
3． A 　　B
4． A
5． B
6． C
三．解答题
1．
①
②该二叉排不平衡，调整后的平衡二叉树为：
2．略