問題プレビューID: c61c4df9応用情報技術者試験 2009年(平成21年度)秋期 午前

問 5
応用情報技術者試験 2009年(平成21年度)秋期 午前

nn 個の要素 x1,x2,⋯ ,xnx_1, x_2, \cdots, x_n から成る連結リストに対して,新たな要素 xn+1x_{n+1} の末尾への追加に要する時間を f(n)f(n) とし,末尾の要素 xnx_n の削除に要する時間を g(n)g(n) とする。nn が非常に大きいとき,実装方法 1 と実装方法 2 における g(n)f(n)\frac{g(n)}{f(n)} の挙動として,適切なものはどれか。

〔実装方法 1〕 先頭のセルを指すポインタ型の変数 front だけをもつ。

〔実装方法 2〕 先頭のセルを指すポインタ型の変数 front と,末尾のセルを指すポインタ型の変数 rear を併せもつ。

解説

正解は「イ」です。

連結リストでは,目的のセルにたどり着くために先頭(front)からポインタをたどる必要があります。nn が非常に大きいとき,たどる回数が支配的になります。

  • 実装方法 1(front のみ): 末尾への追加も,末尾要素の削除も,いずれも先頭から末尾までたどる必要があり,f(n)f(n) も g(n)g(n) もほぼ nn に比例します。したがって g(n)f(n)\frac{g(n)}{f(n)} はほぼ 1 になります。
  • 実装方法 2(front と rear): 末尾を指す rear があるため,末尾への追加は定数時間ででき,f(n)f(n) はほぼ 1 になります。一方,末尾要素 xnx_n を削除するにはその 1 つ前のセル(xn−1x_{n-1})を知る必要があり,rear だけでは分からないため先頭からたどることになり,g(n)g(n) はほぼ nn に比例します。したがって g(n)f(n)\frac{g(n)}{f(n)} はほぼ nn に比例します。

以上より,実装方法 1 はほぼ 1,実装方法 2 はほぼ nn に比例する「イ」が正解です。

関連問題

本文が同じ・似ている問題を表示しています