平成２１年度 秋期 高度情報技術者試験問題と解説
問３
n個の要素ｘ1, ｘ2, …, ｘnから成る連結リストに対して、新たな要素ｘn+1の末尾への追加に要する時間をｆ(n)とし、末尾の要素ｘnの削除に要する時間をｇ(n)とする。nが非常に大きいとき、実装方法1と実装方法2におけるｇ(n)／ｆ(n)の挙動として、適切なものはどれか。
〔実装方法1〕
先頭のセルを指すポインタ型の変数frontだけをもつ。
〔実装方法2〕
先頭のセルを指すポインタ型の変数frontと、末尾のセルを指すポイント型の変数rearを併せもつ。
┌─────────┬─────────┐
│ 実装方法１ │ 実装方法１ │
┌─┼─────────┼─────────┤
│ア│ほぼ１になる。 │ほぼ１になる。 │
├─┼─────────┼─────────┤
│イ│ほぼ１になる。 │ほぼｎに比例する。│
├─┼─────────┼─────────┤
│ウ│ほぼｎに比例する。│ほぼ１になる。 │
├─┼─────────┼─────────┤
│エ│ほぼｎに比例する。│ほぼｎに比例する。│
└─┴─────────┴─────────┘
正解
イ
解説
連結リストをたどって、対象となるセルにたどりつくまでの時間を等考える問題である。
〔実装方法1〕
nが非常に大きいため、
ｘ1から順に連結リストをたどって、ｘnにたどりつく時間も、ｘn+1にたどりつく時間もほとんど変わらない。
したがって、ｇ(n)／ｆ(n) ≒ 1である。
〔実装方法2〕
ｘ1から順に連結リストをたどって、ｘnにたどりつき、末尾の要素ｘnの削除に要する時間はnに比例する。
しかし、末尾のｘn+1にたどりつくには、変数rearによって1回で済む。
したがって、ｇ(n)／ｆ(n) はnに比例する。
| 問２ | 目次 | 問４ |