軟件設(shè)計師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計師案例分析每日一練試題（2024/6/23）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/6/23

點擊查看：更多軟件設(shè)計師習(xí)題與指導(dǎo)

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2024/6/23）

試題五
閱讀下列說明、圖和C代碼。
[說明5-1]
B樹是一種多叉平衡查找樹。一棵m階的B樹，或為空樹，或為滿足下列特性的m叉樹：
①樹中每個結(jié)點最多有m棵子樹；
②若根結(jié)點不是葉子結(jié)點，則它至少有兩棵子樹；
⑧除根之外的所有非葉子結(jié)點至少有[m/2]棵子樹；
④所有的非葉子結(jié)點中包含下列數(shù)據(jù)信息：
(n，A0，K1，A1，K2，A2，  …，Kn，An)其中：Ki(i=1，2，…，n)為關(guān)鍵字，且Ki＜Ki+1(i=1，2，…，n-1)；Ai(i=0，1，…，n)為指向子樹根結(jié)點的指針，且指針Ai-1，所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki，Ai+1，所指子樹中所有結(jié)點的關(guān)鍵字均大于Ki，n為結(jié)點中關(guān)鍵字的數(shù)目。
⑤所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息(可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空)。
例如，一棵4階B樹如下圖所示(結(jié)點中關(guān)鍵字的數(shù)目省略)。

B樹的階M、bool類型、關(guān)鍵字類型及B樹結(jié)點的定義如下：
#define  M  4                                    /*B樹的階*/
typedef enum {FALSE=0,TRUE=1}bool；
typedef int ElemKeyType；
typedef struct BTreeNode {
int numkeys；                                 /*結(jié)點中關(guān)鍵字的數(shù)日*/
struct BTreeNode*parent；                    /*指向父結(jié)點的指針，樹根的父結(jié)點指針為空*/
struct BTreeNode *A[M]；                    /*指向子樹結(jié)點的指針數(shù)組*/
ElemKeyType  K[M]；                          /*存儲關(guān)鍵字的數(shù)組，K[0]閑置不用*/
}BTreeNode；
函數(shù)SearchBtree(BTreeNode*root，ElemKcyTypeakey,BTreeNode：*pb)的功能是：在給定的一棵M階B樹中查找關(guān)鍵字akey所在結(jié)點，若找到則返回TRUE，否則返回 FALSE。其中，root是指向該M階B樹根結(jié)點的指針，參數(shù)ptr返回akey所在結(jié)點的指針，若akey不在該B樹中，則ptr返回查找失敗時空指針?biāo)诮Y(jié)點的指針。例如，在上圖所示的4階B樹中查找關(guān)鍵字25時，ptr返回指向結(jié)點e的指針。
注；在結(jié)點中查找關(guān)鍵字akey時采用二分法。
[函數(shù)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樹中插入一個關(guān)鍵字時，首先在最接近外部結(jié)點的某個非葉子結(jié)點中增加一個關(guān)鍵字，若該結(jié)點中關(guān)鍵字的個數(shù)不超過M-1，則完成插入；否則，要進(jìn)行結(jié)點的“分裂”處理。所謂“分裂”，就是把結(jié)點中處于中間位置上的關(guān)鍵字取出來并插入其父結(jié)點中，然后以該關(guān)鍵字為分界線，把原結(jié)點分成兩個結(jié)點?！胺至选边^程可能會一直持續(xù)到樹根，若樹根結(jié)點也需要分裂，則整棵樹的高度增加1。
例如，在上圖所示的B樹中插入關(guān)鍵字25時，需將其插入結(jié)點e中。由于e中已經(jīng)有3個關(guān)鍵字，因此將關(guān)鍵字24插入結(jié)點e的父結(jié)點b，并以24為分界線將結(jié)點e分裂為e1和e2兩個結(jié)點，結(jié)果如下圖所示。



函數(shù)Isgrowing(BTreeNode*root，ElemKeyTypeakey)的功能是：判斷在給定的M階B樹中插入關(guān)鍵字akey后，該B樹的高度是否增加，若增加則返回TRUE，否則返回FALSE。其中，root是指向該M階B樹根結(jié)點的指針。
在函數(shù)Isgrwing中，首先調(diào)用函數(shù)SearchBtree(即函數(shù)5-1)查找關(guān)鍵字akey是否在給定的M階B樹中，若在，則返回FALSE(表明無需插入關(guān)鍵字akey，樹的高度不會增加)；否則，通過判斷結(jié)點中關(guān)鍵字的數(shù)目考查插入關(guān)鍵字akey后該B樹的高度是否增加。


[函數(shù)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;
}