アルゴリズムとプログラミング
基本情報技術者試験｜データベースの索引に用いられるB+木の、B木と比べた特徴
データベースの索引に用いられるB+木の、B木と比べた特徴として最も適切なものはどれか。
ア各ノードが必ず2個の子だけを持ち、木の高さが2分探索木と同一になる
イキーを葉ノードにだけ格納せず内部ノードのみに置き、葉には何も保持しない
ウ全ての実データ(キー)を葉ノードに格納し、葉同士をポインタで連結して範囲検索を効率化する
エ木を用いず配列の二分探索で代替するため、挿入・削除のたびに全体を並べ替える
正解
ウ．全ての実データ(キー)を葉ノードに格納し、葉同士をポインタで連結して範囲検索を効率化する
B+木は内部ノードを探索の道標とし、実データ(キー)を全て葉ノードに置く。さらに葉同士を連結リストでつなぐため、ある範囲のキーを葉をたどって連続取得でき範囲検索に強く、正しい。
?選択肢ごとの解説
ア ×各ノードが2個の子に限られ高さが2分探索木と同じになるのは2分木の話であり、B+木は1ノードが多数の子を持つ多分岐木でディスクアクセスを減らす。
イ ×内部ノードのみにキーを置き葉に何も持たないのは説明が逆で、B+木は実データを葉に集約する。内部はキーの分岐情報のみを持つ。
ウ ○B+木は内部ノードを探索の道標とし、実データ(キー)を全て葉ノードに置く。さらに葉同士を連結リストでつなぐため、ある範囲のキーを葉をたどって連続取得でき範囲検索に強く、正しい。
エ ×木を使わず配列の二分探索で代替するのは別手法であり、挿入削除のたびに全体を並べ替える非効率も伴うためB+木の特徴ではない。
アルゴリズムとプログラミングの他の問題
ハッシュ表の衝突処理におけるチェイン法(連鎖法)の説明として最も適切なものはどれか。要素数nの単方向連結リストにおいて、先頭ノードへのポインタが分かっているとき、リストの先頭に新しい要素を1個挿入する処理の計…平衡が保たれた2分探索木に約100万個の要素を格納したとき、根から葉までの高さ(段数)はおよそどの程度になるか。なおlog2…スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくらか。次のデータ構造で目的の値を1個探索するときの平均計算量を比べる。最も速い(オーダが小さい)ものはどれか。ただし表引き方式は衝…単純選択ソートで要素数nの配列を昇順に整列するとき、要素の比較回数は最悪・平均ともにおよそどれで表されるか。挿入ソートの計算量について最も適切に述べたものはどれか。シェルソートの基本的な考え方を最も適切に説明したものはどれか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0127