応用情報技術者試験科目A 第5回：データ構造・探索・整列

AP科目A・第5回 · 2026年度・シラバスVer.7.2に基づく独立した学習資料です。IPAとの提携はなく、合格を保証しません。シリーズ一覧を見る

改訂日： 2026-10-20 対象範囲： 2026年の試験、IPA 応用情報技術者試験シラバス Ver.7.2 準拠 注意： 受験前に必ず IPA 公式サイトで最新のシラバスと試験情報を確認してください。本記事は学習補助資料であり、合格を保証するものではありません。IPA による確認や推薦を受けたものではありません。

学習目標
用語対照表（韓国語↔日本語↔英語）
計算量の読み方と本記事のコスト前提
データ構造の選択基準とトレードオフ
探索：線形探索と2分探索
整列：アルゴリズムごとの特徴と比較表
例題（4題以上）
オリジナル練習問題4問
計算量クイックシート
よくある間違い
最終セルフチェック
復習の目安（1日／3日／7日）
シラバス対応
出典・参考
範囲の境界と次回予告

1. 学習目標

本回を終えると、次のことができるようになります。

配列・連結リスト・スタック・キュー・木・ヒープの特徴を説明し、状況に合った構造を根拠とともに選べる。
スタック（LIFO）とキュー（FIFO）の状態遷移を1手ずつ正確に追跡できる。
2分探索の前提条件（整列済み＋ランダムアクセス）を説明し、定めた規則に従って比較回数を数えられる。
主要な整列アルゴリズムの最良／平均／最悪の時間計算量、補助領域、安定性、インプレースかどうかを条件付きで述べられる。
Big-O が「実行時間（秒）」ではなく「入力サイズに対する増加のオーダー」であることを区別できる。

2. 用語対照表（韓国語↔日本語↔英語）

韓国語	日本語	英語
배열	配列	array
연결 리스트	連結リスト（リンク付リスト、線形リスト）	linked list
노드	ノード（節、セル）	node
포인터 / 링크	ポインタ / リンク	pointer / link
스택	スタック	stack
큐	キュー（待ち行列）	queue
트리	木（木構造）	tree
루트 / 리프 / 간선	根 / 葉 / 枝	root / leaf / edge
이진 탐색 트리	2分探索木	binary search tree (BST)
균형 트리	バランス木（平衡木）	balanced tree
힙	ヒープ	heap
선형 탐색	線形探索（法）	linear search
이진 탐색	2分探索（法）	binary search
정렬	整列（ソート）	sorting
안정 정렬	安定なソート（安定ソート）	stable sort
제자리 정렬	インプレースなソート（その場での整列）	in-place sort
시간 복잡도	時間計算量	time complexity
공간 복잡도	領域計算量（空間計算量）	space complexity

用語の注意： 「内部ソート」は「データを主記憶上で整列する」という意味であり、「追加メモリをほとんど使わない」インプレース（その場）のソートとは別の概念です。

3. 計算量の読み方と本記事のコスト前提

3.1 Big-O は増加のオーダー

O(n)、O(n²)、O(log n) などの表記は、入力サイズ n が大きくなるにつれて処理量がどのオーダーで増えるかを表します。
実行時間（秒）そのものではありません。同じ O(n log n) でも、定数係数、メモリアクセスのパターン、ハードウェアによって実際の時間は変わります。n が小さいときは O(n²) のアルゴリズムの方が速いこともあります。

3.2 最良・平均・最悪と補助領域

最良（best）： 最も有利な入力での処理量。例：整列済み入力に対する挿入ソート。
平均（average）： 入力の分布を仮定したときの期待処理量。
最悪（worst）： 最も不利な入力での処理量。「保証」を語るときは最悪を見ます。
補助領域（auxiliary space）： 入力そのものを格納する領域を除いて、アルゴリズムが追加で使うメモリ。「インプレースなソート」とは、補助領域が O(1)（またはそれに近い小さな量）のソートを指します。

3.3 本記事のコスト前提

配列：要素がメモリ上に連続して配置され、添字で任意の位置に O(1) でアクセスできるものとします。
連結リスト：各ノードが次の（双方向なら前のノードへのものも）リンクを持ち、k番目のノードへ行くには先頭からリンクをたどる必要があるものとします。
比較1回、交換1回、リンクを1回たどることは、それぞれ定数時間とみなします。

