| 第１種情報処理技術者試験 |
1997年度 ＝ 平成9年度 |
午前 |
問10 |
B木に関する記述のうち、正しいものはどれか。
ア B木内の各要素は、追加された順に格納されている。
イ 根からそれぞれの葉までのレベル（深さ）は、要素のキー値に偏りがあると、一定にはならない。
ウ 要素の削除に伴って、部分木の要素数が一定値を下回るときは、隣の葉や節を含めて再構成される。
エ 要素は、必ず新しい葉に対して追加される。
ウ
B木は、主に外部記憶域上での探索に適した木構造のデータ構造であり、次の条件を満たすものを、n階のＢ木と呼びます。
(1) 根は、葉であるか、もしくは2ないしn個の子をもつ
(2) 根、葉以外のノードは、［m/2］ないしm個の子をもつ
※[m/2]は、切り上げを表す
(3) 根からすべての葉までの経路の長さが等しい
ア 各要素は、キー値の順に格納されています。
イ 根からそれぞれの葉までのレベル（深さ）は、一定に保たれます。
ウ 要素の削除に伴って、部分木の要素数が一定値を下回るときは、隣の葉や節を含めて再構成されます。
エ 要素は、挿入後にキー値順となるような、最下位の節に追加される。
