テクノロジ系
秋期
応用情報技術者 2009年 秋期 問5
5 / 80
n 個の要素 x1,x2,…,xn から成る連結リストに対して,新たな要素 xn+1 の末尾への追加に要する時間を f(n) とし,末尾の要素 xn の削除に要する時間を g(n) とする。n が非常に大きいとき,実装方法1と実装方法2における g(n)/f(n) の挙動として,適切なものはどれか。〔実装方法1〕先頭のセルを指すポインタ型の変数 front だけをもつ。〔実装方法2〕先頭のセルを指すポインタ型の変数 front と,末尾のセルを指すポインタ型の変数 rear を併せもつ。
正解と解説
表示する
正解 イ
実装方法1ではほぼ1になり,実装方法2ではほぼ n に比例する。
実装方法1はfrontしか持たないため、末尾追加・末尾削除ともに先頭から全要素をたどる必要がありO(n)、比g(n)/f(n)はほぼ1になります。実装方法2はrearを持つため末尾追加はO(1)ですが、末尾削除は末尾の1つ前を求めるために先頭からたどりO(n)となり、比はnに比例します（イ）。