対応するシラバスの範囲（応用情報技術者試験シラバス Ver.7.2）：大分類「基礎理論」の中分類2「アルゴリズムとプログラミング」
一言で言うと
- リスト・スタック・木などのデータ構造と、探索・整列・再帰のアルゴリズム、プログラム言語の基礎
覚え方の軸
リスト・スタック・キュー
- 配列は「場所が決まっている」、連結リストは「ポインタでつながっている」
- 連結リストの種類は「ポインタの向き」で3つ
- HeadとTailをもつリストの処理量は「追加は先頭も末尾も同じ、削除だけ末尾が重い」
- だからこのリストは「末尾に足して先頭から取る」キュー向き
- 2分木のノードは「自分のデータ＋親・左の子・右の子への3本のポインタ」
- スタックは「積み重ねた皿」、キューは「レジの行列」
- 操作の名前は組で覚える
- 探索との対応
- 関数の呼び出しはスタック
- 逆ポーランド表記は「数字ならPUSH、演算子なら2つPOPして計算してPUSH」
木構造
- 木の用語は「家系図」で覚える
- 完全2分木の公式は「葉＝2のH乗、葉以外＝葉−1」
- 走査は「節を見るタイミング」で3つ
- 2分探索木は「左は小さい、右は大きい」
- 偏りを防ぐのがバランス木
探索アルゴリズム
- 3つの探索法は「1回の比較でどれだけ絞れるか」で並ぶ
- 前提条件の違い
- ハッシュは「ぶつかったとき（シノニム）にどうするか」で2つ
- オーダは「一番増え方の大きい項だけ残す」
整列アルゴリズム
- 速さで2グループ
- 基本3つは「何をするか」の動詞で区別
- 安定かどうかの○×
- 例外を押さえる
- 考え方は3つ
再帰法
- 再帰関数は「止まる条件」と「1つ小さい自分を呼ぶ式」の2つでできている
- 再帰は「下りて行って、帰りに計算する」
- 計算問題は「式に数字を入れて1行ずつ書き下す」だけ
- 木は再帰的な構造なので、再帰と相性がよい
プログラム言語
- プログラム特性は「再〜」の4つを、できることの違いで区別する
- 再入可能の作り方は「手続部分は共有、データ部分はタスクごと」
- 引数の渡し方は「値をコピーするか、アドレスを渡すか」
- 変数の寿命は「プログラムの終わりまで（static）」か「手続の終わりまで（auto）」
- 言語は「何を書くか」で4つ
ページ一覧
| テーマ | 何の話か |
|---|---|
| リスト・スタック・キュー | 配列と連結リストの違い、先頭・末尾での追加・削除の手間、リストで2分木を表す。LIFOのスタックとFIFOのキュー、関数呼び出し、グラフ探索、逆ポーランド表記 |
| 木構造 | 木の用語、完全2分木の公式、走査法（先行・中間・後行）、2分探索木、AVL木・B木 |
| 探索アルゴリズム | 線形探索 O(n)、2分探索 O(log n)、ハッシュ法とシノニム対策、オーダ記法 |
| 整列アルゴリズム | 基本整列法 O(n²)、高速整列法 O(n log n)、安定性、分割統治法 |
| 再帰法 | 自分を呼ぶ関数（階乗、最大公約数）、再帰で2分探索木を探す |
| プログラム言語 | 再入・再帰・再使用・再配置、値呼出しと参照呼出し、言語の4分類、Java・XML用語 |