4. データ構造の選択基準とトレードオフ

4.1 配列（array）

添字によるアクセス： O(1)。A[i] のアドレスを直接計算できるためです。
途中への挿入・削除： 通常 O(n)。位置 k に挿入・削除すると、その後ろの要素を1つずつずらす（シフトする）必要があります。
利点： 連続配置のためキャッシュの局所性がよく、逐次処理が実際に速いことが多いです。
動的配列の末尾追加： 償却（amortized）O(1)。容量が尽きるとより大きな領域を確保して全体をコピー（O(n)）するため、毎回 O(1) が保証されるわけではありません。 多数回の追加を平均すると1回あたり O(1) という意味です。
シラバスの用語例：多次元配列、静的配列、動的配列。

4.2 連結リスト（linked list）

位置によるアクセス・探索： O(n)。k番目へ行くには先頭からリンクをたどる必要があります。
挿入・削除： 対象の位置（ノード）と書き換えるべきリンクがすでに分かっている場合に限り O(1)。位置を探す必要があれば、その探索が O(n) です。
- 単方向リストであるノードを削除するには、その直前のノードが分かっている必要があります。双方向リストなら、そのノードさえ分かれば前後のリンクを書き換えて O(1) で削除できます。
欠点： ノードごとにポインタを保持するオーバーヘッドがあり、ノードがメモリ上に散らばるためキャッシュの局所性が弱くなります。
シラバスの用語例：単方向リスト、双方向リスト、環状リスト。

4.3 スタックとキュー

	スタック（stack）	キュー（queue）
原則	LIFO（後入れ先出し）	FIFO（先入れ先出し）
入れる	プッシュ（push）	エンキュー（enqueue）
取り出す	ポップ（pop：最後に入れたもの）	デキュー（dequeue：最初に入れたもの）
用途の例	元に戻す（Undo）履歴、括弧の対応チェック、関数呼出しの管理	プリンタのジョブ待ち行列、要求バッファ、幅優先探索（BFS）

4.4 木、2分探索木、バランス木、ヒープ

木：階層構造。最上位が根、子を持たないノードが葉、ノード同士をつなぐ線が枝です。
2分探索木（BST）： 各ノードについて「左部分木のキー < そのノードのキー < 右部分木のキー」という順序が保たれます（重複キーの扱いは実装による）。
- 通常の2分探索木は挿入順によって偏ることがあります。例：1, 2, 3, 4, 5 の順に挿入すると実質的にリストになり、探索は最悪 O(n)。
- バランス木（平衡2分探索木）（AVL木など）は高さを O(log n) に保つため、探索・挿入・削除が O(log n)。B木も平衡を保つ多分探索木です。
ヒープ： 完全2分木であり、「親 ≥ 子」（最大ヒープ）のような親子間の順序だけを保ちます。
- 最大値の参照 O(1)、挿入・最大値の取出し O(log n) → 優先度付きキューに適しています。
- 全体が整列された列ではありません。 兄弟同士や異なる枝のノード同士の順序は決まっていません。
- そのため、任意のキーの探索には不向きです（一般に O(n)）。

4.5 一言で選ぶ基準

添字アクセスが多い → 配列
手元にある位置での挿入・削除が多い → （双方向）連結リスト
最も新しいものから処理 → スタック／到着順に処理 → キュー
優先度が最も高いものを繰り返し処理 → ヒープ
キーの順序を保ちつつ探索・更新が多い → バランス木

5. 探索

5.1 線形探索（linear search）

先頭から1つずつ比較します。整列は不要です。
時間計算量：最悪 O(n)、平均も O(n)。
連結リストにもそのまま適用できます。

5.2 2分探索（binary search）

前提条件は2つ：
1. 探索範囲が整列済みであること。
2. 中央の位置に直接（ランダム）アクセスできること（配列のように添字で O(1) アクセス）。
比較のたびに範囲が半分になるため O(log n)。
整列済みの連結リストであっても、自動的に O(log n) にはなりません。 中央のノードへ行くにはリンクをたどる必要があり、移動量はおおよそ n/2 + n/4 + … で合計 O(n) になります。比較回数が log オーダーでもアクセスのコストが O(n) なので、利点が失われます。

