試題五（15分）
閱讀下列說(shuō)明、圖和C代碼，將應(yīng)填入 （n） 處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明5-1】
B樹(shù)是一種多叉平衡查找樹(shù)。一棵m階的B樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M足下列特性的m叉樹(shù)：
①樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；
②若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則它至少有兩棵子樹(shù)：
③除根之外的所有非葉子結(jié)點(diǎn)至少有[m/2]棵子樹(shù)；
④所有的非葉子結(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）為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針A_i-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均小于K_i，A_i+1所指子樹(shù)中所有結(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樹(shù)如圖5－1所示（結(jié)點(diǎn)中關(guān)鍵字的數(shù)目省略）。
 
　 圖5－1 4階B樹(shù)示例
B樹(shù)的階M、bool類型、關(guān)鍵字類型及B樹(shù)結(jié)點(diǎn)的定義如下：
#define M 4/*B樹(shù)的階*/
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)的指針，樹(shù)根的父結(jié)點(diǎn)指針為空*/
　structBTreeNode*A[M]; /*指向子樹(shù)結(jié)點(diǎn)的指針數(shù)組*/
　ElemKeyType K[M];/*存儲(chǔ)關(guān)鍵字的數(shù)組，K[0]閑置不用*/
}BTreeNode;

函數(shù)SearchBtree（BTreeNode* root, ElemKeyType akey, BTreeNode **ptr）的功能是：在給定的一棵M階B樹(shù)中查找關(guān)鍵字akey所在結(jié)點(diǎn)，若找到則返回TRUE，否則返回FALSE。其中，root是指向該M階B樹(shù)根結(jié)點(diǎn)的指針，參數(shù)ptr返回akey所在結(jié)點(diǎn)的指針，若akey不在該B樹(shù)中，則ptr返回查找失敗時(shí)空指針?biāo)诮Y(jié)點(diǎn)的指針。例如，在圖5－1所示的4階B樹(shù)中查找關(guān)鍵字okey時(shí)，ptr返回指向結(jié)點(diǎn)e的指針。
注：在結(jié)點(diǎn)中查找關(guān)鍵字akey時(shí)采用二分法。
【函數(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;
}

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