阅读下列说明、图和C代码。[说明5－1]B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列

Question

阅读下列说明、图和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) )

Answer 1

正确答案：(1)p-＞numkeys；或其等价形式 (2)p-＞K[mid]＞akey或其等价形式 (3)p-＞A[hi]或p-＞A[1w-1]或其等价形式 (4)rootakey&f (5)t&&t-＞numkeys==M-1或其等价形式
(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)处应填入“akeyp-＞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”。