仮の宿 学習室 資格 基本情報技術者 合格ラボ アルゴリズムとデータ構造 基本情報技術者 FUNDAMENTAL IT ENGINEER
アルゴリズムとデータ構造
講義 5 本・確認問題 45 問 ｜ 本試験では「科目A テクノロジ」（41問）の一部 ｜ 最終更新 2026-09-24
この章で学ぶこと 基本となるデータ構造を「取り出し方が速いか、出し入れが速いか」という物差しで整理します。 階層をもつデータを扱う木構造を、2分探索木・ヒープ・B木という代表例と3つの走査順序で押さえます。 代表的な探索法3つと整列法7つを、手順・計算量・安定性の3点で比べられるようにします。 オーダ記法でアルゴリズムの伸び方を読み、再帰と代表的な設計技法・グラフ探索まで一気に整理します。 変数のスコープや引数の渡し方といった共通の考え方と、主な言語・記述形式の違いを押さえます。 1. 配列・リスト・スタック・キュー・ハッシュ表
基本となるデータ構造を「取り出し方が速いか、出し入れが速いか」という物差しで整理します。
配列は同じ型のデータを連続した領域に並べたものです。先頭アドレスと添字から要素の位置を計算で求められるので、何番目の要素でも一定時間 O(1) で読み書きできます。その代わり途中への挿入や削除は後ろの要素をすべてずらす必要があり、要素数に比例する時間 O(n) がかかります。大きさをあらかじめ決めておく必要がある点も制約です。擬似言語では配列の要素番号は1から始まり、a[1] が先頭、長さは「aの要素数」で表します。
リストは、各要素（節）が「値」と「次の節の位置を指すポインタ」を持つ構造です。次だけを指すものが単方向リスト、前と次の両方を指すものが双方向リスト、末尾が先頭を指して輪になっているものが環状リストです。挿入や削除はポインタを付け替えるだけなので、場所さえ分かっていれば要素数に関係なく一定時間で済みます。反面「n番目の要素」を得るには先頭から順にたどるしかなく O(n) かかります。配列とリストは、参照の速さと出し入れの速さのトレードオフだと覚えてください。
スタックは後入先出（LIFO：Last In First Out）で、push で積み、pop で最後に積んだものから取り出します。関数呼出しの戻り番地や局所変数の管理、再帰、逆ポーランド記法の計算に使われます。キューは先入先出（FIFO：First In First Out）で、enqueue で末尾に入れ、dequeue で先頭から取り出します。プリンタの待ち行列や幅優先探索が代表例です。キューを配列で作るときは、末尾まで来たら先頭に戻る環状バッファ（リングバッファ）にすると、領域を無駄にせず繰り返し使えます。
ハッシュ表は、鍵をハッシュ関数に通して得た値をそのまま格納位置にする構造です。理想的には1回の計算で目的の要素に届くので、探索・挿入・削除がいずれも平均 O(1) になります。異なる鍵が同じ位置に割り当てられる衝突（シノニム）は原理的に避けられないため、同じ位置の要素を線形リストでつなぐチェイン法（連鎖法）か、空きが見つかるまで別の位置を順に調べるオープンアドレス法（線形探査法など）で対処します。表の占有率が上がるほど衝突が増え、最悪では O(n) まで劣化します。
基本データ構造の比較（nは要素数。計算量は代表的な場合） データ構造 取り出し方 k番目の参照 挿入・削除 主な用途 配列 添字で直接指定 O(1) O(n)（後続をずらす） 表・行列、添字計算が効く処理 単方向リスト 先頭から順にたどる O(n) O(1)（位置が既知なら） 件数が増減するデータの管理 双方向リスト 前後どちらからもたどれる O(n) O(1)（前の節を探す必要なし） 履歴の前後移動、エディタ 環状リスト 末尾の次が先頭に戻る O(n) O(1) ラウンドロビン、バッファ管理 スタック 後入先出（LIFO） 頂上のみ push/pop とも O(1) 関数呼出し、再帰、逆ポーランド記法 キュー 先入先出（FIFO） 先頭のみ enqueue/dequeue とも O(1) 待ち行列、幅優先探索 ハッシュ表 鍵から位置を計算 O(1)（平均） O(1)（平均） 辞書、索引、重複チェック
スタックの push / pop と操作の追跡
スタックは配列 stack と頂上位置 top で実現できる push(v): top ← top + 1 ; stack[top] ← v pop(): v ← stack[top] ; top ← top - 1 ; return v 操作: push(1) push(2) pop push(3) push(4) pop pop push(5) pop pop 操作 stack（下→上） 取り出した値 push(1) 1 push(2) 1 2 pop 1 2 push(3) 1 3 push(4) 1 3 4 pop 1 3 4 pop 1 3 push(5) 1 5 pop 1 5 pop （空） 1 取り出された順序 = 2, 4, 3, 5, 1 用語 配列 同じ型の要素を連続した領域に並べたデータ構造。先頭アドレスと添字から要素の位置を計算できるため、何番目の要素でも一定時間で参照できる。一方で途中への挿入・削除は後続要素の移動を伴い、要素数に比例する時間がかかる。 単方向リスト 各節が値と「次の節を指すポインタ」だけを持つ線形リスト。挿入・削除はポインタの付け替えだけで済むが、たどれる向きが一方向なので、ある節を削除するにはその1つ前の節を先頭から探し直す必要がある。 双方向リスト 各節が前の節と次の節の両方を指すポインタを持つ線形リスト。前後どちらの向きにもたどれ、ある節を指すポインタさえあれば前の節を探さずに削除できる。ポインタを2本持つぶん記憶領域は多く必要になる。 環状リスト 末尾の節のポインタが先頭の節を指し、輪になっている線形リスト。終端がないので、決まった順番で処理を回し続けるラウンドロビン方式のスケジューリングやバッファ管理に向く。たどり続けると無限に回るため停止条件が必要。 スタック 後入先出（LIFO）でデータを出し入れするデータ構造。push で頂上に積み、pop で頂上から取り出す。関数呼出し時の戻り番地や局所変数の退避、再帰処理、逆ポーランド記法の計算などに使われる。 キュー 先入先出（FIFO）でデータを出し入れするデータ構造。enqueue で末尾に加え、dequeue で先頭から取り出す。プリンタの印刷待ち、通信のバッファ、グラフの幅優先探索など、到着順に処理したい場面で使う。 ハッシュ関数 鍵から格納位置（ハッシュ値）を求める関数。鍵を表の大きさで割った余りを使う方法が代表的。値が表全体に均等に散らばるほど衝突が減り、探索が平均一定時間に近づく。 衝突（シノニム） 異なる鍵が同じハッシュ値になり、格納位置がぶつかること。対処法として、同じ位置の要素を線形リストでつなぐチェイン法（連鎖法）と、空いている別の位置を順に探すオープンアドレス法（線形探査法など）がある。 例題
例題：要素数 n の配列の先頭に新しい要素を1つ挿入するには、何回の要素移動が必要か。
答えと考え方 既にある n 個の要素をすべて1つずつ後ろへずらすので n 回。末尾への追加なら0回で済む。同じことを単方向リストで行うと、新しい節の next を旧先頭に向け、先頭ポインタを新しい節に付け替えるだけなので、要素数に関係なく一定時間で終わる。
例題：ハッシュ表で衝突が起きたとき、チェイン法とオープンアドレス法はどう違うか。
答えと考え方 チェイン法は同じハッシュ値の要素を線形リストでつなぐので、表の大きさを超える件数でも格納でき、削除も対象の節を外すだけで済む。オープンアドレス法は表の別の空き位置を順に探して入れるため追加の領域が要らないが、占有率が高くなると探索距離が急に伸び、削除した位置に印を残さないと探索が途中で打ち切られてしまう。
出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
2. 木構造・2分探索木・ヒープ
階層をもつデータを扱う木構造を、2分探索木・ヒープ・B木という代表例と3つの走査順序で押さえます。
木は根（ルート）を頂点として枝分かれする構造です。枝の先を子、その元を親と呼び、子を持たない節点を葉といいます。根からその節点までの枝の本数が深さ（レベル）で、木全体の最大の深さが高さです。すべての節点の子が2個以下の木を2分木、どの節点も子を0個か2個だけ持つ木を全2分木、葉が上から隙間なく詰まっている木を完全2分木といいます。根の深さを0とすると、高さ h の完全2分木が持てる節点数は最大 2^(h+1) − 1 個で、逆に n 個の節点を詰めたときの高さはおよそ log2 n になります。
2分探索木は「左部分木のすべての値 ＜ 節点の値 ＜ 右部分木のすべての値」という規則を守った2分木です。探索は根から始め、目的の値が小さければ左、大きければ右へ進むだけなので、木の形が整っていれば O(log n) で見つかります。ところが昇順に並んだデータを順番に挿入すると一直線の木になってしまい、探索は O(n) まで悪化します。これを防ぐため、挿入・削除のたびに回転を行って左右の高さの差を一定以内に保つのが平衡木（AVL木、赤黒木など）です。B木は1つの節点に複数の鍵と複数の子を持たせて木の高さを抑えたもので、1回の読み込みが高くつくディスク上の索引（データベースやファイルシステム）で使われます。
ヒープは「親の値は必ず子の値以上（最大ヒープ）」または「親の値は必ず子の値以下（最小ヒープ）」という条件だけを満たす完全2分木です。左右の子の間に大小の決まりはないので、2分探索木とはまったく別物です。根に最大値（最小値）が来ることを利用して、優先度付きキューやヒープソートに使います。完全2分木なので配列にそのまま詰められ、要素番号が1から始まるなら節点 i の左の子は 2i、右の子は 2i+1、親は i÷2 の商で求まります。挿入は末尾に置いて親と比べながら上へ、根の取り出しは末尾の要素を根へ移して子と比べながら下へ動かすので、どちらも高さに比例して O(log n) です。
木のすべての節点を一度ずつ訪れる操作を走査（トラバーサル）といい、根をどのタイミングで処理するかで3種類に分かれます。前順（先行順・行きがけ順）は「根 → 左 → 右」、中順（中間順・通りがけ順）は「左 → 根 → 右」、後順（後行順・帰りがけ順）は「左 → 右 → 根」です。2分探索木を中順で走査すると値が昇順に並ぶこと、数式を表す木を後順で走査すると逆ポーランド記法（後置記法）になることは試験で頻出なので、必ず結び付けて覚えてください。
木構造の種類と走査法（根の深さを0とする） 区分 名称 決まり・順序 性質と主な用途 木の形 完全2分木 葉が上の段から隙間なく詰まる 高さ h で最大 2^(h+1) − 1 節点。配列で表せる 木の形 全2分木 どの節点も子は0個か2個 葉の数は内部節点の数より1多い 探索 2分探索木 左部分木 ＜ 節点 ＜ 右部分木 整っていれば探索 O(log n)、偏ると O(n) 探索 平衡木（AVL木・赤黒木） 左右の高さの差を一定以内に保つ 回転で形を直し、常に O(log n) を保証 探索 B木 1節点に複数の鍵と子を持つ多分木 木が低いので読み込みが少ない。DBの索引 順序 最大ヒープ 親 ≧ 子（左右の順は問わない） 根が最大値。挿入・取り出しは O(log n) 順序 最小ヒープ 親 ≦ 子 根が最小値。優先度付きキューに使う 走査 前順（行きがけ順） 根 → 左 → 右 木の複製、式の前置（ポーランド）記法 走査 中順（通りがけ順） 左 → 根 → 右 2分探索木では値が昇順に並ぶ 走査 後順（帰りがけ順） 左 → 右 → 根 式の後置（逆ポーランド）記法
2分木の3つの走査順序と、最大ヒープへの要素追加
1 ／ ＼ 2 3 ／ ＼ ＼ 4 5 6 ／ 7 前順（根→左→右）: 1, 2, 4, 5, 7, 3, 6 中順（左→根→右）: 4, 2, 7, 5, 1, 3, 6 後順（左→右→根）: 4, 7, 5, 2, 6, 3, 1 最大ヒープを1から始まる配列で持つと 節点 i の左の子 = 2i / 右の子 = 2i + 1 / 親 = i ÷ 2 の商 {9, 7, 8, 3, 5, 6} に 10 を追加する 末尾に置く : 9, 7, 8, 3, 5, 6, 10 （10は7番目、親は3番目の8） 8 < 10 なので交換: 9, 7, 10, 3, 5, 6, 8 （10は3番目、親は1番目の9） 9 < 10 なので交換: 10, 7, 9, 3, 5, 6, 8 （根に到達して終了） 用語 根・葉・深さ・高さ 木の頂点にあり親を持たない節点が根、子を持たない節点が葉。根からある節点までの枝の本数がその節点の深さ（レベル）で、木の中で最大の深さが木の高さ。根の深さを0と数えるか1と数えるかは問題文で確認する。 完全2分木 根から順に、葉が上の段から左詰めで隙間なく埋まっている2分木。根の深さを0とすると高さ h で最大 2^(h+1) − 1 個の節点を持ち、節点を配列に順番に詰めるだけで親子関係を添字計算で表せる。 2分探索木 どの節点についても、左部分木の値がすべてその節点より小さく、右部分木の値がすべて大きい2分木。探索は根から大小比較で降りるだけで済むが、偏った順序で挿入すると一直線になり探索が要素数に比例してしまう。 平衡木 挿入・削除のたびに部分木を回転させ、左右の高さの差を一定以内に保つ2分探索木。AVL木や赤黒木が代表例で、どんな順序でデータを入れても探索・挿入・削除が O(log n) に収まることが保証される。 B木 1つの節点に複数の鍵と複数の子を持たせた多分木で、すべての葉の深さが等しくなるように保たれる。木の高さが低く抑えられるため読み込み回数が少なく、データベースの索引やファイルシステムで広く使われる。 ヒープ 親と子の間だけに大小関係を課した完全2分木。最大ヒープは親が子以上、最小ヒープは親が子以下で、左右の子の間に決まりはない。根が最大値（最小値）になるので優先度付きキューやヒープソートの土台になる。 木の走査 木のすべての節点を一度ずつ訪れる操作。根を先に処理する前順（根→左→右）、間に処理する中順（左→根→右）、最後に処理する後順（左→右→根）がある。2分探索木の中順走査は昇順、式の木の後順走査は逆ポーランド記法になる。 例題
例題：節点数が1,000個の、形の整った2分探索木を探索するとき、比較は最大でおよそ何回になるか。
答えと考え方 形が整っていれば高さはおよそ log2 1000 ≒ 9.97 なので、根から葉まで降りても比較は10回程度で済む。同じ1,000件を線形探索すると最悪1,000回なので約100分の1。ただし昇順に並んだデータを順に挿入して一直線の木になっていた場合は、最悪1,000回まで悪化する。
例題：2分探索木を中順で走査すると、どんな順序で値が出てくるか。
答えと考え方 「左 → 根 → 右」の順に処理するので、常に昇順（小さい順）に並ぶ。左部分木の値はすべて根より小さく、右部分木の値はすべて根より大きいという規則が、走査の順序とそのまま対応するため。この性質は、整列済みのデータを取り出したいときにそのまま使える。
出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
3. 探索アルゴリズムと整列アルゴリズム
代表的な探索法3つと整列法7つを、手順・計算量・安定性の3点で比べられるようにします。
探索の基本は線形探索です。先頭から順に比べるだけなので並び順は問いませんが、n件のうち目的の値がある場合の平均比較回数は (n+1)/2 回、最悪は n 回で計算量は O(n) です。2分探索は、あらかじめ昇順（または降順）に整列されていることが前提で、中央の要素と比べて探す範囲を毎回半分に絞ります。1回の比較で候補が半分になるので、最大比較回数は ⌊log2 n⌋ + 1 回、計算量は O(log n) です。n が1,000でも10回程度、1,000,000でも20回で済みます。ハッシュ表探索は鍵から位置を直接計算するので平均 O(1) ですが、衝突が集中すると最悪 O(n) になります。
整列アルゴリズムのうち、単純な3つはいずれも二重ループで平均・最悪とも O(n²) です。バブルソート（隣接交換法）は隣り合う要素を比べて大小が逆なら交換することを繰り返し、1回のパスで最大値が末尾に確定します。選択ソートは未整列部分から最小値を選んで先頭と交換するもので、交換回数は n−1 回と少ないのが特徴です。挿入ソートは、整列済み部分の適切な位置に次の要素を差し込むもので、ほぼ整列済みのデータなら最良 O(n) と非常に速くなります。シェルソートは、離れた要素どうしで挿入ソートを行い、間隔を徐々に詰めていく改良版です。
高速な整列は、いずれも平均 O(n log n) です。クイックソートは基準値（枢軸・ピボット）より小さい組と大きい組に分割し、それぞれを再帰的に整列する分割統治法で、平均は最速級ですが、枢軸の選び方が悪く分割が極端に偏ると最悪 O(n²) になります。マージソートは列を半分ずつに分けて整列し、整列済みの2列を併合（マージ）するもので、データの並びによらず常に O(n log n) を保証しますが、併合用に O(n) の作業領域が必要です。ヒープソートは全体をヒープに構成し、根（最大値）を取り出して末尾に置くことを繰り返すもので、こちらも常に O(n log n) で、追加の作業領域はほとんど要りません。
安定な整列とは、値（キー）が等しい要素どうしの元の前後関係が、整列後も保たれる整列のことです。バブルソート・挿入ソート・マージソートは安定ですが、離れた要素を直接入れ替える選択ソート・シェルソート・クイックソート・ヒープソートは安定ではありません。「部門順に並べたあと売上順に並べ替えても、同じ売上なら部門の順序が保たれてほしい」といった多段の並べ替えでは、安定性が実務上の要件になります。
探索・整列アルゴリズムの比較（nはデータ件数） 区分 アルゴリズム 平均計算量 最悪計算量 安定性 特徴 探索 線形探索 O(n) O(n) — 整列不要。平均比較回数は (n+1)/2 回 探索 2分探索 O(log n) O(log n) — 整列済みが前提。最大 ⌊log2 n⌋ + 1 回 探索 ハッシュ表探索 O(1) O(n) — 鍵から位置を計算。衝突が集中すると劣化 整列 バブルソート O(n²) O(n²) 安定 隣接要素を比較交換。実装が最も単純 整列 選択ソート O(n²) O(n²) 不安定 最小値を選んで先頭と交換。交換は n−1 回 整列 挿入ソート O(n²) O(n²) 安定 ほぼ整列済みなら最良 O(n) と速い 整列 シェルソート n^1.25〜n^1.5 程度 O(n²) 不安定 間隔を詰めながら挿入ソートを繰り返す 整列 クイックソート O(n log n) O(n²) 不安定 枢軸で分割する分割統治法。平均は最速級 整列 マージソート O(n log n) O(n log n) 安定 常に O(n log n)。O(n) の作業領域が要る 整列 ヒープソート O(n log n) O(n log n) 不安定 根の取り出しを繰り返す。追加領域が不要
バブルソートの擬似言語と各パス終了時の配列
○bubbleSort(整数型の配列: a) 整数型: i, j, tmp for (i を 1 から aの要素数 - 1 まで 1 ずつ増やす) for (j を 1 から aの要素数 - i まで 1 ずつ増やす) if (a[j] > a[j + 1]) tmp ← a[j] a[j] ← a[j + 1] a[j + 1] ← tmp endif endfor endfor a ← {5, 3, 8, 1, 9, 2} を整列する途中経過 1回目終了: 3, 5, 1, 8, 2, 9 （最大値9が確定） 2回目終了: 3, 1, 5, 2, 8, 9 3回目終了: 1, 3, 2, 5, 8, 9 4回目終了: 1, 2, 3, 5, 8, 9 （以降は交換なし） 用語 線形探索 先頭から順に目的の値と比べていく最も単純な探索法。データが整列されていなくても使えるが、n件の中に目的の値がある場合の平均比較回数は (n+1)/2 回、最悪は n 回で、計算量は O(n) となる。 2分探索 整列済みのデータに対し、中央の要素と比較して探索範囲を毎回半分に絞る探索法。最大比較回数は ⌊log2 n⌋ + 1 回で計算量は O(log n)。データが整列されていることと、添字で直接アクセスできることが前提になる。 バブルソート 隣り合う要素を比較し、大小が逆なら交換することを繰り返す整列法。隣接交換法ともいう。1回の走査ごとに最大値が末尾に確定する。平均・最悪とも O(n²) だが、隣どうししか交換しないため安定な整列である。 選択ソート 未整列部分から最小値（または最大値）を選び、未整列部分の先頭と交換することを繰り返す整列法。比較回数は常に n(n−1)/2 回で O(n²)、交換は n−1 回と少ない。離れた要素を交換するため安定ではない。 挿入ソート 整列済み部分に対して次の要素を正しい位置へ差し込んでいく整列法。平均・最悪は O(n²) だが、既にほぼ整列されているデータでは移動がほとんど起きず最良 O(n) になる。安定な整列である。 シェルソート 一定間隔だけ離れた要素の組ごとに挿入ソートを行い、間隔を徐々に狭めて最後に間隔1で仕上げる整列法。粗い段階で遠くの要素を大きく動かせるため挿入ソートより速いが、離れた要素を動かすので安定ではない。 クイックソート 基準値（枢軸・ピボット）より小さい要素の組と大きい要素の組に分割し、各組を再帰的に整列する分割統治法の整列。平均は O(n log n) と最速級だが、分割が極端に偏ると最悪 O(n²) に悪化する。安定ではない。 マージソート 列を半分ずつに分割して各々を整列し、整列済みの2列を併合していく整列法。データの並びによらず常に O(n log n) を保証する。併合用に元データと同程度の作業領域を必要とするが、安定な整列である。 ヒープソート データ全体をヒープに構成し、根にある最大値を取り出して未整列部分の末尾に置く操作を繰り返す整列法。常に O(n log n) で、配列内で処理できるため追加領域がほとんど要らない。安定ではない。 安定な整列 キーの値が等しい要素どうしの元の並び順が、整列後も保たれる整列のこと。バブル・挿入・マージは安定、選択・シェル・クイック・ヒープは安定でない。段階的に並べ替える処理では安定性が要件になる。 例題
例題：1,000,000件の整列済みデータを2分探索すると、比較は最大何回か。
答えと考え方 1回の比較で候補が半分になるので、最大比較回数は ⌊log2 n⌋ + 1 回。log2 1,000,000 ≒ 19.93 なので ⌊19.93⌋ + 1 = 20 回。線形探索なら最悪1,000,000回なので、整列しておく価値がよく分かる。
例題：「安定な整列」でないと困るのはどんな場面か。
答えと考え方 先に部門コード順に並べたデータを、次に売上金額の降順に並べ替えるような多段の並べ替え。安定な整列なら売上が同額の行は部門コード順のまま残るが、選択ソートやクイックソートのような不安定な整列だと同額の行の並びが崩れてしまう。
出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
4. 計算量・再帰・アルゴリズム設計技法
オーダ記法でアルゴリズムの伸び方を読み、再帰と代表的な設計技法・グラフ探索まで一気に整理します。
計算量（オーダ）は、データ件数 n が増えたときに手数がどう伸びるかを、係数や定数を無視して表したものです。O(1) は件数によらず一定、O(log n) は件数が2倍になっても手数が1増える程度、O(n) は比例、O(n log n) は比較による整列の理論的な下限、O(n²) は件数が10倍になると手数が100倍、O(2ⁿ) は件数が1増えるだけで手数が倍になり、少し大きいデータで実行不能になります。O(n²) のアルゴリズムで n を k 倍すると時間は k² 倍になる、という比例計算は試験でそのまま問われます。
同じアルゴリズムでも、データの並びによって手数は変わるので、最良・平均・最悪を分けて考えます。線形探索は先頭にあれば1回（最良）、平均 (n+1)/2 回、最悪 n 回。挿入ソートはほぼ整列済みなら O(n)（最良）ですが逆順なら O(n²)。クイックソートは平均 O(n log n) でも、枢軸の選び方が悪く毎回1個ずつしか分けられないと O(n²) になります。マージソートとヒープソートはデータの並びによらず常に O(n log n) で、性能が読みやすいのが利点です。
再帰は、関数が自分自身を呼び出す書き方です。呼出しのたびに戻り番地・引数・局所変数がスタックに積まれるので、再帰の深さに比例した記憶領域を使います。終了条件（基底）を書き忘れたり、引数が基底に近づかなかったりすると、スタック領域を使い切ってスタックオーバフローになります。素朴な再帰でフィボナッチ数を求めると同じ計算を何度も繰り返して指数時間になりますが、一度計算した答えを表に記録して使い回せば O(n) に落ちます。
アルゴリズムの設計技法として、問題を小さく分けて解き結果を併合する分割統治法（マージソート、クイックソート、2分探索）、小さい部分問題の答えを表に残して再利用する動的計画法（フィボナッチ数、ナップサック問題、最長共通部分列）、その場で最良に見える選択を繰り返す貪欲法（ダイクストラ法、ハフマン符号）があります。貪欲法は常に最適解を与えるとは限らない点に注意してください。グラフでは、キューを使って近い頂点から広げる幅優先探索、スタック（再帰）を使って行けるところまで進む深さ優先探索、重みが非負のときに始点からの距離が短い頂点から確定していくダイクストラ法が代表です。
オーダ記法の伸び方と、アルゴリズムの設計技法・グラフ探索 区分 記法・技法 意味・特徴 例／n=1,000のときの手数の目安 オーダ O(1) 件数によらず一定 配列の添字参照、ハッシュ表の平均探索／1 オーダ O(log n) 件数が2倍でも手数は1増える程度 2分探索、平衡木の探索／約10 オーダ O(n) 件数に比例 線形探索、合計値の計算／1,000 オーダ O(n log n) 比較による整列の理論的な下限 マージソート、ヒープソート／約10,000 オーダ O(n²) 件数が10倍で手数は100倍 バブルソート、二重ループ／1,000,000 オーダ O(2ⁿ) 件数が1増えるだけで手数が倍 部分集合の全列挙／事実上計算できない 技法 分割統治法 小さく分けて解き、結果を併合する マージソート、クイックソート、2分探索 技法 動的計画法 部分問題の答えを表に残して再利用する フィボナッチ数、ナップサック問題 技法 貪欲法 その場で最良に見える選択を繰り返す ハフマン符号、ダイクストラ法 グラフ 幅優先探索（BFS） キューを使い、近い頂点から広げる 重みが等しいグラフの最短経路 グラフ 深さ優先探索（DFS） スタック（再帰）で行けるところまで進む 経路の全列挙、閉路の検出 グラフ ダイクストラ法 距離の短い頂点から確定していく 重みが非負の単一始点最短経路
再帰によるフィボナッチ数の計算と、重複する呼出し
○整数型: f(整数型: n) if (n ≦ 2) return 1 endif return f(n - 1) + f(n - 2) f(1)=1 f(2)=1 f(3)=2 f(4)=3 f(5)=5 f(6)=8 f(7)=13 f(8)=21 f(5) の呼出しの様子（同じ計算が何度も現れる） f(5) f(4) f(3) f(2) f(1) f(2) f(3) ← f(3) を2回計算している f(2) f(1) 一度求めた f(k) を表に記録して使い回せば（動的計画法）、 呼出しの回数は n に比例する程度まで減らせる 用語 オーダ記法 データ件数 n が大きくなったときの計算時間や領域の増え方を、定数倍や低次の項を無視して表す記法。O(n²) は n が10倍になれば時間が約100倍になることを意味し、アルゴリズムどうしの規模に対する強さを比較するために使う。 最良・平均・最悪計算量 同じアルゴリズムでもデータの並びによって手数が変わるため、最も都合のよい場合・平均的な場合・最も都合の悪い場合に分けて評価する。クイックソートは平均 O(n log n) だが最悪 O(n²)、挿入ソートは最良 O(n) で最悪 O(n²) となる。 再帰 関数が自分自身を呼び出す手法。呼出しごとに戻り番地・引数・局所変数がスタックに積まれるため、深さに比例した記憶領域を消費する。終了条件（基底）が正しくないと呼出しが止まらず、スタックオーバフローを起こす。 分割統治法 問題を同じ形の小さい問題に分割して解き、その結果を併合して元の問題の答えを得る設計技法。マージソート、クイックソート、2分探索が代表例で、多くの場合 O(n log n) や O(log n) といった性能につながる。 動的計画法 小さい部分問題の答えを表に記録し、同じ計算を繰り返さないようにして全体を解く設計技法。素朴な再帰では指数時間になるフィボナッチ数やナップサック問題を、多項式時間で解けるようにする。 貪欲法 各段階でその場で最良に見える選択を繰り返して解を組み立てる設計技法。ダイクストラ法やハフマン符号のように最適解が保証される問題もあるが、一般には局所的な最良の積み重ねが全体の最適解になるとは限らない。 幅優先探索 始点に近い頂点から順に、キューを使って探索を広げるグラフ探索法。辺の重みがすべて等しい場合の最短経路や、最少手数の探索に適する。訪問済みの頂点を記録しておかないと同じ頂点を何度も処理してしまう。 深さ優先探索 進める限り先へ進み、行き止まりになったら直前の分岐点まで戻って別の道を試すグラフ探索法。スタックまたは再帰で実現する。経路の全列挙や閉路の検出、トポロジカルソートなどに使われる。 ダイクストラ法 辺の重みがすべて非負であるグラフで、1つの始点から各頂点への最短経路を求めるアルゴリズム。始点からの距離が最も短い未確定の頂点を確定していく貪欲法で、負の重みがある場合には正しい答えを得られない。 例題
例題：計算量が O(n²) のアルゴリズムが、2,000件のデータを4秒で処理した。5,000件では何秒かかると見積もれるか。
答えと考え方 件数の比は 5000 ÷ 2000 = 2.5 倍。O(n²) なので時間は 2.5² = 6.25 倍になり、4 × 6.25 = 25秒。これが O(n log n) なら 4 × (5000×log2 5000)／(2000×log2 2000) ≒ 11秒程度で済む。
例題：再帰呼出しの深さが増えると何が問題になるか。
答えと考え方 呼出しのたびに戻り番地・引数・局所変数の組（スタックフレーム）がスタックに積まれるため、深さに比例して記憶領域を消費する。深さが想定を超えるとスタック領域を使い切ってスタックオーバフローとなり異常終了する。終了条件を正しく書くこと、深い再帰は繰返し（ループ）に書き換えることが対策になる。
出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
5. プログラミングの基礎と言語・データ記述
変数のスコープや引数の渡し方といった共通の考え方と、主な言語・記述形式の違いを押さえます。
変数には、有効範囲（スコープ）と生存期間があります。関数やブロックの内側で宣言した局所変数は、その内側からしか参照できず、関数を抜けると値も消えます。プログラム全体から参照できる大域変数は便利に見えますが、どこからでも書き換えられるため不具合の原因を追いにくくなり、必要最小限にとどめるのが原則です。同じ名前の局所変数と大域変数があるときは、内側の局所変数が優先されます（大域変数は隠される）。
引数の渡し方には値渡しと参照渡しがあります。値渡しは実引数の値を複製して仮引数に代入するので、呼ばれた側で仮引数を書き換えても呼び出した側の変数は変わりません。参照渡しは変数そのものの位置（アドレス）を渡すので、呼ばれた側での変更が呼び出した側にも及びます。多くの言語で配列やオブジェクトは実質的に参照として渡されるため、関数の中で要素を書き換えると呼び出し元にも反映される点に注意が必要です。
ソースプログラムの実行方式には、全体を一括して機械語に翻訳してから実行するコンパイラ方式と、1文ずつ解釈しながら実行するインタプリタ方式があります。コンパイラ方式は翻訳に時間がかかる代わりに実行が速く、C言語が代表例です。インタプリタ方式は書いてすぐ動かせて試行錯誤しやすい反面、実行は遅くなりがちで、PythonやJavaScript、Rが代表例です。Javaは中間コード（バイトコード）に翻訳し、それを各環境の仮想機械（JVM）が実行するので、環境に依存しにくいという特徴があります。
データの記述形式には目的の違いがあります。HTMLは見出し・段落・リンクといったWeb文書の構造をタグで表すマークアップ言語、XMLはタグを利用者が自由に定義できるマークアップ言語で、データ交換や設定に使われます。JSONは名前と値の組を { } と [ ] で表す軽量な形式でWeb APIの標準的なやり取りに、CSVは値をコンマで区切り1行を1レコードとする表形式データの受渡しに、YAMLは字下げで階層を表し設定ファイルによく使われます。また、機能を外部から呼び出すための取り決めがAPI、よく使う機能をまとめて再利用できるようにした部品群がライブラリ、アプリケーションの骨組みを提供し開発者がその枠に沿って部品を書くのがフレームワークです。
主なプログラム言語とデータ記述形式の特徴 区分 名称 分類・実行方式 主な特徴と用途 言語 C コンパイラ方式 ポインタでメモリを直接扱える。OSや組込みなど速度が要る分野 言語 Java 中間コードに翻訳し仮想機械(JVM)で実行 オブジェクト指向。環境に依存しにくく業務システムやAndroidで広く使う 言語 Python インタプリタ方式 文法が簡潔でライブラリが豊富。データ分析・AI・自動化 言語 JavaScript インタプリタ方式（主にブラウザ上で実行） Webページの動的な操作。Node.jsによりサーバ側でも使う 言語 R インタプリタ方式 統計解析とグラフ描画に特化した言語 マークアップ HTML タグで文書の構造を表す Webページの見出し・段落・リンクなどの構造記述 マークアップ XML タグを利用者が定義できる システム間のデータ交換や設定。構造の妥当性を検証できる データ記述 JSON { } と [ ] で名前と値の組を表す Web APIのデータ交換で最も広く使われる。JavaScript由来 データ記述 CSV 値をコンマで区切り1行を1レコードとする 表形式データの受渡し。表計算ソフトと相性がよい データ記述 YAML 字下げで階層を表す 設定ファイル向け。人が読み書きしやすい
値渡しと参照渡しで結果がどう変わるか
○swapByValue(整数型: x, 整数型: y) /* 値渡し */ 整数型: t t ← x x ← y y ← t ○main() 整数型: a, b a ← 3 b ← 7 swapByValue(a, b) /* ここでの a は 3、b は 7 のまま変わらない */ ○setFirst(整数型の配列: arr) /* 配列は参照として渡される */ arr[1] ← 99 ○main2() 整数型の配列: c c ← {1, 2, 3} setFirst(c) /* ここでの c は {99, 2, 3} に変わっている */ 用語 スコープ（有効範囲） 変数や関数の名前が参照できる範囲。関数やブロック内で宣言した局所変数はその内側だけで有効で、外からは見えない。大域変数はプログラム全体から参照できるが、どこからでも書き換えられるため影響範囲が読みにくくなる。 局所変数と大域変数 局所変数は宣言したブロック内でだけ有効で、通常は関数の実行中だけ存在する。大域変数はプログラム全体で共有され実行中ずっと存在する。同名の変数が両方あるときは内側の局所変数が優先され、大域変数は隠される。 値渡し 実引数の値を複製して仮引数に渡す方式。呼ばれた側で仮引数の値を変更しても、呼び出した側の変数には影響しない。複製が作られるため、大きなデータでは複製のコストがかかる点が欠点。 参照渡し 変数そのものの位置（アドレス）を渡す方式。呼ばれた側で仮引数を通じて値を変更すると、呼び出した側の変数も変わる。大きなデータを複製せずに渡せる利点があるが、意図しない書換えが起こりやすい。 コンパイラ方式 ソースプログラム全体を事前に機械語（目的プログラム）へ翻訳し、その結果を実行する方式。翻訳に時間はかかるが実行は速く、文法の誤りを実行前にまとめて検出できる。C言語などが代表的。 インタプリタ方式 ソースプログラムを1文ずつ解釈しながら実行する方式。翻訳の待ち時間がなくすぐ試せるため試行錯誤に向くが、実行のたびに解釈するため一般に実行速度は遅い。Python、JavaScript、Rなどが代表的。 XML タグの名前を利用者が自由に定義できるマークアップ言語。データそのものと構造を一緒に記述でき、異なるシステム間のデータ交換や設定ファイルに使われる。スキーマによって文書の構造が妥当かどうかを検証できる。 JSON 名前と値の組を { } で、並びを [ ] で表す軽量なデータ記述形式。JavaScriptの記法に由来し、XMLより記述量が少ない。Web APIでサーバとクライアントがデータをやり取りする形式として広く使われている。 API ソフトウェアの機能やデータを外部のプログラムから呼び出すための取り決め（インタフェース）。内部の作りを知らなくても、決められた呼び方と戻り値の形式に従えば機能を利用できる。Web APIはHTTPで呼び出す形式のもの。 フレームワーク アプリケーションの土台となる骨組みと処理の流れをあらかじめ用意した枠組み。開発者はその決まりに沿って部品を書き足す。呼び出す側と呼ばれる側が逆転する点（制御の反転）が、必要なときに呼び出すだけのライブラリとの違い。 例題
例題：大域変数を多用すると、なぜ保守しにくくなるのか。
答えと考え方 プログラムのどこからでも読み書きできるため、値がおかしくなったときに書き換えた箇所を全体から探さなければならない。局所変数なら影響範囲が宣言したブロック内に限られるので、原因の切り分けが早く、部品として他へ流用するのも容易になる。
例題：ライブラリとフレームワークは何が違うか。
答えと考え方 ライブラリは必要なときにこちらから呼び出す部品の集まりで、処理の流れは自分で決める。フレームワークは処理の流れと骨組みが先にあり、開発者はその決められた場所に部品を書き足す形になる。呼ぶ側と呼ばれる側が逆転するので「制御の反転」と呼ばれる。
出典・根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
確認問題（45問） 四肢択一。「正解と解説」を開くと、正解の理由と他の選択肢が違う理由を確認できます。
問1｜配列とリスト
配列と単方向リストの性質を比較した記述のうち、適切なものはどれか。
配列は途中への要素の挿入が要素数によらず一定時間で終わるが、リストは後続要素の移動が必要になる。 配列はk番目の要素を添字の計算だけで一定時間で参照できるが、リストは先頭から順にたどるため要素数に比例した時間がかかる。 リストはk番目の要素を添字の計算だけで参照できるが、配列は先頭からたどる必要がある。 配列もリストも、k番目の要素の参照と途中への要素の挿入がともに一定時間で終わる。 正解と解説 正解：B. 配列はk番目の要素を添字の計算だけで一定時間で参照できるが、リストは先頭から順にたどるため要素数に比例した時間がかかる。 配列は先頭アドレスと添字から位置を計算できるので参照はO(1)、挿入は後続をずらすためO(n)。リストは参照が先頭からたどるのでO(n)、挿入はポインタの付け替えだけでO(1)。したがってk番目の参照が速いのは配列という記述が正しい。ほかの3つは配列とリストの得意・不得意を入れ替えているか、両方が一定時間だとしている点で誤り。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問2｜スタック
スタックの説明として、適切なものはどれか。
最後に格納したデータを最初に取り出すデータ構造であり、関数呼出しの戻り番地の管理などに使われる。 最初に格納したデータを最初に取り出すデータ構造であり、プリンタの印刷待ちの管理などに使われる。 鍵にハッシュ関数を適用して格納位置を決めるデータ構造であり、辞書の実現などに使われる。 各要素が次の要素の位置を指すポインタをもつデータ構造であり、要素数の増減が多いデータの管理に使われる。 正解と解説 正解：A. 最後に格納したデータを最初に取り出すデータ構造であり、関数呼出しの戻り番地の管理などに使われる。 スタックは後入先出（LIFO）で、最後にpushしたものが最初にpopされる。関数呼出しの戻り番地や局所変数の退避、再帰処理に使われる。最初に入れたものから取り出すのは先入先出（FIFO）のキューの説明、ハッシュ関数で位置を決めるのはハッシュ表、ポインタで次の要素をつなぐのは線形リストの説明であり、いずれもスタックではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問3｜スタック追跡
空のスタックに対して、次の順に操作を行った。取り出された値を取り出された順に並べたものはどれか。ここで push(v) は値vを積む操作、pop() は最後に積んだ値を取り出す操作である。
スタックに対する操作の並び
push(1) push(2) pop() push(3) push(4) pop() pop() push(5) pop() pop() 1, 2, 3, 4, 5 2, 4, 5, 3, 1 2, 4, 3, 5, 1 5, 4, 3, 2, 1 正解と解説 正解：C. 2, 4, 3, 5, 1 順に追うと、push(1)(2)で下から1,2、pop()で2が出る。push(3)(4)で1,3,4となりpop()で4、続くpop()で3が出る。push(5)後のpop()で5、最後のpop()で1が出るので2,4,3,5,1。1,2,3,4,5は先入先出のキューの結果、5,4,3,2,1は5個すべてを積んでから取り出した場合の結果、2,4,5,3,1は取り出す順序を取り違えた誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問4｜キュー追跡
空のキューに対して、次の順に操作を行った。取り出された値を取り出された順に並べたものはどれか。ここで enqueue(v) は値vを末尾に加える操作、dequeue() は先頭の値を取り出す操作である。
キューに対する操作の並び
enqueue(1) enqueue(2) dequeue() enqueue(3) enqueue(4) dequeue() dequeue() enqueue(5) dequeue() dequeue() 1, 2, 3, 4, 5 2, 4, 3, 5, 1 1, 2, 4, 3, 5 5, 4, 3, 2, 1 正解と解説 正解：A. 1, 2, 3, 4, 5 キューは先入先出なので、入れた順にそのまま出てくる。実際に追うと1回目のdequeue()で1、2回目で2、3回目で3、4回目で4、5回目で5が取り出され、1,2,3,4,5となる。2,4,3,5,1は同じ操作をスタックで行った場合の結果、5,4,3,2,1はスタックにすべて積んでから取り出した結果であり、1,2,4,3,5は途中の順序を入れ替えた誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問5｜ハッシュ探索
ハッシュ表を用いた探索の説明として、適切なものはどれか。
データが昇順に整列されていることが前提であり、探索範囲を半分ずつ絞り込んでいく。 鍵にハッシュ関数を適用して格納位置を直接求めるので、衝突が少なければ平均的な探索時間はデータ件数によらずほぼ一定になる。 先頭から順に比較するので、平均比較回数はデータ件数のほぼ半分になる。 木構造を根からたどるので、探索時間はデータ件数の対数に比例する。 正解と解説 正解：B. 鍵にハッシュ関数を適用して格納位置を直接求めるので、衝突が少なければ平均的な探索時間はデータ件数によらずほぼ一定になる。 ハッシュ表探索は鍵から格納位置を計算するため、衝突が少なければ件数nに関係なく平均O(1)で目的の要素に到達できる。整列を前提に範囲を半分に絞るのは2分探索、先頭から順に比較するのは線形探索、根からたどってO(log n)になるのは2分探索木の説明であり、いずれもハッシュ表の説明ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問6｜衝突の処理
大きさ10（位置0〜9）のハッシュ表に、ハッシュ関数 h(k) = k mod 10 を用いて鍵を格納する。衝突したときは位置を1ずつ増やして空きを探し、位置9の次は位置0に戻る（オープンアドレス法）。空の表に 45, 35, 27, 55, 17 をこの順に格納したとき、鍵55が格納される位置はどれか。ここで、x mod y は x を y で割った余りを表す。
位置5 位置6 位置7 位置8 正解と解説 正解：D. 位置8 45はh=5で位置5、35もh=5だが位置5が埋まっているので位置6、27はh=7で位置7に入る。55はh=5で、位置5・6・7がいずれも埋まっているため次の空きである位置8に格納される。位置5は45、位置6は35、位置7は27が既に占めているので、これらはいずれも55の格納先にはならない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問7｜双方向リスト
双方向リストが単方向リストに比べて優れている点はどれか。
各節がもつポインタが1本で済むので、必要な記憶領域が少なくて済む。 ある節を指すポインタが分かっていれば、直前の節を先頭から探さずにその節を削除できる。 n番目の要素を添字の計算だけで直接参照できる。 末尾の節から先頭の節へ自動的に戻れるので、終端を意識せずに巡回できる。 正解と解説 正解：B. ある節を指すポインタが分かっていれば、直前の節を先頭から探さずにその節を削除できる。 双方向リストは各節が前と次の両方のポインタをもつので、削除したい節を指すポインタさえあれば直前の節をたどらずに前後をつなぎ直せる。ポインタが1本で領域が少ないのは単方向リストの利点、添字で直接参照できるのは配列の性質、末尾から先頭へ戻れるのは環状リストの性質であり、いずれも双方向リスト固有の利点ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問8｜節の削除
単方向リストにおいて、節pの直後にある節qをリストから取り除く処理はどれか。ここで、各節は値をもつ val と次の節を指す next をもち、末尾の節の next は 未定義の値 とする。
単方向リストの節のつながり
/* 単方向リストのつながり */ … → p → q → r → … p.next は q を指し、q.next は r を指している 取り除きたいのは節 q p ← p.next q.next ← p.next p.next ← q p.next ← p.next.next 正解と解説 正解：D. p.next ← p.next.next qを取り除くには、pのnextをqの次の節rに付け替えればよく、rはp.next.nextで表せるのでp.next ← p.next.nextとなる。p ← p.nextは着目する節を進めるだけでリストは変わらない。q.next ← p.nextはq.nextを自分自身に向けてしまい輪ができる。p.next ← qは元の状態のままで何も変わらない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問9｜先頭挿入
要素数nの配列と、n個の節から成る単方向リストがある。どちらも先頭の位置は分かっているものとする。それぞれの先頭に新しい要素を1つ挿入するときの処理時間の増え方の組合せとして、適切なものはどれか。
配列 O(1)、リスト O(1) 配列 O(1)、リスト O(n) 配列 O(n)、リスト O(1) 配列 O(n)、リスト O(n) 正解と解説 正解：C. 配列 O(n)、リスト O(1) 配列の先頭に挿入するには既存のn個の要素をすべて1つ後ろへずらす必要があるのでO(n)。リストは新しい節のnextを旧先頭に向け、先頭ポインタを付け替えるだけなので要素数に関係なくO(1)。したがって配列O(n)、リストO(1)。配列がO(1)になるのは末尾への追加の場合であり、リストがO(n)になるのはn番目の要素を参照する場合である。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問10｜環状キュー
要素番号が1から始まる配列bufを使って、末尾まで来たら先頭に戻る環状のキューを実現する。rearは最後に格納した位置を表す。次の擬似言語の3行目の□に入れる式として、適切なものはどれか。ここで、x mod y は x を y で割った余りを表す。
環状キューへの格納
○enqueue(整数型の配列: buf, 整数型: v) /* 大域変数 rear は最後に格納した位置。バッファは空きがあるものとする */ rear ← □ buf[rear] ← v (rear + 1) mod bufの要素数 rear mod (bufの要素数 + 1) (rear mod bufの要素数) + 1 (rear + 1) mod (bufの要素数 - 1) 正解と解説 正解：C. (rear mod bufの要素数) + 1 要素番号は1からなので、次の位置は1〜要素数の範囲に収まらなければならない。(rear mod 要素数) + 1 は、要素数が5ならrear=4のとき5、rear=5のとき1となり正しく巡回する。(rear + 1) mod 要素数 はrear=4のとき0となり存在しない要素番号を指す。残る2つは割る数が要素数とずれているため、範囲外の値や同じ位置の重複が生じる。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造）
問11｜2分探索木
2分探索木の説明として、適切なものはどれか。
どの葉についても根からの経路の長さが等しくなるように、挿入や削除のたびに形を整えて保つ木である。 どの節点についても親の値が子の値以上になっている完全2分木であり、根に全体の最大値が来る。 どの節点についても、左部分木にある値はすべてその節点の値より小さく、右部分木にある値はすべてその節点の値より大きい2分木である。 すべての節点が子を0個または2個だけもち、子を1個だけもつ節点が存在しない2分木である。 正解と解説 正解：C. どの節点についても、左部分木にある値はすべてその節点の値より小さく、右部分木にある値はすべてその節点の値より大きい2分木である。 2分探索木は「左部分木＜節点＜右部分木」という大小関係を全節点で満たす2分木で、根から大小比較で降りるだけで探索できる。根から葉までの長さがそろうのはB木などの性質、親が子以上なのは最大ヒープ、子が0個か2個だけなのは全2分木の定義であり、いずれも2分探索木の定義ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問12｜後順走査
次の2分木を後順（左部分木 → 右部分木 → 根の順）で走査したとき、節点を訪れる順序はどれか。
走査の対象となる2分木
1 ／ ＼ 2 3 ／ ＼ ＼ 4 5 6 ／ 7 1, 2, 4, 5, 7, 3, 6 4, 7, 5, 2, 6, 3, 1 4, 2, 7, 5, 1, 3, 6 4, 5, 7, 2, 6, 3, 1 正解と解説 正解：B. 4, 7, 5, 2, 6, 3, 1 後順では、まず根1の左部分木（2を根とする木）を後順で処理する。4、次に5の左の子7、そして5、最後に2となる。続いて右部分木は6のあと3で、最後に根1を訪れるので4, 7, 5, 2, 6, 3, 1となる。1, 2, 4, 5, 7, 3, 6は前順、4, 2, 7, 5, 1, 3, 6は中順の結果である。4, 5, 7, 2, 6, 3, 1は5とその子7の順序を取り違えている。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問13｜走査と順序
2分探索木と走査に関する記述のうち、適切なものはどれか。
中順（左部分木 → 根 → 右部分木）で走査すると、値が昇順に並んで得られる。 前順（根 → 左部分木 → 右部分木）で走査すると、値が昇順に並んで得られる。 どの節点についても、左の子は右の子より大きい値をもつ。 節点数がnであれば、探索に要する比較回数は木の形によらず常にlog2 n 回程度で済む。 正解と解説 正解：A. 中順（左部分木 → 根 → 右部分木）で走査すると、値が昇順に並んで得られる。 2分探索木では左部分木の値がすべて根より小さく右部分木の値がすべて大きいので、左→根→右の中順で訪れれば必ず昇順になる。前順は根が先に出るため昇順にはならない。左の子は右の子より小さいので3つ目は逆。昇順データを順に挿入すると一直線の木になり比較回数は最悪n回になるので、4つ目も誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問14｜節点数
根の深さを0とする。深さ9までの節点がすべて埋まっている完全2分木の節点数は何個か。
512 1024 2047 1023 正解と解説 正解：D. 1023 深さdの段には2のd乗個の節点があるので、深さ0から9までの合計は1+2+4+…+512であり、公比2の等比数列の和2^10 − 1 = 1023個となる。512は深さ9の段だけの節点数、1024は2^10そのもの、2047は深さ10まで埋まっている場合（2^11 − 1）の節点数であり、いずれも深さ9までの合計ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問15｜ヒープ
ヒープの説明として、適切なものはどれか。
どの節点についても、左部分木の値がすべて節点の値より小さく、右部分木の値がすべて大きい完全2分木である。 すべての葉が同じ深さにあり、1つの節点が複数の鍵をもつ多分木である。 どの節点についても親の値が子の値以上（または以下）である完全2分木であり、左右の子の間に大小の決まりはない。 左右の部分木の高さの差が1以下になるように、挿入や削除のたびに回転を行う2分探索木である。 正解と解説 正解：C. どの節点についても親の値が子の値以上（または以下）である完全2分木であり、左右の子の間に大小の決まりはない。 ヒープは親と子の間だけに大小関係を課した完全2分木で、根に最大値（最小値）が来ることを利用して優先度付きキューやヒープソートに使う。左右の子の間に順序はない。左部分木＜節点＜右部分木は2分探索木、葉の深さがそろった多分木はB木、回転で高さの差を保つのはAVL木などの平衡木の説明である。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問16｜ヒープ追加
要素番号が1から始まる配列で最大ヒープ {9, 7, 8, 3, 5, 6} を表している。ここに値10を追加し、末尾に置いてから親と比較して必要なら交換する操作を根に向かって繰り返した。操作後の配列の内容はどれか。
追加前の最大ヒープ
配列（要素番号1〜6）: 9, 7, 8, 3, 5, 6 節点 i の親は i ÷ 2 の商、左の子は 2i、右の子は 2i + 1 9 ／ ＼ 7 8 ／ ＼ ／ 3 5 6 10, 7, 9, 3, 5, 6, 8 9, 7, 8, 3, 5, 6, 10 10, 9, 8, 7, 5, 6, 3 10, 7, 8, 3, 5, 6, 9 正解と解説 正解：A. 10, 7, 9, 3, 5, 6, 8 10を末尾の要素番号7に置くと、その親は7÷2の商=3番目の8である。8＜10なので交換し配列は9, 7, 10, 3, 5, 6, 8となる。10は3番目に移り、その親は1番目の9で、9＜10なので再び交換して10, 7, 9, 3, 5, 6, 8となり根に達して終了する。2番目は交換をまったく行っていない状態、3番目は要素を入れ替えて作った別のヒープでこの手順の結果ではなく、4番目は親を3番目の8ではなく1番目の9と取り違えて交換した誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問17｜B木
B木の説明として、適切なものはどれか。
1つの節点が1個の鍵と2個以下の子をもち、左部分木＜節点＜右部分木の関係を保つ木である。 1つの節点に複数の鍵と複数の子をもたせて木の高さを低く抑えた木であり、データベースの索引などに用いられる。 親と子の間だけに大小関係を課した完全2分木であり、優先度付きキューの実現に用いられる。 末尾の節点が先頭の節点を指して輪になっており、終端を意識せずに巡回できる構造である。 正解と解説 正解：B. 1つの節点に複数の鍵と複数の子をもたせて木の高さを低く抑えた木であり、データベースの索引などに用いられる。 B木は1節点に複数の鍵と子をもたせた多分木で、葉の深さがそろい木の高さが低くなるため、1回の読み込みが高くつくディスク上の索引に適する。1個の鍵と2個以下の子をもつのは2分探索木、親と子だけに大小関係があるのはヒープ、輪になっているのは環状リストの説明であり、いずれもB木ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問18｜挿入と深さ
空の2分探索木に、50, 30, 70, 20, 40, 60, 80, 35 の順に値を挿入した。挿入後の木において、値35をもつ節点の深さはいくつか。ここで、根の深さを1とする。
1 2 3 4 正解と解説 正解：D. 4 根は50（深さ1）。35は50より小さいので左の30（深さ2）へ、35は30より大きいので右の40（深さ3）へ進み、35は40より小さいので40の左の子（深さ4）に入る。したがって深さは4。深さ1は根の50、深さ2は30と70、深さ3は20・40・60・80であり、いずれも35の位置ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問19｜ヒープ計算量
n個の要素をもつヒープに対して、要素を1つ追加する操作と、根の要素を1つ取り出す操作の計算量の組合せとして、適切なものはどれか。
追加 O(1)、取出し O(1) 追加 O(n)、取出し O(n) 追加 O(log n)、取出し O(log n) 追加 O(log n)、取出し O(n) 正解と解説 正解：C. 追加 O(log n)、取出し O(log n) ヒープは完全2分木なので高さはlog2 nに比例する。追加は末尾に置いて親と比べながら根へ向かって上がるだけ、根の取出しは末尾の要素を根に移して子と比べながら下がるだけで、いずれも移動は高さぶんに収まるためO(log n)。どちらもO(1)で済むのは配列の末尾追加などであり、O(n)になるのはヒープ全体を作り直す場合の見積りで、ここでの操作には当てはまらない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（データ構造・木構造）
問20｜2分探索の前提
2分探索を適用するための前提として、適切なものはどれか。
データが線形リストとして格納されていること。 データの件数が2のべき乗であること。 データの鍵に対してハッシュ関数が定義されていること。 データが鍵の値の順に整列されており、任意の位置の要素を直接参照できること。 正解と解説 正解：D. データが鍵の値の順に整列されており、任意の位置の要素を直接参照できること。 2分探索は中央の要素と比較して範囲を半分に絞る方法なので、整列済みであることと、中央の要素を添字で直接参照できることの2つが前提になる。線形リストは中央の要素を直接参照できないため適さない。件数が2のべき乗である必要はなく、ハッシュ関数はハッシュ表探索で使うものであって2分探索には関係しない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問21｜2分探索追跡
次の擬似言語で2分探索を行う。配列aと鍵keyを図のとおりとしたとき、a[mid]としてkeyと比較される要素の値を、比較される順に並べたものはどれか。
2分探索の擬似言語と対象データ
○整数型: binarySearch(整数型の配列: a, 整数型: key) 整数型: lo, hi, mid lo ← 1 hi ← aの要素数 while (lo ≦ hi) mid ← (lo + hi) ÷ 2 の商 if (a[mid] = key) return mid elseif (a[mid] < key) lo ← mid + 1 else hi ← mid - 1 endif endwhile return -1 a ← {3, 8, 12, 17, 21, 26, 30, 35, 41, 48} key ← 26 21, 35, 26 21, 30, 26 26 21, 35, 30, 26 正解と解説 正解：A. 21, 35, 26 最初はlo=1、hi=10でmid=5となりa[5]=21と比較する。21＜26なのでlo=6となりmid=(6+10)÷2の商=8でa[8]=35と比較する。35＞26なのでhi=7となりmid=(6+7)÷2の商=6でa[6]=26と一致して終了する。よって21, 35, 26。21, 30, 26はhiの初期値を要素数−1とした場合、26はmidを切り上げた場合、21, 35, 30, 26はhi ← mid - 1をhi ← midとした場合の結果で、いずれもこの擬似言語とは異なる。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問22｜バブルソート
バブルソートに関する記述のうち、適切なものはどれか。
未整列部分から最小値を選び、未整列部分の先頭と交換することを繰り返す方法であり、最悪計算量はO(n log n)である。 隣り合う2つの要素を比較し、大小の順序が逆であれば交換することを繰り返す方法であり、最悪計算量はO(n²)である。 基準値より小さい組と大きい組に分割し、それぞれを再帰的に整列する方法であり、最悪計算量はO(n log n)である。 隣り合う2つの要素を比較して交換することを繰り返す方法であり、最悪計算量はO(n log n)である。 正解と解説 正解：B. 隣り合う2つの要素を比較し、大小の順序が逆であれば交換することを繰り返す方法であり、最悪計算量はO(n²)である。 バブルソートは隣接する要素を比較交換する方法で、比較回数は最大 n(n−1)/2 回となるため最悪計算量はO(n²)である。最小値を選んで交換するのは選択ソートで、これもO(n²)であってO(n log n)ではない。分割して再帰的に整列するのはクイックソートで、最悪はO(n²)である。手順は正しいが最悪計算量をO(n log n)としている選択肢も誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問23｜バブル追跡
次の擬似言語のバブルソートに a ← {5, 3, 8, 1, 9, 2} を与えた。外側の繰返しでi=1のときの内側の繰返しが終わった直後の配列aの内容はどれか。
バブルソートの擬似言語と対象データ
○bubbleSort(整数型の配列: a) 整数型: i, j, tmp for (i を 1 から aの要素数 - 1 まで 1 ずつ増やす) for (j を 1 から aの要素数 - i まで 1 ずつ増やす) if (a[j] > a[j + 1]) tmp ← a[j] a[j] ← a[j + 1] a[j + 1] ← tmp endif endfor endfor a ← {5, 3, 8, 1, 9, 2} 3, 5, 1, 8, 2, 9 3, 1, 5, 2, 8, 9 1, 3, 2, 5, 8, 9 3, 5, 8, 1, 9, 2 正解と解説 正解：A. 3, 5, 1, 8, 2, 9 jを1から5まで動かすと、5と3を交換して3,5,8,1,9,2、5と8は順序どおりで交換なし、8と1を交換して3,5,1,8,9,2、8と9は交換なし、9と2を交換して3,5,1,8,2,9となる。最大値9が末尾に確定する点が確認できる。3, 1, 5, 2, 8, 9はi=2まで、1, 3, 2, 5, 8, 9はi=3まで進めた状態であり、3, 5, 8, 1, 9, 2は最初の1回だけ交換した途中の状態である。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問24｜選択ソート追跡
配列 {8, 3, 5, 1, 9, 2} を選択ソートで昇順に整列する。未整列部分から最小値を選び、未整列部分の先頭要素と交換する操作を2回終えた直後の配列の内容はどれか。
1, 3, 5, 8, 9, 2 1, 2, 3, 8, 9, 5 1, 2, 5, 9, 8, 3 1, 2, 5, 8, 9, 3 正解と解説 正解：D. 1, 2, 5, 8, 9, 3 1回目は全体の最小値1（4番目）を先頭の8と交換して1, 3, 5, 8, 9, 2となる。2回目は2番目以降の最小値2（6番目）を2番目の3と交換して1, 2, 5, 8, 9, 3となる。1, 3, 5, 8, 9, 2は1回目を終えた状態、1, 2, 3, 8, 9, 5は3回目まで進めた状態、1, 2, 5, 9, 8, 3は交換する相手を取り違えた誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問25｜挿入ソート追跡
次の擬似言語の挿入ソートに a ← {6, 2, 7, 1, 5} を与えた。外側の繰返しでi=4の処理が終わった直後の配列aの内容はどれか。
挿入ソートの擬似言語と対象データ
○insertionSort(整数型の配列: a) 整数型: i, j, v for (i を 2 から aの要素数 まで 1 ずつ増やす) v ← a[i] j ← i - 1 while (j ≧ 1 and a[j] > v) a[j + 1] ← a[j] j ← j - 1 endwhile a[j + 1] ← v endfor a ← {6, 2, 7, 1, 5} 2, 6, 7, 1, 5 2, 6, 1, 7, 5 1, 2, 6, 7, 5 1, 2, 5, 6, 7 正解と解説 正解：C. 1, 2, 6, 7, 5 i=2で2を6の前に入れて2, 6, 7, 1, 5、i=3では7が6より大きいのでそのまま、i=4では1を先頭まで移動させて1, 2, 6, 7, 5となる。2, 6, 7, 1, 5はi=3を終えた状態、1, 2, 5, 6, 7はi=5まで進めて整列が完了した状態、2, 6, 1, 7, 5は1を途中までしか移動させていない誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問26｜安定な整列
安定な整列の説明として、適切なものはどれか。
整列に要する時間が、データの並びによらずほぼ一定である整列。 鍵の値が等しい要素どうしの整列前の並び順が、整列後も保たれる整列。 作業用の記憶領域を追加で必要としない整列。 最悪の場合でも計算量がO(n log n)に収まる整列。 正解と解説 正解：B. 鍵の値が等しい要素どうしの整列前の並び順が、整列後も保たれる整列。 安定な整列とは、鍵が同じ値の要素の相対的な順序が入れ替わらない整列のことで、バブルソート・挿入ソート・マージソートが該当し、選択ソート・シェルソート・クイックソート・ヒープソートは該当しない。実行時間が一定であること、追加領域が不要であること、最悪がO(n log n)であることは、いずれも別の観点の性質であって安定性の定義ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問27｜クイック分割
配列 {4, 9, 2, 7, 5, 1, 8} をクイックソートで昇順に整列する。枢軸（基準値）として5を選んで1回目の分割を行ったとき、枢軸より小さい要素の組に入る要素をすべて挙げたものはどれか。
4, 2, 1 4, 2, 1, 5 9, 7, 8 4, 9, 2 正解と解説 正解：A. 4, 2, 1 枢軸5より小さい要素は4、2、1の3個で、これらが左側の組になる。5より大きい9、7、8は右側の組に入り、枢軸5自身はどちらの組にも属さず位置が確定する。4, 2, 1, 5は枢軸を小さい側に含めてしまった誤り、9, 7, 8は大きい側の組、4, 9, 2は配列の前から3個を並べただけで大小による分割になっていない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問28｜最悪計算量
クイックソート、マージソート、ヒープソートの最悪計算量の組合せとして、適切なものはどれか。
クイック O(n log n)、マージ O(n log n)、ヒープ O(n log n) クイック O(n²)、マージ O(n²)、ヒープ O(n log n) クイック O(n log n)、マージ O(n²)、ヒープ O(n²) クイック O(n²)、マージ O(n log n)、ヒープ O(n log n) 正解と解説 正解：D. クイック O(n²)、マージ O(n log n)、ヒープ O(n log n) クイックソートは平均O(n log n)だが、枢軸の選び方が悪く毎回1個ずつしか分割できないと比較回数がn(n−1)/2に近づき最悪O(n²)になる。マージソートは分割が常に半分ずつ、ヒープソートは高さがlog2 nに収まるので、どちらもデータの並びによらず最悪でもO(n log n)である。クイックをO(n log n)としたりマージ・ヒープをO(n²)としたりする組合せは誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（探索・整列）
問29｜オーダ記法
計算量がO(n²)であるアルゴリズムに関する記述として、適切なものはどれか。ここで、nはデータ件数とする。
データ件数が2倍になると、処理時間もおよそ2倍になる。 データ件数が2倍になっても、処理時間はおよそ1回分増えるだけである。 データ件数が10倍になると、処理時間はおよそ100倍になる。 処理時間はデータ件数によらず、ほぼ一定である。 正解と解説 正解：C. データ件数が10倍になると、処理時間はおよそ100倍になる。 O(n²)は処理時間がnの2乗に比例することを表すので、nが10倍になれば時間は10の2乗=100倍になる。件数に比例して2倍になるのはO(n)、2倍になっても1回分しか増えないのはO(log n)、件数によらず一定なのはO(1)の説明であり、いずれもO(n²)ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問30｜処理時間見積
計算量がO(n²)のアルゴリズムで、2,000件のデータを処理したところ4秒かかった。同じアルゴリズムで5,000件のデータを処理すると、およそ何秒かかると見積もれるか。ここで、処理時間はデータ件数の2乗に比例するものとする。
10秒 16秒 20秒 25秒 正解と解説 正解：D. 25秒 件数の比は5,000÷2,000=2.5倍。処理時間は件数の2乗に比例するので2.5²=6.25倍となり、4×6.25=25秒。10秒は件数に比例（O(n)）とみなして2.5倍した値、20秒は比を5倍と取り違えて比例計算した値、16秒は比を2倍として2乗した値であり、いずれも2.5の2乗を使っていない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問31｜比較回数
1,000,000件の整列済みデータに対して2分探索を行うとき、目的のデータを見つけるまでの比較回数は最大でおよそ何回か。
20回 100回 1,000回 500,000回 正解と解説 正解：A. 20回 2分探索は1回の比較で候補が半分になるので、最大比較回数は⌊log2 n⌋+1回である。log2 1,000,000≒19.93なので約20回。500,000回は線形探索の平均比較回数、1,000回は√1,000,000にあたる値、100回も根拠のない値であり、いずれも2分探索の見積りにはならない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問32｜計算量の比較
nが十分大きいとき、計算量の増え方が小さいものから大きいものへ順に並べたものはどれか。
O(log n) → O(n) → O(n²) → O(n log n) O(log n) → O(n) → O(n log n) → O(n²) O(n) → O(log n) → O(n log n) → O(n²) O(n log n) → O(n) → O(log n) → O(n²) 正解と解説 正解：B. O(log n) → O(n) → O(n log n) → O(n²) nが大きいときの増え方はO(log n)＜O(n)＜O(n log n)＜O(n²)の順になる。O(n log n)はO(n)にlog nを掛けたものなのでO(n)より大きくO(n²)より小さい。O(n²)をO(n log n)より小さいとする並びや、O(n)をO(log n)より小さいとする並びは大小関係が逆になっており誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問33｜再帰の戻り値
次の擬似言語で定義された関数fについて、f(8)の戻り値はどれか。
再帰によって定義された関数f
○整数型: f(整数型: n) if (n ≦ 2) return 1 endif return f(n - 1) + f(n - 2) 13 20 21 34 正解と解説 正解：C. 21 定義に従って小さい方から求めると、f(1)=1、f(2)=1、f(3)=2、f(4)=3、f(5)=5、f(6)=8、f(7)=13、f(8)=f(7)+f(6)=13+8=21となる。13はf(7)、34はf(9)の値であり、1つずれた答えである。20は前2項の和ではなく別の計算をした場合の値で、この定義からは得られない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問34｜再帰とスタック
再帰呼出しを行うプログラムに関する記述のうち、適切なものはどれか。
呼出しのたびに戻り番地・引数・局所変数がスタックに積まれるので、再帰の深さに比例した記憶領域を必要とする。 呼出しのたびに情報がキューに入れられるので、先に呼び出したものから順に処理を再開する。 再帰で書けるアルゴリズムは繰返しでは書けないので、必ず再帰を用いなければならない。 同じ処理を再帰で書き直すと、計算量は必ず繰返しで書いた場合より小さくなる。 正解と解説 正解：A. 呼出しのたびに戻り番地・引数・局所変数がスタックに積まれるので、再帰の深さに比例した記憶領域を必要とする。 再帰呼出しでは呼出しごとにスタックフレームが積まれるため、深さに比例して記憶領域を消費し、深すぎるとスタックオーバフローになる。呼出しの管理に使うのはキューではなくスタックである。再帰で書ける処理は原理的に繰返しでも書けるし、再帰にしたからといって計算量が小さくなるわけではなく、素朴な再帰はむしろ同じ計算を繰り返して遅くなることがある。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問35｜動的計画法
動的計画法の説明として、適切なものはどれか。
その時点で最良に見える選択を繰り返して解を組み立てる方法。 問題を同じ形の小さい問題に分割して解き、その結果を併合して答えを得る方法。 取り得る解をすべて列挙し、その中から条件を満たすものを選ぶ方法。 小さい部分問題の答えを表に記録しておき、同じ計算を繰り返さずに再利用して全体を解く方法。 正解と解説 正解：D. 小さい部分問題の答えを表に記録しておき、同じ計算を繰り返さずに再利用して全体を解く方法。 動的計画法は部分問題の答えを表に残して再利用することで、重複する計算を省く技法であり、素朴な再帰では指数時間になるフィボナッチ数やナップサック問題を現実的な時間で解けるようにする。その場で最良を選ぶのは貪欲法、小さく分けて併合するのは分割統治法、すべて列挙するのは全探索（力任せ法）の説明である。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問36｜最短経路
次の重み付き無向グラフにおいて、頂点Aから頂点Fに至る経路のうち、重みの合計が最小になるものの重みの合計はいくらか。
重み付き無向グラフの辺と重み
辺と重み A — B : 4 A — C : 2 B — C : 1 B — D : 5 C — D : 8 C — E : 10 D — E : 2 D — F : 6 E — F : 3 11 13 14 15 正解と解説 正解：B. 13 A→C→B→D→E→Fをたどると2+1+5+2+3=13で最小になる。14はA→C→B→D→F（2+1+5+6）、15はA→C→E→F（2+10+3）やA→B→D→F（4+5+6）の合計であり、いずれも13より大きい。11になる経路はこのグラフには存在しない。Aから各頂点への最短距離を短い順に確定していけば、C=2、B=3、D=8、E=10、F=13と求まる。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問37｜深さ優先探索
次の無向グラフに対して、頂点Aから深さ優先探索を行う。未訪問の隣接頂点が複数あるときは名前の昇順に選ぶものとするとき、頂点を訪れる順序はどれか。
探索の対象となる無向グラフ
無向グラフの隣接関係（各頂点の隣接頂点を昇順に並べたもの） A : B, C, D B : A, E C : A, E, F D : A, F E : B, C, G F : C, D, G G : E, F A, B, E, C, F, D, G A, B, C, D, E, F, G A, B, E, G, F, C, D A, C, B, E, G, F, D 正解と解説 正解：A. A, B, E, C, F, D, G AからBへ進み、Bの未訪問の隣接頂点Eへ、Eの未訪問の隣接頂点はCとGなので昇順にCへ進む。Cの未訪問はFなのでFへ、Fの未訪問はDとGなのでDへ進み、Dは行き止まりなのでFに戻ってGへ行く。よってA, B, E, C, F, D, Gとなる。A, B, C, D, E, F, Gは幅優先探索の順序、残りの2つは昇順で選ぶ規則に反している。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（アルゴリズム・計算量）
問38｜変数のスコープ
局所変数と大域変数に関する記述のうち、適切なものはどれか。
局所変数はプログラム全体から参照できるので、関数どうしでデータを受け渡すのに適している。 関数の中で宣言した局所変数はその関数の外から参照できないので、影響範囲が限定され保守しやすい。 大域変数は宣言した関数の中でだけ有効であり、その関数を抜けると値は失われる。 同じ名前の局所変数と大域変数があるとき、局所変数が隠されて大域変数が優先される。 正解と解説 正解：B. 関数の中で宣言した局所変数はその関数の外から参照できないので、影響範囲が限定され保守しやすい。 局所変数は宣言したブロックの中だけで有効なので、値がおかしくなったときに調べる範囲が限られ、部品としても流用しやすい。プログラム全体から参照できるのは大域変数、宣言した関数を抜けると失われるのは局所変数の性質であり、2つの選択肢は説明が入れ替わっている。名前が重なった場合に優先されるのは内側の局所変数の側である。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
問39｜引数の渡し方
次の擬似言語で手続mainを実行し終えた時点における、変数a、変数b、配列cの内容の組合せはどれか。ここで、整数型の引数は値渡し、配列は参照として渡されるものとする。
値渡しと参照渡しを含むプログラム
○swapByValue(整数型: x, 整数型: y) 整数型: t t ← x x ← y y ← t ○setFirst(整数型の配列: arr) arr[1] ← 99 ○main() 整数型: a, b 整数型の配列: c a ← 3 b ← 7 c ← {1, 2, 3} swapByValue(a, b) setFirst(c) a=3、b=7、c={99, 2, 3} a=7、b=3、c={99, 2, 3} a=3、b=7、c={1, 2, 3} a=7、b=3、c={1, 2, 3} 正解と解説 正解：A. a=3、b=7、c={99, 2, 3} swapByValueは値渡しなので、複製された仮引数x、yの中身が入れ替わるだけで、呼出し元のaとbは3と7のまま変わらない。一方、配列は参照として渡されるのでsetFirstの中のarr[1] ← 99は呼出し元のcにそのまま及び、c={99, 2, 3}になる。aとbが入れ替わるとする選択肢は値渡しの理解が誤りで、cが変わらないとする選択肢は参照渡しの理解が誤りである。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
問40｜実行方式
コンパイラ方式とインタプリタ方式に関する記述のうち、適切なものはどれか。
コンパイラ方式は1文ずつ解釈しながら実行するので、書き換えた結果をすぐに試せる。 インタプリタ方式はソースプログラム全体を機械語に翻訳してから実行するので、一般に実行速度が速い。 コンパイラ方式は事前に全体を機械語へ翻訳しておくので、インタプリタ方式に比べて一般に実行速度が速い。 インタプリタ方式では翻訳結果の目的プログラムが生成されるので、それを保存して繰り返し実行できる。 正解と解説 正解：C. コンパイラ方式は事前に全体を機械語へ翻訳しておくので、インタプリタ方式に比べて一般に実行速度が速い。 コンパイラ方式は実行前に全体を機械語へ翻訳するので、実行時は翻訳の手間がなく速い。1文ずつ解釈してすぐ試せるのはインタプリタ方式、全体を翻訳してから実行するのはコンパイラ方式であり、2つの選択肢は方式の説明が入れ替わっている。インタプリタ方式は実行のたびに解釈するので、保存して繰り返し実行できる目的プログラムは生成されない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
問41｜言語の特徴
プログラム言語の特徴に関する記述のうち、適切なものはどれか。
Cは統計解析とグラフ描画に特化した言語であり、主にデータ分析の分野で使われる。 Rは中間コードに翻訳されて仮想機械上で実行される言語であり、Androidアプリの開発に広く使われる。 Pythonはコンパイラ方式の言語であり、ポインタでメモリを直接操作できることからOSの記述に使われる。 JavaScriptは主にWebブラウザ上で実行され、Webページの動的な操作に使われる言語である。 正解と解説 正解：D. JavaScriptは主にWebブラウザ上で実行され、Webページの動的な操作に使われる言語である。 JavaScriptはブラウザ上で動作してWebページを動的に操作する言語で、Node.jsによってサーバ側でも使われる。統計解析に特化しているのはCではなくR、中間コードを仮想機械で実行しAndroid開発に使われるのはRではなくJava、ポインタでメモリを直接扱いOSの記述に使われるのはPythonではなくCであり、いずれも言語の対応が入れ替わっている。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
問42｜XML
XMLの特徴として、適切なものはどれか。
あらかじめ決められたタグだけを使って、Webページの見出しや段落などの構造を表す。 利用者がタグを自由に定義でき、データそのものと構造を一緒に記述できるので、システム間のデータ交換に使われる。 値をコンマで区切り、1行を1レコードとして表す表形式データ向けの形式である。 字下げの深さで階層を表すので、設定ファイルとして人が読み書きしやすい。 正解と解説 正解：B. 利用者がタグを自由に定義でき、データそのものと構造を一緒に記述できるので、システム間のデータ交換に使われる。 XMLはタグ名を利用者が自由に定義できるマークアップ言語で、データと構造を一緒に記述でき、スキーマによって構造の妥当性も検証できる。決められたタグでWeb文書の構造を表すのはHTML、コンマ区切りで1行1レコードなのはCSV、字下げで階層を表すのはYAMLの説明であり、いずれもXMLの特徴ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
問43｜JSON
JSONの特徴として、適切なものはどれか。
名前と値の組を { } で、値の並びを [ ] で表す軽量なデータ記述形式であり、Web APIのデータ交換で広く使われる。 タグによって文書の構造を表すマークアップ言語であり、Webページを表示するために用いられる。 1行を1レコードとし値をコンマで区切る形式であり、階層をもつデータをそのまま表すことはできない。 画像や音声を圧縮して格納するための、バイナリ形式のファイル形式である。 正解と解説 正解：A. 名前と値の組を { } で、値の並びを [ ] で表す軽量なデータ記述形式であり、Web APIのデータ交換で広く使われる。 JSONはJavaScriptの記法に由来する軽量なデータ記述形式で、{ } で名前と値の組、[ ] で並びを表し、XMLより記述量が少ないためWeb APIのやり取りに広く使われる。タグで文書構造を表すのはHTML、1行1レコードのコンマ区切りはCSVの説明である。JSONはテキスト形式であり、圧縮したバイナリ形式ではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
問44｜API
APIの説明として、適切なものはどれか。
ソースプログラムを機械語に翻訳するソフトウェアのこと。 アプリケーションの骨組みと処理の流れをあらかじめ用意した枠組みのこと。 ソフトウェアの機能やデータを外部のプログラムから呼び出すための取決め（インタフェース）のこと。 利用者が画面上で操作するためのウィンドウやボタンなどの部品の集まりのこと。 正解と解説 正解：C. ソフトウェアの機能やデータを外部のプログラムから呼び出すための取決め（インタフェース）のこと。 APIは、内部の作りを知らなくても決められた呼び方と戻り値の形式に従えば機能を利用できるようにした取決めであり、HTTPで呼び出すものをWeb APIという。ソースプログラムを機械語に翻訳するのはコンパイラ、骨組みと処理の流れを用意するのはフレームワーク、画面部品の集まりはGUI部品の説明であり、いずれもAPIではない。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
問45｜フレームワーク
ライブラリとフレームワークの違いの説明として、適切なものはどれか。
ライブラリは処理の流れをあらかじめ持ち開発者の書いた部品を呼び出すのに対し、フレームワークは開発者が必要なときに呼び出す部品の集まりである。 ライブラリはソースコードの形でしか配布できないのに対し、フレームワークは実行形式でしか配布できない。 ライブラリは特定のプログラム言語でしか使えないのに対し、フレームワークはどの言語からでも使える。 ライブラリは開発者が必要なときに呼び出す部品の集まりであるのに対し、フレームワークは処理の流れをあらかじめ持ち、開発者が書いた部品を呼び出す。 正解と解説 正解：D. ライブラリは開発者が必要なときに呼び出す部品の集まりであるのに対し、フレームワークは処理の流れをあらかじめ持ち、開発者が書いた部品を呼び出す。 ライブラリは呼びたいときにこちらから呼ぶ部品の集まりで、処理の流れは開発者が決める。フレームワークは骨組みと流れが先にあり、決められた場所に書いた部品がフレームワーク側から呼ばれる（制御の反転）。この関係を逆にした選択肢は誤り。配布形式や対応言語の違いは両者を区別する本質ではなく、いずれも事実に反する。
根拠：IPA 基本情報技術者試験 シラバス Ver.9.2 大分類1：基礎理論 中分類2：アルゴリズムとプログラミング（プログラミング・言語）
演習：この章の問題を解く ランダム出題の演習ツールです（JavaScript が有効な場合に動きます）。上の「確認問題」はそのままでもすべて読めます。
← 前の章：基礎理論 次の章：コンピュータ構成要素 → ※ 解説は学習用の情報提供です。最新の出題範囲・制度は必ずIPAの公式発表をご確認ください。