第8章查找 要点: 1、各种查找表元素如何组织; 2、各种查找方法的特征 查找算法。 练习 、填空题 1、假定在有20个元素的有序表上进行二分查找,则比较一次查找成功的元素个数为 较两次查找成功的元素个数为 比较三次查找成功的元素个数为 比较四次查找成 功的元素个数为 比较五次查找成功的元素个数为 平均查找长度 为 2、在索引查找中,首先查找 ,然后再查找相应的 3、在一个10阶的B树上,根结点中所含的关键字数目最多允许为 个,最少允许为 个。 4、一棵深度为h的B-树上,若根结点为第一层,则任一叶子结点所处的层数为 当向该 B-树插入一个新关键字时,为检索插入位置需读取 个结点 参考解答 1、124853.7 2、索引表 子表 4、h,h(若不包含叶子结点层则为h-1) 、选择题 1、采用顺序检索的方法检索长度为n的线性表,则检索每个元素的平均比较次数为(), 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 3、CB 三、应用题 1、习题8.12 (1)ASL=(1*1+2*2+3*3+4*31+5*2+6*1)/12=4/12(4px July (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) I if(base>top)return(-1 int mid=(base+top)/2 if(a [mid]=key)return(mid) if(a[mid]>key)return(Bisearch(a, base, mid-1, key)第 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);