5.3 本記事の比較回数の規則（例題・問題共通）

正確な回数を数える前に、規則を定めます。

線形探索： 要素1つと目標値を比較することを1回と数えます。整列済み配列であっても「目標より大きい値が出たら打ち切る」という早期終了は行わない基本形で数えます。
2分探索： 添字は0から、最初は low = 0、high = n − 1。中央は mid = ⌊(low + high) / 2⌋（小数点以下切捨て）。A[mid] と目標値を比較して「等しい／小さい／大きい」を判定することを 1回（1プローブ） と数えます。
- 等しければ終了、A[mid] < 目標 なら low = mid + 1、A[mid] > 目標 なら high = mid − 1。low > high になったら「見つからない」で終了します。
- 参考：教材によっては「等しいか」と「小さいか」を別々の2回と数えることもあるため、試験では問題文の規則を優先してください。
この規則では、要素数 n の配列に対する2分探索の最大プローブ数は ⌊log₂ n⌋ + 1 です。

5.4 ハッシュ表探索についての短いメモ

シラバスの同じ項目には、ハッシュ表探索法とシノニム（衝突）対策も用語例として挙げられています。ハッシュ関数がキーを均等に分散し、負荷率が低く保たれていれば平均的に O(1) に近くなりますが、衝突が一箇所に集中すると最悪 O(n) まで悪化しえます。衝突対策にはチェイン法、オープンアドレス法などがあります。本回ではここまでにとどめます。

6. 整列

6.1 アルゴリズムごとの要点

バブルソート： 隣接する2要素を比較・交換するパスを繰り返します。1パスごとに残り範囲の最大値が末尾へ移動します。「交換が1回もなければ終了」というフラグ（早期終了）を設けた場合に限り、整列済み入力で最良 O(n)。平均・最悪 O(n²)。安定、インプレース。
選択ソート： 残り範囲の最小値を探して先頭と交換します。入力によらず比較回数が n(n−1)/2 なので、すべての場合で O(n²)。離れた要素同士を交換するため一般に不安定。インプレース。
挿入ソート： 整列済みの前方部分に、次のキーを適切な位置へ挿入します。標準的な実装で、整列済みまたはほぼ整列済みの入力なら最良 O(n)。平均・最悪 O(n²)。安定、インプレース。
シェルソート： 一定の間隔（ギャップ）だけ離れた要素同士で挿入ソートを行い、間隔を徐々に縮めて最後に間隔1で仕上げる挿入ソート系の方法です。時間計算量は間隔列によって変わり、1つの普遍的な上界では述べられません。 一般に不安定。
マージソート： 整列済みの小さなまとまり（ラン）を2つずつ併合して大きくしていきます。すべての場合で O(n log n)。安定。配列での典型的な実装では O(n) の補助領域が必要です。
クイックソート： ピボットを基準に小さい側と大きい側に分割する処理を繰り返します。平均 O(n log n)、最悪 O(n²)（例：整列済み入力で常に末尾をピボットに選ぶ場合）。一般に不安定。領域は実装・再帰スタック・ピボット戦略によって異なります（分割自体はインプレースで行えますが、呼出しスタックは平均的に O(log n)、単純な実装の最悪時には O(n) まで使われることがあります）。
ヒープソート： 配列を最大ヒープにしたうえで、根（最大値）を末尾と交換してヒープを再構成することを繰り返します。O(n log n)。インプレース。一般に不安定。

6.2 比較表

アルゴリズム	最良	平均	最悪	補助領域	安定性	インプレース
バブル（早期終了あり）	O(n)	O(n²)	O(n²)	O(1)	安定	はい
選択	O(n²)	O(n²)	O(n²)	O(1)	一般に不安定	はい
挿入（標準実装）	O(n)	O(n²)	O(n²)	O(1)	安定	はい
シェル	間隔列に依存	間隔列に依存	間隔列に依存	O(1)	一般に不安定	はい
マージ（配列実装）	O(n log n)	O(n log n)	O(n log n)	O(n)	安定	いいえ（典型的な実装）
クイック	O(n log n)	O(n log n)	O(n²)	実装・スタック・ピボット戦略に依存	一般に不安定	分割はインプレース可能
ヒープ	O(n log n)※	O(n log n)	O(n log n)	O(1)	一般に不安定	はい

