第8章 查找要点：
1、各种查找表元素如何组织；
2、各种查找方法的特征；
3、查找算法。
练习：
一、填空题
1、假定在有20个元素的有序表上进行二分查找，则比较一次查找成功的元素个数为,比较两次查找成功的元素个数为,比较三次查找成功的元素个数为,比较四次查找成功的元素个数为,比较五次查找成功的元素个数为,平均查找长度为 。
2、在索引查找中，首先查找,然后再查找相应的 。
3、在一个10阶的B-树上，根结点中所含的关键字数目最多允许为 个，最少允许为 个。
4、一棵深度为h的B-树上，若根结点为第一层，则任一叶子结点所处的层数为,当向该B-树插入一个新关键字时，为检索插入位置需读取 个结点。
参考解答：
1,1 2 4 8 5 3.7
2、索引表 子表
3、9 1
4、h,h（若不包含叶子结点层则为h-1）
二、选择题
1、采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为（ ）。
A）n B）n/2 C）(n+1)/2 D）(n-1)/2
2、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素，检索成功的比较次数为（ ）。
A）1 B）2 C）3 D）4
3、在一个3阶的B-树上，每个结点包含的子树相同，最多为 个，最少为 个。
A）1 B）2 C）3 D）4
参考解答：1、C 2、B 3、C B
三、应用题
1、习题8.12
（1）ASL = (1*1+2*2+3*3+4*3+5*2+6*1)/12 = 42/12 = 3.5
（2）ASL = (1*1+2*2+3*4+4*5)/12 = 37/12 = 3.1
2、写出二分查找的递归算法。
int Bisearch(int a[],int base,int top,int key)
{ if(base>top)return(-1);
int mid=(base+top)/2;
if(a[mid]==key)return(mid);
else{
if(a[mid]>key)return(Bisearch(a,base,mid-1,key);
else return(Bisearch(a,mid+1,top,key);
}
}
3、试设计一个算法，求出指定结点在给定的二叉排序树中的层次。
int level(BiTree t,KeyType Key)
{ int i=0;
while(t)
{i++;
if(t->data.key==key)break;
else t=t->data.key>key?t->lchild:t->rchild;
}
return i;
}
4、习题8.2解答：
ASL = (1*1+2*2+3*4+4*3)/10 = 2.9
5、习题8.4解答：
（1）3阶B-树中每一个结点中最少棵子树，－1个元素，最多3棵子树，2个元素；
（2）元素的插入总是从叶子结点的上一层结点中操作。首先从根结点开始，找到应当插入的结点；如果插入后结点中的元素个数>2，则结点分裂，且将中间的元素提升到其双亲结点；若双亲结点中的元素个数>2，则分裂、提升……。B-树总是平衡的
……
6、习题8.5解答：H(k) = (3k)%11 22,41,53,46,30,13,01,67
0
1
2
3
4
5
6
7
8
9
10
22
41
30
01
53
46
39
67
30
01
39
67
ASLsucc = (1*4 + 2*3 + 6*1)/8 = 16/8 = 2
ASLunsucc = (1*3 +2*2 + 3 + 4 + 5 + 6 + 7 + 8)/11 = 42/11 = 3.8
7、习题8.13解答,9个叶子结点的3阶B-树至少有4个非叶子结点，10个叶子结点则至少有7个非叶子结点。