クイズ: データ構造とアルゴリズム
バイナリツリーをBSできるか？
このクイズは、データ構造（スタック、リスト、ツリー等）とアルゴリズム、そして時間計算量に関する知識を評価します。
20問…開始！
LIFO（Last In, First Out）アクセスパターンに最適なデータ構造はどれですか？
スタックはLIFOアクセスパターンに最適です。キューはFIFO（First In, First Out）アクセスパターンに最適です。
アルゴリズムが入力サイズに関係なく常に同じ時間で実行される場合、その時間計算量は何ですか？
O(1) は定数時間計算量を表します。入力サイズに関係なく、アルゴリズムは常に同じ時間で実行されます。
単方向リンクリストの長さを計算する際の時間計算量は何ですか？
単方向リンクリストの長さを計算するには、ヘッドからテイルまで全てのノードを走査する必要があり、時間計算量は O(n) になります。
バランスの取れた二分探索木で要素を検索する際の平均時間計算量は何ですか？
バランスの取れたBSTでは、各レベルで探索空間が半分になるため、検索の平均時間計算量は O(log n) です。
最悪の場合のマージソートアルゴリズムの時間計算量は何ですか？
マージソートは常に最悪ケースで O(n log n) の計算量で動作します。配列を半分に分割し、ソート済みの部分配列をマージすることを繰り返すためです。
Breadth-First Search (BFS) を実装する際に通常使用されるデータ構造は何ですか？
BFS はキューを使用してノードをレベルごとに探索し、幅優先（「行」単位）でノードを処理します。
有向グラフでサイクルを検出する際に一般的に使用されるアルゴリズムはどれですか？
深さ優先探索（DFS）は、訪問したノードを追跡するために再帰スタックを保持することで、グラフ内のサイクルを検出する際に一般的に使用されます。
ヒープソートはヒープを構築し、最大要素を繰り返し取り出すことで、最悪ケースでも O(n log n) の時間計算量を保ちます。
ハッシュテーブルで要素にアクセスする際の平均時間計算量は何ですか？
ハッシュテーブルは、衝突を最小限に抑える優れたハッシュ関数を前提とすれば、要素へのアクセスの平均時間計算量は O(1) です。
スタックの主要な操作は Push（要素を追加）、Pop（要素を削除）、そして Peek（要素を削除せずにトップを参照）です。
非負の重みを持つグラフで最短経路を求める際に一般的に使用されるアルゴリズムはどれですか？
ダイクストラ法は、非負のエッジ重みを持つグラフで最短経路を求める際に頻繁に使用されます。優先度キューを利用して、最短距離を効率的に算出します。
自己平衡二分探索木の例が含まれるセットはどれですか？
AVL木 と 赤黒木 は自己平衡木の一種で、挿入や削除のたびに木がバランスを保つようにします。
再帰関数で無限再帰を防ぐために何を定義する必要がありますか？
再帰関数では、特定の条件が満たされたときに再帰呼び出しを停止させ、無限再帰を防ぐために基本ケースが必要です。
キューの主要な2つの操作はエンキュー（要素を末尾に追加する）とデキュー（要素を先頭から削除する）です。
グラフでトポロジカルソートを実行する条件は何ですか？
グラフが有向非循環（DAG）である場合にトポロジカルソートを実行できます。この順序付けはタスクスケジューリング問題で役立ちます。
フィボナッチ数列の単純な再帰実装の時間計算量は何ですか？
フィボナッチ数列の単純な再帰実装は、各フィボナッチ数に対して膨大な繰り返し計算が行われるため、時間計算量は O(2^n) です。
優先度キューを実装する際に一般的に使用されるデータ構造はどれですか？
優先度キューは、最高または最低の優先度の要素を効率的に取り出せるため、通常ヒープを使って実装されます。
二分木の深さ優先走査で一般的な順序を列挙しているのはどれですか？
中順、前順、後順は二分木における代表的な深さ優先走査の3つの順序で、ノードの訪問順序がそれぞれ異なります。幅優先走査も一般的ですが、別の走査カテゴリです。
次のうち、ミニヒープに当てはまる性質はどれですか？
ミニヒープでは、根は常に最小要素であり、木の高さは O(log n) になるため、挿入と抽出が効率的です。
バブルソートは安定なソートアルゴリズムで、等しい要素の相対順序を保ったままソートします。
