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

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

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

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

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2023/8/21）

試題五
閱讀下列說(shuō)明、圖和C代碼。
[說(shuō)明5-1]
B樹是一種多叉平衡查找樹。一棵m階的B樹，或?yàn)榭諛洌驗(yàn)闈M足下列特性的m叉樹：
①樹中每個(gè)結(jié)點(diǎn)最多有m棵子樹；
②若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則它至少有兩棵子樹；
⑧除根之外的所有非葉子結(jié)點(diǎn)至少有[m/2]棵子樹；
④所有的非葉子結(jié)點(diǎn)中包含下列數(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é)點(diǎn)的指針，且指針Ai-1，所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，Ai+1，所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于Ki，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樹如下圖所示(結(jié)點(diǎn)中關(guān)鍵字的數(shù)目省略)。

B樹的階M、bool類型、關(guān)鍵字類型及B樹結(jié)點(diǎn)的定義如下：
#define  M  4                                    /*B樹的階*/
typedef enum {FALSE=0,TRUE=1}bool；
typedef int ElemKeyType；
typedef struct BTreeNode {
int numkeys；                                 /*結(jié)點(diǎn)中關(guān)鍵字的數(shù)日*/
struct BTreeNode*parent；                    /*指向父結(jié)點(diǎn)的指針，樹根的父結(jié)點(diǎn)指針為空*/
struct BTreeNode *A[M]；                    /*指向子樹結(jié)點(diǎn)的指針數(shù)組*/
ElemKeyType  K[M]；                          /*存儲(chǔ)關(guān)鍵字的數(shù)組，K[0]閑置不用*/
}BTreeNode；
函數(shù)SearchBtree(BTreeNode*root，ElemKcyTypeakey,BTreeNode：*pb)的功能是：在給定的一棵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返回查找失敗時(shí)空指針?biāo)诮Y(jié)點(diǎn)的指針。例如，在上圖所示的4階B樹中查找關(guān)鍵字25時(shí)，ptr返回指向結(jié)點(diǎn)e的指針。
注；在結(jié)點(diǎn)中查找關(guān)鍵字akey時(shí)采用二分法。
[函數(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;
}
[說(shuō)明5-2]
在M階B樹中插入一個(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ù)到樹根，若樹根結(jié)點(diǎn)也需要分裂，則整棵樹的高度增加1。
例如，在上圖所示的B樹中插入關(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é)果如下圖所示。



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