アルゴリズムとプログラミング
基本情報技術者試験｜2分探索木(BST)が満たすべき構造的性質
2分探索木(BST)が満たすべき構造的性質として最も適切なものはどれか。
ア任意のノードについて、左部分木の全ての値がそのノードより小さく、右部分木の全ての値が大きい
イ任意のノードについて、その値が左右どちらの子の値以上でもあり、結果として根に格納された値が木全体の最大値となる
ウ全ての葉が同じ深さに並び、根から葉までの経路長が全て等しくなっている
エ各ノードが最大3個の子を持ち、子の個数に応じてキーを内部に保持する
正解
ア．任意のノードについて、左部分木の全ての値がそのノードより小さく、右部分木の全ての値が大きい
2分探索木は各ノードを基準に左部分木の全値が小さく、右部分木の全値が大きいという順序条件を満たす。これにより根から比較しながら片側へ進む二分探索が可能になり、正しい。
?選択肢ごとの解説
ア ○2分探索木は各ノードを基準に左部分木の全値が小さく、右部分木の全値が大きいという順序条件を満たす。これにより根から比較しながら片側へ進む二分探索が可能になり、正しい。
イ ×ノードの値が左右の子以上で根が最大値になるのはヒープ(最大ヒープ)の性質であり、左右の大小関係を定める2分探索木とは異なる。
ウ ×全ての葉が同じ深さで経路長が等しいのは完全2分木や平衡木が近づける形であり、順序関係を定める2分探索木の定義そのものではない。
エ ×各ノードが複数の子と複数キーを持つのは多分木やB木の特徴であり、子が最大2個の2分探索木とは構造が異なる。
アルゴリズムとプログラミングの他の問題
AVL木などの平衡2分探索木を用いる主な目的として最も適切なものはどれか。データベースの索引に用いられるB+木の、B木と比べた特徴として最も適切なものはどれか。ハッシュ表の衝突処理におけるチェイン法(連鎖法)の説明として最も適切なものはどれか。要素数nの単方向連結リストにおいて、先頭ノードへのポインタが分かっているとき、リストの先頭に新しい要素を1個挿入する処理の計…平衡が保たれた2分探索木に約100万個の要素を格納したとき、根から葉までの高さ(段数)はおよそどの程度になるか。なおlog2…スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくらか。次のデータ構造で目的の値を1個探索するときの平均計算量を比べる。最も速い(オーダが小さい)ものはどれか。ただし表引き方式は衝…単純選択ソートで要素数nの配列を昇順に整列するとき、要素の比較回数は最悪・平均ともにおよそどれで表されるか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0125