必ず受かる情報処理技術者試験

問題5

ポケットスタディ 基本情報午後・要点整理―即効!7つの知識 (情報処理技術者試験)

n 個の要素x 1,x 2,…,x n から成る連結リストに対して、新たな要素x n +1の末尾への追加に要する時間をf (n )とし、末尾の要素x n の削除に要する時間をg (n )とする。n が非常に大きいとき、実装方法1と実装方法2におけるの挙動として、適切なものはどれか。

  [実装方法1]
  先頭のセルを指すポインタ型の変数frontだけをもつ。
 
  [実装方法2]
  先頭のセルを指すポインタ型の変数frontと、末尾のセルを指すポインタ型の変数rearを併せもつ。
 

解答・解説を見る

解答:イ

[実装方法1]
新たな要素を追加する際には先頭から順に最後まで辿らなくてはならず、処理時間f(n) はn が増えるほど増加するのでn に比例することになる。同じように削除処理時間g(n)もnが増えれば同様にn に比例するのでg(n)/f(n)はほぼ1になる。
[実装方法2]
追加の場合はポインタrearのアドレス指定に従い1つ追加するだけなので処理時間はほぼ1になる。削除する場合はrearからは1つ前のアドレスがわからないためfrontから順に辿らなくてはならず、作業時間g(n)はn に比例します。よってg(n)/f(n)はnに比例する。
前の問題 次の問題

Copyrithg naruha