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

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