基本情報技術者 アルゴリズム＆計算量「線形探索・二分探索・整列・Big O 記法・再帰・グラフ探索」の練習問題8問です。解けなかった問題は、各問の解説末尾のリンクから対応する解説記事に進んでください。
Q1. ソート済みの配列に対する線形探索と二分探索の計算量として、もっとも適切な組合せはどれですか？
回答
解説
正解は「C」です。
線形探索は先頭から順に1つずつ比較するため、最悪で n 個を確認することになり計算量は O(n) です。二分探索はソート済みの配列に対し中央の値と比較して対象範囲を毎回半分に絞るため、計算量は O(log n) ととても速くなります。電話帳を半分ずつめくっていくイメージです。
A は線形探索と二分探索が入れ替わり、B と D は両方の計算量が事実と一致しないため、いずれも誤りです。
Q2. バブルソートとクイックソートの平均計算量として、もっとも適切な組合せはどれですか？
回答
解説
正解は「A」です。
バブルソートは隣り合う要素を比較・交換する単純な整列で、平均・最悪ともに計算量は O(n²) です。クイックソートは基準値（ピボット）で小さい組・大きい組に分割していく分割統治型で、平均計算量は O(n log n) と高速です（最悪は O(n²)）。試験では平均計算量で問われることが多くなります。
B はバブルとクイックが入れ替わり、C は両方とも実際の計算量と異なり、D は両者の差を無視しているため、いずれも誤りです。
Q3. Big O 記法で計算量を表すとき、データ量 n が大きくなったときに「もっとも速く処理が終わる」ものはどれですか？
回答
解説
正解は「B」です。
Big O 記法はデータ量 n の増加に対して処理時間がどう増えるかを示す表記です。一般に O(1) < O(log n) < O(n) < O(n log n) < O(n²) の順で、左ほど速く右ほど遅くなります。選択肢の中では O(log n) がもっとも増加が緩やかで、n が大きくなっても処理時間がほとんど伸びません。
A の O(n²) はバブルソートなどの遅い整列、C の O(n) は線形探索のような線形時間で、O(log n) より増加が大きいため誤りです。
Q4. 再帰関数で n の階乗 n! を求める処理として、もっとも適切な考え方はどれですか？
回答
解説
正解は「D」です。
再帰関数は、自分自身を呼び出して処理を表現する手法です。階乗は「n = 0 なら 1（ベースケース）、それ以外は n × (n-1)!」と定義します。ベースケース（終了条件）があるからこそ呼び出しが止まり、正しい結果が得られます。
A は階乗の定義と無関係、B は終了条件のない再帰はスタックオーバーフローを起こすため誤り、C は階乗は掛け算であり足し算ではないため誤りです。
Q5. 二分探索を正しく使うために必要な前提条件として、もっとも適切なものはどれですか？
回答
解説
正解は「A」です。
二分探索は中央の値と探したい値を比較し、大小に応じて探索範囲を毎回半分に絞り込みます。この絞り込みが成り立つのは、データがソート済み（昇順または降順）のときだけです。未整列のデータには二分探索を適用できず、線形探索などを使います。
B は連結リストでは添字での中央アクセスが O(1) にならず二分探索に不向きなため誤り、C は要素数が2の累乗である必要はないため誤りです。
Q6. グラフの探索アルゴリズム「幅優先探索（BFS）」と「深さ優先探索（DFS）」の違いとして、もっとも適切なものはどれですか？
回答
解説
正解は「C」です。
幅優先探索（BFS）はキューを使い、出発点から距離の近いノードから順に広げていく探索です。一方の深さ優先探索（DFS）はスタック（または再帰）を使い、行ける所まで深く進んでから引き返します。迷路を壁伝いに進むようなイメージです。
A は BFS と DFS で使うデータ構造が入れ替わり、B は両者の探索順そのものが異なるため、いずれも誤りです。
Q7. O(1)、O(n)、O(n²) の3つを、データ量 n が大きいときに処理が速く終わる順（速い→遅い）に並べたものはどれですか？
回答
解説
正解は「B」です。
計算量はデータ量 n が大きいほど差が顕著になります。O(1) は n に関係なく一定時間、O(n) は n に比例、O(n²) は n の2乗に比例して増えます。したがって速い順は O(1) → O(n) → O(n²) です。配列の添字アクセスが O(1)、線形探索が O(n)、二重ループが O(n²) の代表例です。
A は遅い順、C と D は途中の順序が事実と一致しないため、いずれも誤りです。
Q8. アルゴリズムの効率とデータ構造の関係について、もっとも適切なものはどれですか？
回答
解説
正解は「A」です。
同じ「要素を探す」処理でも、未整列の配列なら線形探索で O(n)、二分探索木なら平均 O(log n) というように、選ぶデータ構造でアルゴリズムの計算量が変わります。要件に合ったデータ構造を選ぶことが、効率の良いプログラムの第一歩です。
B はデータ構造によって計算量が変わるため誤り、C は効率は言語名ではなくアルゴリズムとデータ構造で決まるため誤りです。
試験全体の流れを俯瞰したい時は、基本情報技術者 試験全体概要 に戻れます。