応用情報技術者 2009年 秋期 問5

n 個の要素 x1,x2,…,xn から成る連結リストに対して,新たな要素 xn+1 の末尾への追加に要する時間を f(n) とし,末尾の要素 xn の削除に要する時間を g(n) とする。n が非常に大きいとき,実装方法1と実装方法2における g(n)/f(n) の挙動として,適切なものはどれか。〔実装方法1〕先頭のセルを指すポインタ型の変数 front だけをもつ。〔実装方法2〕先頭のセルを指すポインタ型の変数 front と,末尾のセルを指すポインタ型の変数 rear を併せもつ。