平成１９年度 技術士第一次試験問題【専門科目】
Ⅳ－６
1つのレコードにキーが2個、ポインタが3個交互に格納できるＢ木 (balanced tree, B-tree) が下図のようになっているとき、キーの値3を追加した場合のＢ木の構成図として最も適切なものは①～⑤のうちどれか。ここで、キーの値は数値型とする。
正解
①
解説
Ｂ木の構造のポイントは、
(1) キーがポインタとポインタの間に入っていること。言い換えると、1つのレコードから出ている枝の数はキーの数より1つ多いということである。
(2) キー i と キー i+1 の間にあるポインタから出ている枝にあるキーj は キーi より大きく、キー i+1 より小さいこと。
これらを踏まえる。
① 正しい。
② キー6の右横から矢印が出ていない。
③ キー4があるレコードと、キー1、キー2があるレコードの間で分割が行われるが、キー4があるレコードと、キー5、キー6があるレコードの間で分割が行われており、誤り。
④ キー6とキー10の間から枝が出ていない。
⑤ キー3とキー4の間から枝が出ていない。
| Ⅳ－５ | 目次 | Ⅳ－７ |