アルゴリズムとプログラミング
基本情報技術者試験｜AVL木などの平衡2分探索木を用いる主な目的
AVL木などの平衡2分探索木を用いる主な目的として最も適切なものはどれか。
アノードを連結するポインタを完全に廃止し全要素を連続したメモリ領域に詰めて格納することでメモリ使用量を大きく削減すること
イ要素を一切並べ替えず到着順に末尾へ追加し、挿入を必ずO(1)で完了させること
ウ同じ値の重複登録を物理的に禁止し、集合演算の和や積を高速化すること
エ挿入や削除のたびに木の高さの偏りを抑え、探索を常にO(log n)に近く保つこと
正解
エ．挿入や削除のたびに木の高さの偏りを抑え、探索を常にO(log n)に近く保つこと
AVL木は各ノードで左右部分木の高さの差を一定以下に保つよう回転で再平衡する。これにより木が一方向に偏って高さがnに近づくのを防ぎ、探索・挿入・削除をO(log n)に保てるため正しい。
?選択肢ごとの解説
ア ×ポインタを廃止し連続領域に格納するのは配列の発想であり、ノードをポインタでつなぐ木構造の説明ではない。平衡化の目的とも無関係である。
イ ×並べ替えず末尾へ追加して挿入O(1)にするのはスタックやキューの挙動であり、順序を保ちながら平衡を維持するAVL木の目的とは異なる。
ウ ×重複禁止と集合演算高速化は集合データ型の目的に近く、AVL木が高さの偏りを抑えて探索効率を保つという本来の目的とは別である。
エ ○AVL木は各ノードで左右部分木の高さの差を一定以下に保つよう回転で再平衡する。これにより木が一方向に偏って高さがnに近づくのを防ぎ、探索・挿入・削除をO(log n)に保てるため正しい。
アルゴリズムとプログラミングの他の問題
データベースの索引に用いられるB+木の、B木と比べた特徴として最も適切なものはどれか。ハッシュ表の衝突処理におけるチェイン法(連鎖法)の説明として最も適切なものはどれか。要素数nの単方向連結リストにおいて、先頭ノードへのポインタが分かっているとき、リストの先頭に新しい要素を1個挿入する処理の計…平衡が保たれた2分探索木に約100万個の要素を格納したとき、根から葉までの高さ(段数)はおよそどの程度になるか。なおlog2…スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくらか。次のデータ構造で目的の値を1個探索するときの平均計算量を比べる。最も速い(オーダが小さい)ものはどれか。ただし表引き方式は衝…単純選択ソートで要素数nの配列を昇順に整列するとき、要素の比較回数は最悪・平均ともにおよそどれで表されるか。挿入ソートの計算量について最も適切に述べたものはどれか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0126