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

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験，基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 応用情報技術者
  3. 平成21年度秋季問題一覧
  4. 平成21年度秋季問題5-解答・解説-分析

平成21年度秋季問題

問題5

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

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

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 に比例するのでg(n)/f(n)はほぼ1になる。
[実装方法2]
追加の場合はポインタrearのアドレス指定に従い1つ追加するだけなので処理時間はほぼ1になる。削除する場合はrearからは1つ前のアドレスがわからないためfrontから順に辿らなくてはならず、作業時間g(n)はn に比例します。よってg(n)/f(n)はnに比例する。