試題五（15分）
閱讀下列說明、圖和C代碼，將應填入 （n） 處的字句寫在答題紙的對應欄內。
【說明5-1】
B樹是一種多叉平衡查找樹。一棵m階的B樹，或為空樹，或為滿足下列特性的m叉樹：
①樹中每個結點至多有m棵子樹；
②若根結點不是葉子結點，則它至少有兩棵子樹：
③除根之外的所有非葉子結點至少有[m/2]棵子樹；
④所有的非葉子結點中包含下列數(shù)據(jù)信息
（n，A₀，K₁，A₁，K₂，A₂，…，K₁₁，A₁₁）
其中：K（i＝1，2，……，n）為關鍵字，且K_j<K_i+1（i=1，2，…，n-l）；A_i（i=0，1，…，n）為指向子樹根結點的指針，且指針A_i-1所指子樹中所有結點的關鍵字均小于K_i，A_i+1所指子樹中所有結點的關鍵字均大于K_i，n為結點中關鍵字的數(shù)目。
⑤所有的葉子結點都出現(xiàn)在同—層次上，并且不帶信息（可以看作是外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指針為空）。
例如，一棵4階B樹如圖5－1所示（結點中關鍵字的數(shù)目省略）。
 
　 圖5－1 4階B樹示例
B樹的階M、bool類型、關鍵字類型及B樹結點的定義如下：
#define M 4/*B樹的階*/
typedef enum {FALSE = 0，TRUE = 1} bool;
typedef int ElemKeyType;
typedef structBTreeNode{
　int numkeys;/*結點中關鍵字的數(shù)目*/
　structBTreeNode*parent;/*指向父結點的指針，樹根的父結點指針為空*/
　structBTreeNode*A[M]; /*指向子樹結點的指針數(shù)組*/
　ElemKeyType K[M];/*存儲關鍵字的數(shù)組，K[0]閑置不用*/
}BTreeNode;

函數(shù)SearchBtree（BTreeNode* root, ElemKeyType akey, BTreeNode **ptr）的功能是：在給定的一棵M階B樹中查找關鍵字akey所在結點，若找到則返回TRUE，否則返回FALSE。其中，root是指向該M階B樹根結點的指針，參數(shù)ptr返回akey所在結點的指針，若akey不在該B樹中，則ptr返回查找失敗時空指針所在結點的指針。例如，在圖5－1所示的4階B樹中查找關鍵字okey時，ptr返回指向結點e的指針。
注：在結點中查找關鍵字akey時采用二分法。
【函數(shù)5-1】
bool SearchBtree（BTreeNode* root, ElemKeyType akey, BTreeNode **ptr）
{
intlw, hik mid；
BTreeNode *p = root;
*ptr = 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樹中插入一個關鍵字時，首先在最接近外部結點的某個非葉子結點中增加—個關鍵字，若該結點中關鍵字的個數(shù)不超過M-1，則完成插入；否則，要進行結點的“分裂”處理。所謂“分裂”，就是把結點中處于中間位置上的關鍵字取出來并插入其父結點中，然后以該關鍵字為分界線，把原結點分成兩個結點?！胺至选边^程可能會一直持續(xù)到樹根，若樹根結點也需要分裂，則整棵樹的高度增1。
例如，在圖5-1所示的B樹中插入關鍵字25時，需將其插入結點e中，由于e中已經(jīng)有3個關鍵字，因此將關鍵字24插入結點e父結點b，并以24為分界線將結點e分裂為e1和e2兩個結點，結果如圖5-1所示。
　
　圖5-2 在圖5-1所示的4階B樹中插入關鍵字25后的B樹
函數(shù)Isgrowing（BTreeNode* root，ElemKeyType akey）的功能是：判斷在給定的M階B樹中插入關鍵字akey后，該B樹的高度是否增加，若增加則返回TRUE，否則返回FALSE。其中，root是指向該M階B樹根結點的指針。
在函數(shù)Isgrowing中，首先調用函數(shù)SearchBtree（即函數(shù)5－l）查找關鍵字akey是否在給定的M階B樹中，若在則返回FALSE（表明無需插入關鍵字akey，樹的高度不會增加）；否則，通過判斷結點中關鍵字的數(shù)目考察插入關鍵字akey后該B樹的高度是否增加。
【函數(shù)5-2】
bool Isgrowing（BTreeNode* root， ElenlKeyType akey）
{ BTreeNode *t， *f；
　if (!SearchBtree(（4））){
t = f;
while （ （5） ）{
t = t -> parent;
}
if（!t）
return TRUE；
　}
　return FALSE;
}

[答案討論]

[1]  [2]  [3]  [4]  [5]  [6]