※ キーがすべて異なる場合を仮定。早期終了フラグのないバブルソートは最良でも O(n²) です。

6.3 安定性とは

同じキーを持つ要素同士の元の相対順序が、整列後も保たれるソートを安定なソートといいます。例：選択ソートで [2a, 2b, 1]（a、b は元の順序を示す印）を整列すると、最小値 1 を先頭の 2a と交換して [1, 2b, 2a] になります。2a と 2b の順序が入れ替わったので、この入力に対して選択ソートは不安定です。

7. 例題

例題1：状況に応じたデータ構造の選択

状況	選択	理由
センサー値を末尾に追加し続け、「k番目の値」を頻繁に読む	動的配列	添字アクセス O(1)、末尾追加は償却 O(1)
エディタの「元に戻す」	スタック	最も新しい操作から戻す（LIFO）
プリンタのジョブを到着順に処理	キュー	FIFO
緊急度が最も高い患者から繰り返し処理し、随時新しい患者が加わる	ヒープ（優先度付きキュー）	挿入・最大値の取出し O(log n)
会員IDの順序を保ちつつ探索・追加・削除が多く、範囲検索も必要	バランス木	探索・更新 O(log n)、中間順の巡回で順序どおりに列挙可能
カーソルが指すノードはすでに分かっており、その位置での挿入・削除が多い	双方向連結リスト	ノードとリンクが分かっているので O(1)

例題2：スタックとキューの状態遷移

同じ順序で A、B を入れて1つ取り出し、C、D を入れて2つ取り出します。状態の左側が「先に入った側」です。

スタック（右端が top）

手順	操作	取り出した値	状態
0	（開始）	–	[ ]
1	push A	–	[A]
2	push B	–	[A, B]
3	pop	B	[A]
4	push C	–	[A, C]
5	push D	–	[A, C, D]
6	pop	D	[A, C]
7	pop	C	[A]

取り出した順：B, D, C。残り：[A]。

キュー（左端が先頭）

手順	操作	取り出した値	状態
0	（開始）	–	[ ]
1	enqueue A	–	[A]
2	enqueue B	–	[A, B]
3	dequeue	A	[B]
4	enqueue C	–	[B, C]
5	enqueue D	–	[B, C, D]
6	dequeue	B	[C, D]
7	dequeue	C	[D]

取り出した順：A, B, C。残り：[D]。

例題3：線形探索と2分探索

整列済み配列（添字 0〜9、n = 10）：

添字	0	1	2	3	4	5	6	7	8	9
値	3	8	12	17	21	26	30	34	41	47

規則は 5.3 節と同じです。

(a) 34 を探す

線形探索：3, 8, 12, 17, 21, 26, 30, 34 → 8回（添字7で発見）。
2分探索：

プローブ	low	high	mid	A[mid]	判定
1	0	9	4	21	21 < 34 → low = 5
2	5	9	7	34	発見

→ 2回。

(b) 10 を探す（存在しない値）

線形探索：早期終了のない基本形なので10個すべてと比較 → 10回の後「見つからない」。
2分探索：

プローブ	low	high	mid	A[mid]	判定
1	0	9	4	21	21 > 10 → high = 3
2	0	3	1	8	8 < 10 → low = 2
3	2	3	2	12	12 > 10 → high = 1
–	2	1	–	–	low > high → 見つからない

→ 3回。

(c) 最悪の場合： n = 10 なら ⌊log₂ 10⌋ + 1 = 3 + 1 = 4回。例：47 を探すと mid = 4（21）、7（34）、8（41）、9（47）で4回。

例題4：整列パスの追跡

入力：[5, 2, 9, 1, 6]（昇順）。

(a) バブルソート — 左から隣接ペアを比較し、左が大きければ交換。比較1回 = 隣接する2要素の比較1回。

パス1（比較4回）：

