印刷プレビューです。ブラウザの印刷機能でPDF保存・印刷できます。
基本情報技術者 アルゴリズムとデータ構造
全40問 ／ トルカ（https://toruca.app）
問1. アルゴリズムの計算量を表す「オーダー記法（O記法）」の説明として最も適切なものはどれか。
- A. 入力サイズが増加した際の処理時間や使用メモリの増加傾向を漸近的に表す記法
- B. プログラムの実行にかかった正確な秒数を表す記法
- C. プログラムのバグの個数を表す記法
- D. プログラムのソースコードの行数を表す記法
正解: A. 入力サイズが増加した際の処理時間や使用メモリの増加傾向を漸近的に表す記法 ／ オーダー記法（O記法）は、入力サイズnが増加した際に処理時間や使用メモリがどのような傾向で増加するかを漸近的（大まかな上限）に表す記法であり、アルゴリズムの効率性を比較する際の指標として広く用いられる。
問2. 配列に対する二分探索法の計算量として最も適切なものはどれか（配列は整列済みとする）。
- A. O(log n)
- B. O(n)
- C. O(n^2)
- D. O(1)
正解: A. O(log n) ／ 二分探索法は、整列済み配列に対して探索範囲を毎回半分に絞り込むため、計算量はO(log n)となる。線形探索のO(n)と比較して大規模データに対して高速である。
問3. バブルソートの説明として最も適切なものはどれか。
- A. 隣接する要素を比較し、順序が逆であれば交換する操作を繰り返して整列するアルゴリズム
- B. 配列の中央値を基準に要素を分割し再帰的に整列するアルゴリズム
- C. 未整列部分から最小値を探して先頭に移動する操作を繰り返すアルゴリズム
- D. 整列済み部分に新しい要素を適切な位置に挿入していくアルゴリズム
正解: A. 隣接する要素を比較し、順序が逆であれば交換する操作を繰り返して整列するアルゴリズム ／ バブルソートは、隣接する要素同士を比較し、順序が逆であれば交換するという操作を配列全体に繰り返し適用することで整列するアルゴリズムであり、平均・最悪計算量はO(n^2)である。
問4. クイックソートの基本的な考え方として最も適切なものはどれか。
- A. 基準値（ピボット）を選び、それより小さい要素と大きい要素に分割することを再帰的に繰り返して整列する
- B. 隣接要素の交換のみを繰り返して整列する
- C. 常に配列全体を1要素ずつ末尾から比較して整列する
- D. 整列を一切行わず出現順のまま出力する
正解: A. 基準値（ピボット）を選び、それより小さい要素と大きい要素に分割することを再帰的に繰り返して整列する ／ クイックソートは、基準値（ピボット）を選定し、それより小さい要素のグループと大きい要素のグループに分割する操作を再帰的に繰り返すことで整列する分割統治法に基づくアルゴリズムであり、平均計算量はO(n log n)である。
問5. マージソートの特徴として最も適切なものはどれか。
- A. 配列を再帰的に半分に分割し、それぞれを整列した後に統合（マージ）することで全体を整列する
- B. 常に最悪計算量がO(n^2)になる
- C. 追加のメモリ領域を一切使用しない
- D. 整列の安定性（同じ値の要素の順序維持）が保証されない
正解: A. 配列を再帰的に半分に分割し、それぞれを整列した後に統合（マージ）することで全体を整列する ／ マージソートは、配列を再帰的に半分に分割していき、最小単位まで分割した後に整列された部分列同士を統合（マージ）していくことで全体を整列するアルゴリズムであり、最悪計算量もO(n log n)で安定しており、安定な整列アルゴリズムでもある。
問6. 選択ソートの説明として最も適切なものはどれか。
- A. 未整列部分から最小値（または最大値）を探索し、未整列部分の先頭と交換する操作を繰り返す
- B. 隣接する要素のみを比較して交換する
- C. 配列を再帰的に分割して整列する
- D. 既に整列済みの部分に要素を挿入していく
正解: A. 未整列部分から最小値（または最大値）を探索し、未整列部分の先頭と交換する操作を繰り返す ／ 選択ソートは、未整列部分から最小値（昇順の場合）を探索し、それを未整列部分の先頭要素と交換するという操作を繰り返すことで整列するアルゴリズムであり、計算量はO(n^2)である。
問7. 挿入ソートの特徴として最も適切なものはどれか。
- A. 整列済み部分に対して未整列の要素を適切な位置に挿入していくことで整列する
- B. 常に配列全体を分割して並列に処理する
- C. 計算量は常にO(log n)である
- D. 整列済みデータに対しても必ずO(n^2)の時間がかかる
正解: A. 整列済み部分に対して未整列の要素を適切な位置に挿入していくことで整列する ／ 挿入ソートは、整列済みの部分列に対して未整列の要素を適切な位置に挿入していくことで全体を整列するアルゴリズムであり、ほぼ整列済みのデータに対しては高速に動作するという特徴がある（最良計算量O(n)）。
問8. スタック（Stack）のデータ構造の特徴として最も適切なものはどれか。
- A. 後入れ先出し（LIFO: Last In First Out）でデータを管理する構造
- B. 先入れ先出し（FIFO: First In First Out）でデータを管理する構造
- C. データに優先順位を付けて管理する構造
- D. キーと値のペアで管理する構造
正解: A. 後入れ先出し（LIFO: Last In First Out）でデータを管理する構造 ／ スタックは、最後に格納（プッシュ）されたデータが最初に取り出される（ポップされる）、後入れ先出し（LIFO）の性質を持つデータ構造であり、関数呼び出しの管理やブラウザの「戻る」機能等に応用される。
問9. キュー（Queue）のデータ構造の特徴として最も適切なものはどれか。
- A. 先入れ先出し（FIFO: First In First Out）でデータを管理する構造
- B. 後入れ先出し（LIFO: Last In First Out）でデータを管理する構造
- C. データを常に降順に自動整列する構造
- D. 重複するデータを許可しない構造
正解: A. 先入れ先出し（FIFO: First In First Out）でデータを管理する構造 ／ キューは、最初に格納（エンキュー）されたデータが最初に取り出される（デキューされる）、先入れ先出し（FIFO）の性質を持つデータ構造であり、印刷ジョブの管理やタスクの順次処理等に応用される。
問10. 連結リスト（Linked List）の特徴として最も適切なものはどれか。
- A. 各要素（ノード）が次の要素へのポインタ（参照）を持つことで連結される構造で、要素の挿入・削除が配列より効率的な場合がある
- B. 全ての要素が連続したメモリ領域に必ず配置される構造
- C. 要素数が固定され、実行時に変更できない構造
- D. キーと値の組のみで構成される構造
正解: A. 各要素（ノード）が次の要素へのポインタ（参照）を持つことで連結される構造で、要素の挿入・削除が配列より効率的な場合がある ／ 連結リストは、各要素（ノード）がデータと次の要素へのポインタ（参照）を持つことで連結される構造であり、配列と異なり要素が連続したメモリ領域である必要がなく、途中への挿入・削除がポインタの付け替えのみで済むため効率的な場合がある。
問11. 二分木（Binary Tree）の説明として最も適切なものはどれか。
- A. 各ノードが最大2つの子ノード（左の子・右の子）を持つ木構造
- B. 各ノードが必ず3つ以上の子ノードを持つ木構造
- C. 循環構造を持つグラフ
- D. 全てのノードが同じ深さに位置する構造
正解: A. 各ノードが最大2つの子ノード（左の子・右の子）を持つ木構造 ／ 二分木は、各ノードが最大2つの子ノード（左の子・右の子）を持つ木構造であり、探索・整列・優先度付きキュー等、様々なアルゴリズムやデータ構造の基礎として利用される。
問12. 二分探索木（Binary Search Tree）の性質として最も適切なものはどれか。
- A. 各ノードについて、左の子孫は自分より小さい値、右の子孫は自分より大きい値を持つ
- B. 全てのノードの値が等しい
- C. 葉ノード以外は子を持たない
- D. 根ノードは常に最小値を持つ
正解: A. 各ノードについて、左の子孫は自分より小さい値、右の子孫は自分より大きい値を持つ ／ 二分探索木は、各ノードについて左部分木の全ノードが自分より小さい値、右部分木の全ノードが自分より大きい値を持つという性質を満たす二分木であり、この性質により平均O(log n)での探索が可能になる（ただし偏った木では最悪O(n)になりうる）。
問13. 二分木の「行きがけ順（先行順、pre-order）」の走査順序として最も適切なものはどれか。
- A. 根 → 左部分木 → 右部分木 の順で訪問する
- B. 左部分木 → 根 → 右部分木 の順で訪問する
- C. 左部分木 → 右部分木 → 根 の順で訪問する
- D. 右部分木 → 根 → 左部分木 の順で訪問する
正解: A. 根 → 左部分木 → 右部分木 の順で訪問する ／ 行きがけ順（先行順、pre-order）は、根ノードを最初に訪問し、その後左部分木、右部分木の順に再帰的に訪問する走査方法である。中間順（in-order）は左→根→右、通りがけ順（post-order）は左→右→根の順である。
問14. グラフの「隣接行列」による表現の説明として最も適切なものはどれか。
- A. 頂点数×頂点数の2次元配列を用い、各要素で頂点間の接続の有無や重みを表す表現方法
- B. 各頂点が持つ隣接頂点のリストのみで表現する方法
- C. 頂点をハッシュテーブルのキーとしてのみ管理する方法
- D. グラフを常に木構造に変換してから表現する方法
正解: A. 頂点数×頂点数の2次元配列を用い、各要素で頂点間の接続の有無や重みを表す表現方法 ／ 隣接行列は、頂点数×頂点数の2次元配列を用い、行と列の交点にあたる要素で頂点間の接続の有無（または重み）を表現する方法であり、頂点間の接続確認がO(1)で行える一方、疎なグラフではメモリ効率が悪くなる。
問15. 幅優先探索（BFS: Breadth-First Search）の特徴として最も適切なものはどれか。
- A. 開始頂点から近い頂点（距離が小さい頂点）から順に探索していく手法で、キューを用いて実装されることが多い
- B. 常に最も遠い頂点から探索する手法
- C. スタックのみを用いて実装しなければならない手法
- D. グラフの全頂点を一度にまとめて探索する手法
正解: A. 開始頂点から近い頂点（距離が小さい頂点）から順に探索していく手法で、キューを用いて実装されることが多い ／ 幅優先探索（BFS）は、開始頂点から近い頂点（距離が小さい頂点）から順に探索していく手法であり、キュー（FIFO）を用いて実装されることが多く、最短経路（辺の重みがない場合）を求める際等に利用される。
問16. 深さ優先探索（DFS: Depth-First Search）の特徴として最も適切なものはどれか。
- A. 1つの経路を可能な限り深く進んでから引き返す探索手法で、スタック（または再帰）を用いて実装されることが多い
- B. 常に幅方向に均等に探索する手法
- C. キューを用いなければ実装できない手法
- D. グラフの探索には一切利用されない手法
正解: A. 1つの経路を可能な限り深く進んでから引き返す探索手法で、スタック（または再帰）を用いて実装されることが多い ／ 深さ優先探索（DFS）は、1つの経路を可能な限り深く進み、行き止まりに達したら直前の分岐点まで引き返して別の経路を探索する手法であり、スタック（または再帰呼び出し）を用いて実装されることが多い。
問17. 再帰的アルゴリズムにおいて必ず必要となる要素として最も適切なものはどれか。
- A. 処理を終了させるための「基底条件（ベースケース）」
- B. 必ず2つ以上の引数を取ること
- C. 必ずループ文（for/while）を併用すること
- D. 必ずグローバル変数を使用すること
正解: A. 処理を終了させるための「基底条件（ベースケース）」 ／ 再帰的アルゴリズムは、自分自身を呼び出す処理であるため、無限に呼び出しが続かないよう処理を終了させる「基底条件（ベースケース）」を必ず含む必要がある。基底条件がないと無限再帰によりスタックオーバーフローが発生する。
問18. n=1,000のデータに対し、計算量がO(n^2)のアルゴリズムを実行した場合の概算比較演算回数はどの程度のオーダーか。数値で答えよ（n^2の値を答える）。
n=1,000として、n^2の値を計算せよ。単位: 回 ／ ヒント: n^2 = 1,000 × 1,000
正解: 1000000回 ／ O(n^2)のアルゴリズムでは、n=1,000の場合、概算の演算回数はn^2=1,000×1,000=1,000,000回のオーダーとなる。これはO(n log n)やO(n)のアルゴリズムと比較して大幅に多い演算回数であり、データ量が増えるほど処理時間の差が顕著になる。
問19. 優先度付きキュー（Priority Queue）の特徴として最も適切なものはどれか。
- A. 格納順序に関わらず、優先度が最も高い（または最も低い）要素から取り出される
- B. 必ず格納した順序どおりに取り出される
- C. 常に格納した要素の逆順に取り出される
- D. ランダムな順序でのみ取り出しが可能である
正解: A. 格納順序に関わらず、優先度が最も高い（または最も低い）要素から取り出される ／ 優先度付きキューは、各要素に優先度が設定されており、格納順序に関わらず優先度が最も高い（または最も低い）要素から取り出されるデータ構造であり、多くの場合ヒープ（Heap）というデータ構造を用いて効率的に実装される。
問20. ハッシュテーブル（Hash Table）の特徴として最も適切なものはどれか。
- A. キーをハッシュ関数で変換したハッシュ値を用いて格納位置を決定し、平均的にO(1)での検索・追加・削除が可能なデータ構造
- B. 常にキーの大小関係に基づいて整列された状態を維持するデータ構造
- C. 格納できる要素数に上限が一切ないデータ構造
- D. ハッシュ値の衝突が絶対に発生しないデータ構造
正解: A. キーをハッシュ関数で変換したハッシュ値を用いて格納位置を決定し、平均的にO(1)での検索・追加・削除が可能なデータ構造 ／ ハッシュテーブルは、キーをハッシュ関数によって変換したハッシュ値を用いて格納位置（バケット）を決定するデータ構造であり、ハッシュ関数が適切に設計されていれば平均的にO(1)での検索・追加・削除が可能である。ただし異なるキーが同じハッシュ値になる「衝突」への対処（チェイン法・オープンアドレス法等）が必要である。
問21. 整列アルゴリズムにおける「安定性（stability）」の説明として最も適切なものはどれか。
- A. 同じ値を持つ要素同士の元の相対順序が、整列後も維持される性質
- B. 整列に必要な計算時間が常に一定であるという性質
- C. 整列済みデータに対しては絶対にエラーが発生しないという性質
- D. 使用するメモリ量が常にゼロになるという性質
正解: A. 同じ値を持つ要素同士の元の相対順序が、整列後も維持される性質 ／ 整列アルゴリズムの「安定性」とは、同じ値を持つ複数の要素があった場合、整列後もそれらの元の相対順序が維持される性質を指す。マージソートや挿入ソートは安定な整列アルゴリズムであるのに対し、一般的なクイックソートの実装は不安定である。
問22. 計算量O(1)（定数時間）の説明として最も適切なものはどれか。
- A. 入力サイズnに関わらず、処理時間がほぼ一定であること
- B. 入力サイズnに比例して処理時間が増加すること
- C. 入力サイズnの2乗に比例して処理時間が増加すること
- D. 処理に無限の時間がかかること
正解: A. 入力サイズnに関わらず、処理時間がほぼ一定であること ／ 計算量O(1)（定数時間）は、入力サイズnがどれだけ大きくなっても、処理時間がほぼ一定であることを意味する。配列の特定インデックスへのアクセスやハッシュテーブルへの平均的なアクセス等がこれに該当する。
問23. 整列アルゴリズムと平均計算量の組み合わせを対応させよ。
- バブルソート ー （ ）
- クイックソート ー （ ）
- 二分探索 ー （ ）
正解: バブルソート→O(n^2)、クイックソート→O(n log n)、二分探索→O(log n) ／ バブルソート・選択ソート・挿入ソート等の単純な整列アルゴリズムはO(n^2)、クイックソート・マージソート・ヒープソート等の高度な整列アルゴリズムは平均O(n log n)、整列済み配列への二分探索はO(log n)である。
問24. ダイクストラ法（Dijkstra's algorithm）の用途として最も適切なものはどれか。
- A. 辺に非負の重みを持つグラフにおいて、単一始点から各頂点への最短経路を求めるアルゴリズム
- B. グラフが木構造であるかどうかを判定するアルゴリズム
- C. 配列を整列するためのアルゴリズム
- D. 文字列同士の類似度を計算するアルゴリズム
正解: A. 辺に非負の重みを持つグラフにおいて、単一始点から各頂点への最短経路を求めるアルゴリズム ／ ダイクストラ法は、辺に非負の重みを持つグラフにおいて、単一の始点から他の全ての頂点への最短経路（および最短距離）を求めるアルゴリズムであり、カーナビゲーションシステムの経路探索やネットワークルーティング等に応用される。
問25. 配列と連結リストを比較した際の配列の利点として最も適切なものはどれか。
- A. インデックスを指定した要素へのランダムアクセスがO(1)で可能である
- B. 要素の途中への挿入・削除が常に高速である
- C. サイズを実行時に自由に変更でき、メモリの再配置が一切発生しない
- D. ポインタを一切使用しないためメモリ効率が常に最も良い
正解: A. インデックスを指定した要素へのランダムアクセスがO(1)で可能である ／ 配列は要素が連続したメモリ領域に格納されるため、インデックスを指定した要素へのランダムアクセスがO(1)で可能であるという利点がある。一方、途中への挿入・削除には要素のシフトが必要でO(n)かかる場合があり、この点では連結リストの方が有利な場合がある。
問26. フィボナッチ数列を単純な再帰で計算する場合に生じうる問題として最も適切なものはどれか。
- A. 同じ部分問題が何度も繰り返し計算され、計算量が指数関数的に増大する
- B. 計算量が常にO(1)になり非効率が問題になることはない
- C. 再帰を使うと必ず無限ループになる
- D. フィボナッチ数列は再帰では一切計算できない
正解: A. 同じ部分問題が何度も繰り返し計算され、計算量が指数関数的に増大する ／ フィボナッチ数列を単純な再帰（メモ化なし）で計算すると、同じ部分問題（例：fib(3)）が何度も繰り返し計算されるため、計算量が指数関数的（O(2^n)程度）に増大するという問題が生じる。この非効率性は、計算結果を記録して再利用する「メモ化」や「動的計画法」によって解消できる。
問27. 動的計画法（Dynamic Programming）の基本的な考え方として最も適切なものはどれか。
- A. 問題を部分問題に分割し、各部分問題の計算結果を記録（メモ化）して再利用することで効率的に解を求める手法
- B. 問題を一切分割せず一度に全体を計算する手法
- C. 常にランダムな試行を繰り返して近似解を求める手法
- D. 整列アルゴリズムの一種を指す用語である
正解: A. 問題を部分問題に分割し、各部分問題の計算結果を記録（メモ化）して再利用することで効率的に解を求める手法 ／ 動的計画法は、問題を部分問題に分割し、各部分問題の計算結果を記録（メモ化）して再利用することで、重複した計算を避け効率的に解を求める手法であり、フィボナッチ数列の計算やナップサック問題、最短経路問題等、幅広い分野に応用される。
問28. 木構造とグラフの関係性として最も適切なものはどれか。
- A. 木構造は、閉路（サイクル）を持たない連結グラフの一種である
- B. 木構造とグラフは全く無関係の概念である
- C. グラフは必ず木構造の一種である
- D. 木構造は必ず閉路を持つ
正解: A. 木構造は、閉路（サイクル）を持たない連結グラフの一種である ／ 木構造は、閉路（サイクル）を持たない連結グラフの特殊な形態であり、n個の頂点を持つ木は必ずn-1本の辺を持つという性質がある。グラフの一種として捉えることができ、階層構造の表現等に広く利用される。
問29. ヒープ（Heap）の特徴として最も適切なものはどれか。
- A. 親ノードと子ノードの間に一定の大小関係（ヒープ条件）が常に成り立つ完全二分木の一種で、優先度付きキューの実装に用いられる
- B. 常に要素を挿入した順序どおりに保持する構造
- C. キーと値のペアのみを扱う構造
- D. 循環リストの別名である
正解: A. 親ノードと子ノードの間に一定の大小関係（ヒープ条件）が常に成り立つ完全二分木の一種で、優先度付きキューの実装に用いられる ／ ヒープは、親ノードの値が子ノードの値以上（最大ヒープ）または以下（最小ヒープ）であるという一定の大小関係（ヒープ条件）が常に成り立つ完全二分木の一種であり、この性質を利用して優先度付きキューやヒープソートの実装に用いられる。
問30. 「最悪計算量（worst-case complexity）」の説明として最も適切なものはどれか。
- A. 入力の与えられ方によらず、そのアルゴリズムが取りうる最も多くの処理時間・ステップ数を表す指標
- B. そのアルゴリズムの平均的な処理時間を表す指標
- C. そのアルゴリズムが最も速く終了する場合の処理時間を表す指標
- D. 実際に測定した処理時間のみを表す指標
正解: A. 入力の与えられ方によらず、そのアルゴリズムが取りうる最も多くの処理時間・ステップ数を表す指標 ／ 最悪計算量は、あらゆる入力パターンの中で、そのアルゴリズムが取りうる最も多くの処理時間・ステップ数を表す指標であり、システムの応答時間の上限を保証したい場合等に重視される（クイックソートの最悪計算量O(n^2)等が代表例）。
問31. n=10,000のデータに対する処理時間が短い順（効率が良い順）に、以下の計算量を並び替えよ。
- （ ）O(log n)
- （ ）O(n)
- （ ）O(n log n)
- （ ）O(n^2)
正解の順序: O(log n) → O(n) → O(n log n) → O(n^2) ／ 計算量の増加速度は、O(log n) < O(n) < O(n log n) < O(n^2)の順であり、nが大きくなるほどこの差は顕著になる。効率の良いアルゴリズムを選択することは、大規模データを扱うシステムの性能に直結する。
問32. 二分探索木において、要素の探索・挿入・削除の平均計算量として最も適切なものはどれか（木が適度にバランスしている場合）。
- A. O(log n)
- B. O(n)
- C. O(n^2)
- D. O(1)
正解: A. O(log n) ／ 二分探索木がバランスの取れた状態であれば、木の高さがO(log n)程度になるため、探索・挿入・削除の平均計算量はO(log n)となる。ただし、偏った木（例：単純な連結リスト状）になると最悪O(n)まで悪化する点に注意が必要である（これを解消するのが平衡二分探索木）。
問33. 文字列の中から特定のパターンを検索するアルゴリズムの工夫として最も適切なものはどれか。
- A. KMP法（Knuth-Morris-Pratt法）等、一致に失敗した際の情報を活用して比較回数を削減する手法を用いる
- B. 常に1文字ずつ先頭から全て比較し直す単純な方法のみが存在する
- C. 文字列検索には計算量という概念が適用されない
- D. 文字列は必ず数値に変換してからでないと検索できない
正解: A. KMP法（Knuth-Morris-Pratt法）等、一致に失敗した際の情報を活用して比較回数を削減する手法を用いる ／ 文字列検索アルゴリズムには、単純な総当たり法（計算量O(nm)）に加え、KMP法（Knuth-Morris-Pratt法）やボイヤー・ムーア法等、一致に失敗した際に得られる情報を活用することで無駄な比較を削減し、より効率的に検索する手法が存在する。
問34. 「分割統治法（Divide and Conquer）」の基本的な考え方として最も適切なものはどれか。
- A. 問題を独立した複数の小さな部分問題に分割し、それぞれを解いた後に結果を統合して元の問題を解く手法
- B. 問題を一切分割せず力任せに全探索する手法
- C. 問題をランダムに変形して解を推測する手法
- D. データ構造にのみ適用され、アルゴリズムには適用されない考え方
正解: A. 問題を独立した複数の小さな部分問題に分割し、それぞれを解いた後に結果を統合して元の問題を解く手法 ／ 分割統治法は、問題を独立した複数の小さな部分問題に分割し、それぞれを再帰的に解いた後、その結果を統合（マージ）して元の問題の解を得る手法であり、マージソートやクイックソート、二分探索等がこの考え方に基づいている。
問35. 巡回セールスマン問題（TSP: Traveling Salesman Problem）の特徴として最も適切なものはどれか。
- A. 全ての都市を1度ずつ訪れて出発地に戻る最短経路を求める問題で、都市数の増加に伴い計算量が爆発的に増大するNP困難な問題として知られる
- B. 常にO(log n)で厳密解が求まる問題
- C. グラフ理論とは全く無関係の問題である
- D. 都市が2つ以下の場合にのみ定義される問題である
正解: A. 全ての都市を1度ずつ訪れて出発地に戻る最短経路を求める問題で、都市数の増加に伴い計算量が爆発的に増大するNP困難な問題として知られる ／ 巡回セールスマン問題（TSP）は、全ての都市をちょうど1度ずつ訪問して出発地に戻る経路のうち、総移動距離が最小となる経路を求める問題であり、都市数nの増加に伴い組み合わせ数が階乗的に増大するNP困難な問題として知られ、大規模な場合は近似解法が用いられることが多い。
問36. 実務で使われる多くのプログラミング言語の標準ライブラリの整列関数（ソート関数）で採用されることが多いアルゴリズムの特徴として最も適切なものはどれか。
- A. クイックソートやマージソート、ティムソート等、平均計算量O(n log n)の高度なアルゴリズムをベースに実装されていることが多い
- B. 必ずバブルソートのみで実装されている
- C. 整列アルゴリズムは標準ライブラリには一切実装されていない
- D. 常に手動でアルゴリズムを1から実装する必要がある
正解: A. クイックソートやマージソート、ティムソート等、平均計算量O(n log n)の高度なアルゴリズムをベースに実装されていることが多い ／ 多くのプログラミング言語の標準ライブラリの整列関数は、クイックソートやマージソート、それらを改良したティムソート（Timsort）等、平均計算量O(n log n)の高度なアルゴリズムをベースに実装されていることが多く、開発者が1からアルゴリズムを実装する必要は通常ない。
問37. 双方向連結リスト（Doubly Linked List）が単方向連結リストと比較して持つ利点として最も適切なものはどれか。
- A. 各ノードが前後両方のノードへのポインタを持つため、逆方向への走査や削除操作がより効率的に行える
- B. メモリ使用量が単方向連結リストより必ず少なくなる
- C. ランダムアクセスがO(1)で可能になる
- D. 整列済みの状態を常に自動的に維持する
正解: A. 各ノードが前後両方のノードへのポインタを持つため、逆方向への走査や削除操作がより効率的に行える ／ 双方向連結リストは、各ノードが次のノードへのポインタに加え前のノードへのポインタも持つため、逆方向への走査や、あるノードの前後のポインタを付け替えるだけで済む削除操作が、単方向連結リストよりも効率的に行えるという利点がある（ただし各ノードが追加のポインタを持つ分メモリ使用量は増える）。
問38. システム開発において、アルゴリズムの計算量を意識することが重要である理由として最も適切なものはどれか。
- A. データ量が将来的に増大した際にも、システムの応答性能を維持できるよう設計するため
- B. 計算量はプログラムの見た目の美しさにのみ関係するため
- C. 計算量を意識してもシステムの性能には一切影響しないため
- D. 計算量は法律上の届出事項であるため
正解: A. データ量が将来的に増大した際にも、システムの応答性能を維持できるよう設計するため ／ システム開発において計算量を意識することは、開発時点では問題にならなくても、将来的にデータ量が増大した際にシステムの応答性能が著しく悪化することを防ぐために重要である。小規模なテストデータでは問題が顕在化しないため、設計段階での考慮が特に重要となる。
問39. 既にほぼ整列済みのデータに対して整列アルゴリズムを選択する際、最も適した選択として妥当なものはどれか。
- A. 挿入ソート（ほぼ整列済みのデータに対しては高速に動作するため）
- B. 常にクイックソート（データの状態に関わらず必ず最速であるため）
- C. 常にバブルソート（唯一の整列アルゴリズムであるため）
- D. 整列アルゴリズムの選択に意味はなく、どれを選んでも同じ処理時間になる
正解: A. 挿入ソート（ほぼ整列済みのデータに対しては高速に動作するため） ／ 既にほぼ整列済みのデータに対しては、挿入ソートが適している場合が多い。挿入ソートは最良計算量がO(n)であり、ほぼ整列済みのデータに対しては要素の移動がほとんど発生しないため高速に動作する。一方、クイックソート等は特定のデータパターン（既に整列済み等）によっては最悪計算量O(n^2)に陥る場合がある実装も存在する。
問40. 基本情報技術者試験のアルゴリズムとデータ構造分野で求められる能力として最も適切なものはどれか。
- A. 問題に応じた適切なアルゴリズム・データ構造を選択し、計算量やトレードオフを考慮したうえで効率的なプログラムを設計・実装する能力
- B. 特定のプログラミング言語の文法を暗記するだけの能力
- C. アルゴリズムの理論的な理解を一切必要としない能力
- D. 整列アルゴリズムを1種類だけ知っていれば十分な能力
正解: A. 問題に応じた適切なアルゴリズム・データ構造を選択し、計算量やトレードオフを考慮したうえで効率的なプログラムを設計・実装する能力 ／ 基本情報技術者試験のアルゴリズムとデータ構造分野で求められるのは、単なる知識の暗記ではなく、与えられた問題に応じて適切なアルゴリズム・データ構造を選択し、計算量やメモリ使用量等のトレードオフを考慮したうえで、効率的なプログラムを設計・実装できる実践的な能力である。