2. 计算机
  3. 阅读下列说明、图和C代码。 [说明5-1] B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树： ①树中每个结点最多有m棵子树； ②若根结点不是叶子结点，则它至少有两棵子树； ⑧除根之外的所有非叶子结点至少有

阅读下列说明、图和C代码。 [说明5-1] B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树： ①树中每个结点最多有m棵子树； ②若根结点不是叶子结点，则它至少有两棵子树； ⑧除根之外的所有非叶子结点至少有

admin2008-02-15  31
问题 阅读下列说明、图和C代码。
[说明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树如下图所示(结点中关键字的数目省略)。
   
   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，ElemKcyTypeakey,BTreeNode：*pb)的功能是：在给定的一棵M阶B树中查找关键字akey所在结点，若找到则返回TRUE，否则返回 FALSE。其中，root是指向该M阶B树根结点的指针，参数ptr返回akey所在结点的指针，若akey不在该B树中，则ptr返回查找失败时空指针所在结点的指针。例如，在上图所示的4阶B树中查找关键字25时，ptr返回指向结点e的指针。
   注；在结点中查找关键字akey时采用二分法。
[函数5-1]
     bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)
    {
         int  lw, hi, mid;
         BTreeNode*p = root;
         *ptr = NULL;
         while ( p ) {
             1w = 1;   hi=(1);
             while (1w ＜= hi) {
                 mid = (1w + hi)/2;
                 if (p -＞ K[mid] == akey) {
                    *ptr = p;
                   return TRUE;
             }
                 else
                   if ((2))
                      hi=mid - 1;
                   else
                      1w = mid + 1;
          }
             *ptr = p;
             p = (3);
       }
         return FALSE;
    }
[说明5-2]
   在M阶B树中插入一个关键字时，首先在最接近外部结点的某个非叶子结点中增加一个关键字，若该结点中关键字的个数不超过M-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来并插入其父结点中，然后以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根，若树根结点也需要分裂，则整棵树的高度增加1。
   例如，在上图所示的B树中插入关键字25时，需将其插入结点e中。由于e中已经有3个关键字，因此将关键字24插入结点e的父结点b，并以24为分界线将结点e分裂为e1和e2两个结点，结果如下图所示。
   
   函数Isgrowing(BTreeNode*root，ElemKeyTypeakey)的功能是：判断在给定的M阶B树中插入关键字akey后，该B树的高度是否增加，若增加则返回TRUE，否则返回FALSE。其中，root是指向该M阶B树根结点的指针。
   在函数Isgrwing中，首先调用函数SearchBtree(即函数5-1)查找关键字akey是否在给定的M阶B树中，若在，则返回FALSE(表明无需插入关键字akey，树的高度不会增加)；否则，通过判断结点中关键字的数目考查插入关键字akey后该B树的高度是否增加。
[函数5-2]
    bool Isgrowing(BTreeNode* root, ElernKeyType akey)
   {   BTreeNode *t, *f;
       if( !SearchBtree((4) ) ) {
            t=f;
            while ((5)) {
                t=t -＞ parent;
        }
        if( !t )
          return TRUE;
     }
      return FALSE;
   }
选项
答案(1)p-＞numkeys；或其等价形式 (2)p-＞K[mid]＞akey，或其等价形式 (3)p-＞A[hi]，或p-＞A[1w-1]，或其等价形式 (4)root,akey,&f (5)t&&t-＞numkeys==M-1，或其等价形式
解析 本题考查C程序设计。
   B树是一种多叉平衡查找树，由B树的定义可知，在B树上进行查找的过程是：首先在根结点所包含的关键字中查找给定的关键字，若找到则成功返回：否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败(指针为空)为止。树的内部结点中关键字存储在数组中并按照递增顺序排列，因此可以用二分法查找某个关键字是否在指定的结点中。
   二分法查找元素的过程是：首先令待查找的元素与查找表中间位置上的元素进行比较，若相等，则查找成功，否则，根据待查元素与表中间位置元素的大小关系，下一步到查找表的前半区间或后半区间继续进行二分查找。如果在确定的任何一个子区间都找不到指定的元素，则确定查找失败。若查找区间用一对下标1w和hi确定，则1w≤hi表示有效的查找区间，查找失败时所确定的查找区间为1w＞hi。
    例如，上图中的结点c包含了关键字60、70、80，那么在c结点中找不到元素65，由于65介于60和70之间，因此下一步必将进入h结点继续查找。
   每个结点中的关键字数目由BTreeNode中的numkeys域表示，结点中的查找表存储在数组K[]中，由于下标0未用，因此numkeys个关键字存储在K11)～K[numkeys]中。显然开始在p所指向的结点中进行查找时，确定查找表的下标为1和结点的numkeys域，因此函数5-1的空(1)处应填入“p-＞numkeys”。
   若用1w和hi指示出查找区间，则由于查找表元素的递增排列特性，当待查找的元素小于表中间位置的元素时，下一步应在前半区间查找，即查找区间的一对下标为1w、 mid-1，也就是说函数5-1的空(2)处应填入“akey＜p-＞K[mid]。
   如果在当前结点中找不到指定的关键字akey，则1w＞hi，由结点中的指针A[hi]或 A[1w-1]指示出下一层的子树结点，因此函数5-1的空(3)处应填入“p＞A[hi]”或“p-＞ A[1w-1]”。
   下面分析函数5-2的功能及运算过程。函数5-2用于判断在B树中插入一个关键字时，树的高度是否增加。若指定的关键字已经在B树的某结点中，就不需要插入该关键字，显然树也不会长高。
   实现函数调用时实参要向形参传递信息，C语言采取传值调用方式，根据实参向形参的值传递原则，函数4-2中的空(4)处应填入“root,akey,&f"。
   根据题目中给出的描述，在M阶B树中插入一个关键字时，首先在最接近外部结点的某个非叶子结点中增加一个关键字，若该结点中关键字的个数不超过M-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来并插入其父结点中，然后以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根，若树根结点也需要分裂，则整棵树的高度增加1。
   显然考查插入关键字akey后树的高度是否增加，只需沿其祖先结点关系一直考查直到树根为止，判断依据就是每个待考查的结点中目前已有的关键字个数，因此函数5-2中的空(5)处应填入“t&&t-＞numkeys==M-1”。
转载请注明原文地址:https://jikaoti.com/ti/ihi7FFFM
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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