比較ペア	交換？	結果
(5, 2)	はい	[2, 5, 9, 1, 6]
(5, 9)	いいえ	[2, 5, 9, 1, 6]
(9, 1)	はい	[2, 5, 1, 9, 6]
(9, 6)	はい	[2, 5, 1, 6, 9]

→ 比較4回、交換3回。最大値 9 が末尾に確定。

パス2（確定した末尾を除いて比較3回）：(2, 5) 交換なし → (5, 1) 交換 [2, 1, 5, 6, 9] → (5, 6) 交換なし。比較3回、交換1回。

パス3（比較2回）：(2, 1) 交換 [1, 2, 5, 6, 9] → (2, 5) 交換なし。比較2回、交換1回。

パス4（比較1回）：(1, 2) 交換なし。

合計：比較 4 + 3 + 2 + 1 = 10回（= n(n−1)/2）、交換 5回。参考：整列済みの5要素の入力なら、早期終了フラグがある場合はパス1で比較4回（= n − 1）、交換0回で終了します。

(b) 挿入ソート — 同じ入力。比較1回 = 取り出したキーと整列済み部分の要素1つとの比較。配列の先頭に達して止まることは比較として数えません。「移動」= 要素を右へ1つずらすこと。

手順	キー	比較の内容	比較	移動	結果
1	2	5 > 2（移動）、先頭に到達	1	1	[2, 5, 9, 1, 6]
2	9	5 > 9？いいえ → 停止	1	0	[2, 5, 9, 1, 6]
3	1	9 > 1、5 > 1、2 > 1（すべて移動）、先頭に到達	3	3	[1, 2, 5, 9, 6]
4	6	9 > 6（移動）、5 > 6？いいえ → 停止	2	1	[1, 2, 5, 6, 9]

合計：比較 7回、移動 5回。バブルの交換5回と挿入の移動5回は、どちらも入力の転倒数（(5, 2)、(5, 1)、(2, 1)、(9, 1)、(9, 6) の5組）と一致します。「等しければ移動しない（> で比較する）」規則により、挿入ソートは安定です。

(c) マージソートのラウンド — 入力 [6, 3, 8, 1, 7, 2, 5, 4]（n = 8）。長さ1のランから始め、隣り合う2つのランを併合します。比較1回 = 2つのランの先頭要素同士の比較1回。片方のランが尽きたら、残りは比較なしでコピーします。

ラウンド	結果	比較回数
1（1+1 → 2）	[3, 6] [1, 8] [2, 7] [4, 5]	1 + 1 + 1 + 1 = 4
2（2+2 → 4）	[1, 3, 6, 8] [2, 4, 5, 7]	3 + 3 = 6
3（4+4 → 8）	[1, 2, 3, 4, 5, 6, 7, 8]	7

合計比較 17回。ラウンド数は log₂ 8 = 3 で、各ラウンドで8要素すべてを移すため、全体の処理量は n log n のオーダーになります。併合結果を格納する別の配列が必要なので、補助領域は O(n) です。

8. オリジナル練習問題4問

以下の4問はすべて本記事のために独自に作成したオリジナル問題であり、過去問題は使用していません。選択肢の記号は IPA の試験形式に合わせてア・イ・ウ・エを用います。

問1（データ構造の選択）

要素数 n が大きく、次の2つの操作がどちらも頻繁に実行される。各操作の最悪時間計算量をいずれも O(log n) 以下にしたい。配列を使う場合、容量はあらかじめ十分に確保されており、再割当ては発生しないものとする。

新しい要素（優先度の値を含む）を追加する。
現時点で優先度が最も高い要素を取り出す。

最も適切なデータ構造はどれか。

ア整列していない配列（末尾に追加）
イ優先度の降順に整列しておく単方向連結リスト
ウ 2分ヒープ（最大ヒープ）
エキュー（FIFO）

正解：ウ

解説：

