平成21年度 秋期 応用情報技術者試験 午前 問5
テクノロジ／アルゴリズムn個の要素 x1，x2，…，xn から成る連結リストに対して，新たな要素 xn+1 の末尾への追加に要する時間を f(n) とし，末尾の要素 xn の削除に要する時間を g(n) とする。n が非常に大きいとき，実装方法1と実装方法2における g(n)/f(n) の挙動として，適切なものはどれか。 〔実装方法1〕 先頭のセルを指すポインタ型の変数 front だけをもつ。要素は front から x1，x2，…，xn の順に単方向に連結されており，末尾の要素は次を指すポインタが空になっている。 〔実装方法2〕 先頭のセルを指すポインタ型の変数 front と，末尾のセルを指すポインタ型の変数 rear を併せもつ。要素の並びは実装方法1と同じである。
出典：平成21年度 秋期 応用情報技術者試験 午前 問5
- ア実装方法1はほぼ1になる，実装方法2はほぼ1になる。
- イ実装方法1はほぼ1になる，実装方法2はほぼnに比例する。
- ウ実装方法1はほぼnに比例する，実装方法2はほぼ1になる。
- エ実装方法1はほぼnに比例する，実装方法2はほぼnに比例する。
正解：イ
解説
実装方法1はfrontポインタしかもたないため，末尾への追加f(n)には先頭から末尾までn個をたどる必要があり，末尾の削除g(n)も末尾の一つ前を探すのにほぼ同じn回のたどりが必要です。したがってg(n)/f(n)はほぼ1に収束します。実装方法2はrearポインタがあるため追加f(n)は定数時間で済みますが，削除では単方向リストのため末尾の一つ前のセルを探すのにやはり先頭からn回たどる必要があり，g(n)はnに比例します。よってg(n)/f(n)はnに比例します。
選択肢ごとの解説
- ア誤り。実装方法2はrearポインタがあっても末尾削除には先頭からの探索が必要でnに比例するため，「ほぼ1になる」は誤りです。
- イ正しい。実装方法1はf(n)もg(n)もほぼn回のたどりを要するため比はほぼ1になり，実装方法2はf(n)が定数時間であるのに対しg(n)がnに比例するため比はnに比例します。
- ウ誤り。実装方法1はf(n)もg(n)もほぼ同じ回数のたどりが必要なので，比がnに比例することはありません。
- エ誤り。実装方法2のf(n)はrearポインタにより定数時間で行えるため，比がほぼ1になることはありません。