基本情報技術者 科目B アルゴリズムとプログラミングの練習問題10問です。データ構造（配列・連結リスト・木・ハッシュ）、整列・探索・再帰・グラフのアルゴリズム、擬似言語トレース、計算量の理解度を、あなた自身でチェックできます。解けなかった問題は、各問の解説末尾のリンクから対応する解説記事に進んでください。
Q1. 配列と連結リストの違いとして、もっとも適切なものはどれですか？
回答
解説
正解は「B」です。
配列はメモリ上で要素が連続して並んでおり、添字を使ったランダムアクセスが O(1) で行えます。一方の連結リストは、各要素が次の要素へのポインタを持ち、ポインタの付け替えだけで途中挿入・削除を O(1) で行えるのが強みです。配列を「整然と並んだロッカー」、連結リストを「順番にチケットを渡していく行列」とイメージすると違いをつかみやすくなります。
A は配列と連結リストの強みが逆です。C はランダムアクセスと挿入の計算量が異なるため誤り、D は連結リストの要素がメモリ上で散らばっていてもポインタでつながる点が強みなので誤りです。
Q2. スタックとキューの動作として、もっとも適切な組合せはどれですか？
回答
解説
正解は「C」です。
スタックは LIFO（Last In First Out）構造で、最後に入れたものを最初に取り出します。お皿を積み上げて上から取るイメージです。キューは FIFO（First In First Out）構造で、最初に入れたものを最初に取り出します。お店のレジ待ちの行列が代表例です。スタックは関数呼び出しの管理（コールスタック）に、キューはタスクスケジューリングや印刷ジョブの管理によく使われます。
A は LIFO と FIFO が入れ替わっており誤り、B は両方を FIFO とする点で誤り、D は両方とも取り出し操作（pop / dequeue）を備えているため誤りです。
Q3. 二分探索木（Binary Search Tree）の性質として、もっとも適切なものはどれですか？
回答
解説
正解は「A」です。
二分探索木は、各ノードについて「左部分木の値 < 親 < 右部分木の値」という大小関係を保つ木構造です。この性質によって、根から比較を繰り返すだけで目的の値を素早く絞り込めます。バランスの取れた状態であれば探索・挿入・削除の計算量は平均 O(log n) となり、線形探索より大幅に高速です。
B は二分探索木が完全二分木とは限らないため誤り、C は大小関係こそが二分探索木の核なので誤り、D は最悪ケース限定の話で、平均では O(log n) で動作するため誤りです。
Q4. ソート済みの配列に対する線形探索と二分探索の計算量として、もっとも適切な組合せはどれですか？
回答
解説
正解は「D」です。
線形探索は先頭から順に1つずつ比較していくため、最悪ケースで n 個を確認することになり計算量は O(n) です。二分探索はソート済みの配列に対して中央の値と比較し、対象範囲を毎回半分に絞り込みます。電話帳を半分めくっていくイメージで、計算量は O(log n) ととても速くなります。ただし二分探索を使う前提として、配列がソート済みである必要があります。
A は線形探索と二分探索の計算量が入れ替わっており誤り、B と C は両方の計算量が事実と一致しません。
Q5. バブルソートとクイックソートの平均計算量として、もっとも適切な組合せはどれですか？
回答
解説
正解は「B」です。
バブルソートは隣り合う要素を比較・交換していく単純な整列で、平均・最悪ともに計算量は O(n²) です。実装がやさしい反面、データ量が増えると遅くなります。クイックソートは基準値（ピボット）を選んで小さい組・大きい組に分割していく分割統治型で、平均計算量は O(n log n) と高速です（最悪ケースは O(n²)）。本試験では平均計算量で問われることが多くなります。
A はバブルとクイックの計算量が入れ替わっており誤り、C は両方とも実際の計算量と異なり誤り、D は両者の差を無視しているため誤りです。
Q6. Big O 記法での計算量が、データ量 n が大きくなったときに「もっとも速く処理が終わる」ものはどれですか？
回答
解説
正解は「C」です。
Big O 記法はデータ量 n の増加に対して処理時間がどう増えるかを示す表記です。一般に O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) の順で、左ほど速く右ほど遅くなります。選択肢の中では O(log n) がもっとも増加が緩やかで、n が大きくなっても処理時間がほとんど伸びません。二分探索や平衡二分木の探索が典型例です。
A の O(n²) はバブルソートなどの遅い整列、B の O(n) は線形探索のような線形時間、D の O(2ⁿ) は指数時間で、n が少し増えただけで爆発的に処理が遅くなる最悪クラスです。
Q7. 再帰関数で n の階乗 n! を求める処理として、もっとも適切な考え方はどれですか？
回答
解説
正解は「A」です。
再帰関数は、自分自身を呼び出すことで処理を表現する手法です。階乗の場合、「n = 0 なら 1（ベースケース）、それ以外は n × (n-1)!」と定義します。ベースケース（終了条件）があるからこそ呼び出しが止まり、正しい結果が得られます。階乗のように小さな同じ形の問題に分割できる処理は、再帰で簡潔に書けます。
B は階乗の定義と無関係なため誤り、C は終了条件を持たない再帰はスタックオーバーフローを起こすため誤り、D は for ループを使った反復処理の説明で再帰ではなく、また「足し算」も階乗の定義と合わないため誤りです。
Q8. 次の擬似言語プログラムを実行したとき、変数 result に入る値はどれですか？
整数型: x ← 5
整数型: y ← 3
整数型: result
もし x > y ならば
result ← x – y
そうでなければ
result ← y – x
回答
解説
正解は「C」です。
順にトレースします。x に 5、y に 3 が代入され、条件「x > y」は 5 > 3 で真となります。そのため「もし」側の分岐に入り、result ← x – y が実行されて result には 5 – 3 = 2 が入ります。擬似言語の問題は、変数の値を1行ずつ書き出して条件分岐を丁寧に追う「トレース」が鉄則です。
A の 8 は加算してしまった誤り、B の -2 は y – x（そうでなければ側）を実行してしまった誤り、D の 0 は代入順を取り違えた誤りです。
Q9. ハッシュ法で異なるキーが同じハッシュ値になる衝突への対策「チェイン法」の説明として、もっとも適切なものはどれですか？
回答
解説
正解は「D」です。
チェイン法（連鎖法）は、ハッシュ表の各位置に連結リストを持たせ、同じハッシュ値になった要素をそのリストにつないで格納する方法です。衝突が起きてもリストを順にたどれば目的の要素にたどり着けます。実装がシンプルで、要素数がハッシュ表のサイズを超えても破綻しないのが強みです。
A は衝突のたびに作り直す方法は一般的な対策ではないので誤り、B は別のオープンアドレス法の説明、C は暗号化と衝突対策は別概念で誤りです。
Q10. グラフの探索アルゴリズム「幅優先探索（BFS）」と「深さ優先探索（DFS）」の違いとして、もっとも適切なものはどれですか？
回答
解説
正解は「B」です。
幅優先探索（BFS）はキューを使い、出発点から距離の近いノードから順に広げていく探索です。最短経路（辺の重みがない場合）を求める用途に向いています。一方の深さ優先探索（DFS）はスタック（または再帰）を使い、行ける所まで深く進んでから引き返す方式です。迷路を片手で壁伝いに進むようなイメージです。
A は BFS と DFS で使うデータ構造が入れ替わっており誤り、C は探索順そのものが異なるため誤り、D はソートはグラフ探索の前提ではないため誤りです。
試験全体の流れを俯瞰したい時は、基本情報技術者 試験全体概要 に戻れます。