ア：追加は末尾に入れるので O(1) だが、最大値を取り出すには全体を走査する必要があり O(n)。条件を満たさない。
イ：取出しは先頭ノードを外すので O(1) だが、追加時に適切な位置を探してリンクをたどる必要があり最悪 O(n)。条件を満たさない。
ウ：追加は末尾に置いて上へ移動させ（高さは最大 ⌊log₂ n⌋）O(log n)、取出しは根を外して下方向に再構成し O(log n)。両方の操作が条件を満たす。正解。
エ：FIFO なので取り出されるのは「最初に入った要素」であり、優先度が最も高い要素ではない。優先度で選ぶには全体を走査する必要があり O(n)。条件を満たさない。

問2（スタック・キューの状態遷移）

空のスタック S と空のキュー Q がある。次の操作を順に実行する。

S に 1 を push
S に 2 を push
S に 3 を push
S から pop した値を Q に enqueue
S から pop した値を Q に enqueue
S に 4 を push
S から pop した値を Q に enqueue

その後、Q が空になるまで dequeue を繰り返す。取り出される値の順序はどれか。

ア 4, 2, 3
イ 3, 2, 4
ウ 1, 2, 3
エ 3, 2, 1

正解：イ

解説（状態の追跡）：

手順	S（右が top）	Q（左が先頭）
1〜3	[1, 2, 3]	[ ]
4	[1, 2]（3 を pop）	[3]
5	[1]（2 を pop）	[3, 2]
6	[1, 4]	[3, 2]
7	[1]（4 を pop）	[3, 2, 4]

Q から dequeue すると入れた順に 3, 2, 4。S には 1 が残ります。

ア 4, 2, 3：Q を LIFO のように扱い、最後に入れたものから取り出した誤り。
イ 3, 2, 4：上の追跡結果と一致。正解。
ウ 1, 2, 3：S を FIFO のように扱った誤り。（そうすると手順4・5で 1、2 を取り出し、手順6の後 S = [3, 4] から手順7で 3 を取り出して Q = [1, 2, 3] になります。）
エ 3, 2, 1：手順6の push 4 を無視する、または手順7の後に実行したと誤解し、手順7で 1 を取り出した誤り。

問3（2分探索の条件と比較回数）

次の配列 B（添字 0〜14、n = 15）から 51 を2分探索する。規則は 5.3 節と同じ（mid = ⌊(low + high) / 2⌋、A[mid] との3方向の判定1回を1回と数える）とする。

添字	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
値	4	9	13	18	22	27	31	36	40	45	51	56	62	68	75

比較回数と2分探索の適用条件をいずれも正しく表したものはどれか。

ア 3回。データが整列済みでありさえすれば、連結リストでも同じ効率で適用できる。
イ 4回。データが整列されていない配列にも適用できる。
ウ 11回。データが整列済みである必要がある。
エ 4回。データが整列済みであり、かつ中央の位置に直接アクセスできる必要がある。

正解：エ

解説（追跡）：

プローブ	low	high	mid	B[mid]	判定
1	0	14	7	36	36 < 51 → low = 8
2	8	14	11	56	56 > 51 → high = 10
3	8	10	9	45	45 < 51 → low = 10
4	10	10	10	51	発見

→ 4回。（n = 15 の最大プローブ数 ⌊log₂ 15⌋ + 1 = 4 とも一致。）

ア：回数が誤り（⌊log₂ 15⌋ = 3 を回数と取り違えた値）。また、連結リストでは中央のノードに O(1) でアクセスできず、アクセスのコストが O(n) になるため「同じ効率」ではない。
イ：回数は正しいが、整列されていない配列では「半分を捨てる」判断が成り立たないため、2分探索は使えない。
ウ：11回は、線形探索で添字10に到達するまでの比較回数（4, 9, …, 51 の11個）であり、2分探索の回数ではない。
エ：回数4回と2つの条件（整列済み、直接アクセス）がいずれも正しい。正解。

問4（整列の動作・計算量・安定性）

整列アルゴリズムに関する記述として、適切なものはどれか。

ア標準的な実装の挿入ソートは、すでに昇順に整列された n 個のデータを昇順に整列するとき、キーの比較が n − 1 回であり、安定なソートである。
イクイックソートは、ピボットをどのように選んでも最悪時間計算量が O(n log n) である。
ウ選択ソートは、整列済みのデータに対しては O(n) で終了する。
エヒープソートは安定なソートであり、入力と同じ大きさの補助配列（O(n)）を必要とする。

正解：ア