平成21年度 秋期 応用情報技術者試験 午前 問5
n個の要素x₁，x₂，…，xₙから成る連結リストに対して，新たな要素xₙ₊₁の末尾への追加に要する時間をf(n)とし，末尾の要素xₙの削除に要する時間をg(n)とする。nが非常に大きいとき，実装方法1と実装方法2における g(n)/f(n) の挙動として，適切なものはどれか。
〔実装方法1〕
先頭のセルを指すポインタ型の変数frontだけをもつ。
〔実装方法2〕
先頭のセルを指すポインタ型の変数frontと，末尾のセルを指すポインタ型の変数rearを併せもつ。
| 実装方法1 | 実装方法2 | |
|---|---|---|
| ア | ほぼ1になる。 | ほぼ1になる。 |
| イ | ほぼ1になる。 | ほぼnに比例する。 |
| ウ | ほぼnに比例する。 | ほぼ1になる。 |
| エ | ほぼnに比例する。 | ほぼnに比例する。 |
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
それぞれの実装方法で，末尾への追加時間f(n)と末尾の削除時間g(n)を考えます。
- 実装方法1（frontだけ）
- 追加: 末尾のセルを見つけるために先頭からn個たどる必要があるので，f(n)はnに比例します。
- 削除: 末尾の一つ前のセル（xₙ₋₁）のポインタを空にする必要があり，先頭からたどるので，g(n)もnに比例します。
- したがって g(n)/f(n) は ほぼ1 になります。
- 実装方法2（frontとrear）
- 追加: rearから末尾のセルが直接分かるので，f(n)はnによらず一定です。
- 削除: 単方向リストではrearからxₙ₋₁に戻れないため，先頭からたどる必要があり，g(n)はnに比例します。
-
したがって g(n)/f(n) は ほぼnに比例 します。
-
ア: 実装方法1: ほぼ1，実装方法2: ほぼ1
誤り。実装方法2では，追加は一定時間でできますが，削除にはnに比例する時間がかかるため，比はnに比例します。 -
イ: 実装方法1: ほぼ1，実装方法2: ほぼnに比例
正しい。上記のとおり，実装方法1は追加・削除ともnに比例するので比はほぼ1，実装方法2は追加が一定時間・削除がnに比例するので比はほぼnに比例します。 -
ウ: 実装方法1: ほぼnに比例，実装方法2: ほぼ1
誤り。実装方法1では追加も削除も先頭からたどる必要があり，どちらもnに比例するため，比はほぼ1です。 -
エ: 実装方法1: ほぼnに比例，実装方法2: ほぼnに比例
誤り。実装方法1の比はほぼ1になります。
答え
イ: 実装方法1: ほぼ1になる，実装方法2: ほぼnに比例する
出典：平成21年度 秋期 応用情報技術者試験 午前 問5
