スタックやキュー、ハッシュテーブル、木構造など、プログラミングの土台になるデータ構造は、名前を知っていても違いを説明しようとすると意外と迷うものです。このクイズでは、基本的な構造の特徴や計算量、使いどころといった考え方を10問で確認できます。学習の総復習にも、試験や面接の前の腕試しにも使えます。解説も読みながら、知識を確かなものにしていきましょう。
Q1 : グラフの幅優先探索（BFS）を実装する際に、次に訪問するノードを管理するために一般的に使われるデータ構造はどれですか。
幅優先探索は、開始ノードに近いものから順に訪問していくアルゴリズムです。訪問したノードの隣接ノードをキューの末尾に追加し、先頭から順に取り出して処理することで、開始点からの距離が短い順に探索できます。一方、深さ優先探索（DFS）はスタック（または再帰呼び出し）を用いる点が対照的です。BFSは重みなしグラフでの最短経路の探索にも利用されます。
Q2 : 根の深さを0としたとき、高さが3の二分木が持つことのできる最大のノード数はいくつですか。
二分木では深さdの階層に最大2のd乗個のノードが存在できます。高さ3の木は深さ0から3までの4つの階層を持つため、最大ノード数は1+2+4+8=15となります。一般に高さhの二分木の最大ノード数は2の(h+1)乗から1を引いた値です。逆に言えば、n個のノードを持つ完全二分木の高さはおよそlog2 nとなり、これが二分探索木やヒープの操作がO(log n)になる根拠です。
Q3 : 文字列の集合に対する接頭辞検索（例：「app」で始まる単語をすべて探す）に特に適したデータ構造はどれですか。
トライ木は、文字列を1文字ずつ辺に対応させて根から葉へ枝分かれさせる木構造で、共通する接頭辞を持つ単語が同じ経路を共有します。そのため、接頭辞に対応するノードまで文字数分だけたどれば、その下にぶら下がる単語をすべて列挙でき、検索時間は単語数ではなく接頭辞の長さに比例します。オートコンプリートや辞書検索などに広く活用されています。
Q4 : ブルームフィルタ（Bloom filter）の性質として正しいものはどれですか。
ブルームフィルタは、複数のハッシュ関数で得た位置のビット配列を1にすることで要素の所属を判定する、省メモリな確率的データ構造です。追加済みの要素は必ず関連するビットが1になっているため「含まれない」と判定されることはなく偽陰性は起こりません。一方、別の要素によって偶然ビットが1になっていると、未追加の要素を含まれると誤判定する偽陽性が起こりえます。
Q5 : ハッシュテーブルにおいて、ハッシュ値の衝突が少なく適切に設計されている場合の、キーによる検索の平均的な時間計算量はどれですか。
ハッシュテーブルはキーをハッシュ関数で配列の添字に変換して要素を格納するため、衝突が少なければ検索・挿入・削除の平均計算量はO(1)になります。ただし衝突が多発すると、チェイン法では同じ位置の連結リストを順にたどる必要があり、最悪の場合はO(n)まで悪化します。そのため、ハッシュ関数の選び方や負荷率の管理が性能を左右する重要な要素となります。
Q6 : 平衡化されていない二分探索木に、すでに昇順にソートされたn個の値を順番に挿入した場合、その後の探索の最悪計算量はどれですか。
昇順のデータを順に挿入すると、各要素は常に直前の要素の右の子になり、木が一本の連なり（連結リストのような形）に退化します。その結果、木の高さはn-1となり、探索では最悪すべてのノードをたどる必要があるためO(n)になります。AVL木や赤黒木のような自己平衡二分探索木は、挿入時に回転操作で高さを保ち、最悪でもO(log n)を保証します。
Q7 : 最小ヒープ（min-heap）において、最小の要素を削除せずに参照するだけの計算量はどれですか。
最小ヒープでは、すべての親ノードがその子ノードより小さいか等しいという性質を持つため、最小値は必ず根（先頭）に位置します。したがって最小値の参照は根を見るだけで済み、O(1)で行えます。一方、最小値を取り出して削除する場合は、末尾の要素を根に移して下方向へ入れ替える処理が必要になるため、O(log n)かかります。優先度付きキューの実装に広く使われています。
Q8 : 配列と連結リストを比べたとき、連結リストの先頭に新しい要素を挿入する操作の計算量と、その理由の組み合わせとして正しいものはどれですか。
連結リストは各ノードが次のノードへのポインタを持つ構造です。先頭への挿入は、新しいノードの次のポインタを現在の先頭ノードに向け、先頭を指す参照を新しいノードに更新するだけで完了するため、要素数に関係なくO(1)です。これに対し配列で先頭に挿入すると、既存の要素をすべて1つずつ後ろへずらす必要があり、O(n)の時間がかかります。
Q9 : 二分探索木を中間順（in-order：左の子、自分、右の子の順）で走査したとき、ノードの値はどのような順序で得られますか。
二分探索木では、任意のノードについて左部分木の値はそのノードより小さく、右部分木の値は大きいという性質があります。中間順走査は左の部分木、自分、右の部分木の順に訪問するため、小さい値から順に処理され、結果として昇順に整列された列が得られます。この性質を利用すると、二分探索木の要素をソート済みの状態で列挙することができます。
Q10 : スタックの特徴として正しいものはどれですか。
スタックは最後に入れた要素を最初に取り出すLIFO（後入れ先出し）構造です。push操作で要素を上に積み、pop操作で一番上の要素を取り出します。関数呼び出しを管理するコールスタック、ブラウザの戻る機能、エディタのUndo機能などに利用されます。最初に入れた要素を最初に取り出すFIFOはキューの性質であり、この違いはデータ構造を学ぶ上での基本となります。
まとめ
いかがでしたか？ 今回はデータ構造クイズをお送りしました。
皆さんは何問正解できましたか？
今回はデータ構造クイズを出題しました。
ぜひ、ほかのクイズにも挑戦してみてください！
次回のクイズもお楽しみに。
