2. 计算机
  3. 阅读下列说明、图和C代码，将应填入(n)处的字句写在对应栏内。 【说明5-1】 B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树： ①树中每个节点至多有m棵子树； ②若根节点不是叶子节点，则它至少有两棵子树；

阅读下列说明、图和C代码，将应填入(n)处的字句写在对应栏内。 【说明5-1】 B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树： ①树中每个节点至多有m棵子树； ②若根节点不是叶子节点，则它至少有两棵子树；

admin2009-05-15  43
问题 阅读下列说明、图和C代码，将应填入(n)处的字句写在对应栏内。
【说明5-1】
   B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：
   ①树中每个节点至多有m棵子树；
   ②若根节点不是叶子节点，则它至少有两棵子树；
   ③除根之外的所有非叶子节点至少有[m/2]棵子树；
   ④所有的非叶子节点中包含下列数据信息(n，A0，K1，A1，K2，A2，…，Kn，An)，其中：Ki(i=1，2，…，n)为关键字，且Ki＜Ki+1(i=1，2，…，n-1)，Ai(i=0，1，…，n)为指向子树根节点的指针，且指针Ai-1所指子树中所有节点的关键字均小于Ki，Ai+1所指子树中所有节点的关键字均大于Ki，n为节点中关键字的数目；
   ⑤所有的叶子节点都出现在同一层次上，并且不带信息(可以看成是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。
   例如，一棵4阶B树如图5-1所示(节点中关键字的数目省略)。
         
   B树的阶M、bool类型、关键字类型及B树节点的定义如下：
   #define  M  4                                  /*B树的阶*/
   typedef enum{FALSE=0,TRUE=1}bool;
   typedef int ElemKeyType;
   typedef struct BTreeNode{
         int numkeys;                             /*节点中关键字的数目*/
         struct BTreeNode *parent;                /*指向父节点的指针，树根的父节点指针为空*/
         struct BTreeNode *A[M];                  /*指向子树节点的指针数组*/
         ElemKeyType K[M];                        /*存储关键字的数组，K[0]闲置不用*/
   }BTreeNode；
   函数SearchBtree(BTreeNode* root，ElemKeyType akey，BTreeNode **ptr)的功能是：在给定的一棵M阶B树中查找关键字akey所在节点，若找到则返回TRUE，否则返回FALSE。其中， root是指向该M阶B树根节点的指针，参数ptr返回akey所在节点的指针，若akey不在该B树中，则ptr返回查找失败时空指针所在节点的指针。例如，在如图5-1所示的4阶B树中查找关键字25时，ptr返回指向节点e的指针。
   注：在节点中查找关键字akey时采用二分法。
   【函数5-1】
   bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)
   {
        int  lw,hi,mid;
        BTreeNode *p=root;
        *pb=NULL;
        while(p){
              lw=1;hi=(1);
              while(lw＜=hi){
                   mid=(lw+hi)/2;
                   if(p-＞K[mid]==akey){
                        *Ptr=p;
                        return TRUE;
                   }else if((2))
                         hi=mid-1;
                   else
                         lw=mid+1;
              }
              *ptr=p;
              p=(3);
        }
        return FALSE;
   }
   【说明5-2】
   在M阶B树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增1。
   例如，在如图5-1所示的B树中插入关键字25时，需将其插入节点e中，由于e中已经有3个关键字，因此将关键字24插入节点e的父节点b，并以24为分界线将节点e分裂为e1和e2两个节点，结果如图5-2所示。
         
   函数Isgrowing(BTreeNode* root，ElemKeyType akey)的功能是：判断在给定的M阶B树中插入关键字akey后，该B树的高度是否增加，若增加则返回TRUE，否则返回FALSE。其中， root是指向该M阶B树根节点的指针。
   在函数Isgrowing中，首先调用函数SearchBtree(即函数5-1)查找关键字akey是否在给定的M阶B树中，若在则返回FALSE(表明无须插入关键字akey，树的高度不会增加)；否则，通过判断节点中关键字的数目考察插入关键字akey后该B树的高度是否增加。
   【函数5-2】
   bool Isgrowing(BTreeNode* root,ElemKeyType akey)
   {
          BTreeNode *t,*f;
          if(!SearchBtree((4))){
                 t=f;
                 while((5)){
                       t=t-＞parent;
                 }
                 if(!t)
                       return TRUE;
          }
          return FALSE;
   }
选项
答案(1) p-＞numkeys (2) akey＜p-＞K[mid] (3) p-＞A[hi] (4) root，akey，&f (5) t && t-＞numkeys==M-1
解析 该题考查B树上的查找和插入操作，解题之前需要弄清楚B树的存储结构。
   函数5-1采用二分法查找，先在根节点查找待查关键字，若找到则成功返回；否则，确定待查关键字所可能在的子树继续查找，直到找到或到达叶节点(查找失败)。如何确定子树是该题的难点。
   根据二分法查找的思想，变量hi应该赋值为查找表中最后元素的下标，结合B树的存储结构，应该为p-＞numkeys，即查找表中的元素个数(因下标从1开始)。故空(1)应填p-＞numkeys。
   接着通过while循环进行查找，循环体中分3种情况分别处理：找到时，记录待查关键字所在节点的指针，并返回；否则，若空(2)条件成立，则将hi赋值为mid-1(即表示继续在前半段查找)，否则将1w赋值为mid+1(即表示继续在后半段查找)，结合二分法查找思想很容易得空(2)条件应该为akey＜p-＞K[mid]。故空(2)应填akey＜p-＞K[mid]。
   执行到空(3)处，结束了while循环，说明在当前节点处没找到待查关键字，需要继续在相应子树中查找，那么究竟应该在哪棵子树中继续查找呢?该空是比较难的一空，需要对题中 B树的存储结构有深刻的理解。显然该空该填p-＞A[下标]，关键就是下标如何确定。根据B树的存储结构(n，A0，K1，A1，K2，A2，…，Kn，An)，当hi、lw及mid相等时(while循环结束条件)，如果待查关键字较小，则应该在A[mid-1]中查找，而此时正好有语句“hi=mid-1”；若待查关键字较大，则应该在A[mid]中查找，亦即A[hi]。综合可得应在A[hi]中继续查找。故空(3)应填p-＞A[hi]。
   空(4)和空(5)相对比较简单。空(4)只要根据形参正确将实参传递即可。根据题意，此处显然是打算在B树root中查找关键字akey，再根据紧接的语句“t=f”可知第三个参数应该为&f。故空(4)应填“root，akey，&f”。
   根据分裂的说明，若当前节点的关键字个数为M-1个时，其子节点的分裂将导致该节点的分裂。因此不难得到空(5)应填“t&&t-＞numkeys==M-1”。注意别填成“t-＞numkeys== M-1”，此处t是一个指针，首先得保证t不为空才能进行访问。
转载请注明原文地址:https://kaotiyun.com/show/n5xZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)