第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);
el se return (Bisearch(a, mid+1, top, key 3、试设计一个算法,求出指定结点在给定的二叉排序树中的层次 int level(Bitree t, Key Type Key) while(t) else t=t->data key key?t->lchild: t->rchild 4、习题8.2解答: ASL=(1*1+2*2+3米4+4*3)/10=2.9 5、习题8.4解答 (1)3阶B-树中每一个结点中最少3棵子树,[31-1个元素,最多3棵子树,2个元素 2 (2)元素的插入总是从叶子结点的上一层结点中操作。首先从根结点开始,找到应当插入的结点 如果插入后结点中的元素个数>2,则结点分裂,且将中间的元素提升到其双亲结点;若双亲结点中 的元素个数>2,则分裂、提升……。B-树总是平衡的 2030 6、习题8.5解答:H(k)=(3k)%1122,41,53,46,30,13,01,67 0 9 (1*4+2*3+6*1)/8=16/8=2 ns=(1*3+2*2+3+4+5+6+7+8)/11=42/11=3.8 7、习题8.13解答:9个叶子结点的3阶B-树至少有4个非叶子结点,10个叶子结点则至少有7 个非叶子结点
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-树中每一个结点中最少 2 3 棵子树， 2 3 －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 个非叶子结点。 20 20 30 20 50 30 20 50 52 30 20 50 30 52 60
c d e f a b g h c d e f a g b h i