平成21年秋期試験午前問題 問5

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

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

05a.gif
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
2つの連結構造(単方向リスト・双方向リスト)において、
  • 新要素の末尾への追加 f(n)
  • 末尾の要素の削除 g(n)
に要する時間の関係を考える問題です。
※一回のポインタ参照→次のセルへのアクセスに要する時間は一定であるとし、処理に要する時間は、このセル移動に回数に比例するものとします。

まず〔実装方法1〕について考えます。
"新要素(n+1)の末尾への追加"は、 ポインタfrontからリスト構造を末尾のデータ(n)まで順にたどり、末尾のデータのポインタ部を新しい要素へのポインタにします。したがって、セル移動の回数はn回です。 
"末尾の要素の削除"は、ポインタfrontから末尾の要素の一つ前の手前の要素(n-1)までたどり、末尾の要素へのポインタを削除します。したがって、セル移動の回数はn-1回です。

nは非常に大きいという条件があるので、〔実装方法1〕の05_1.gifは、(n-1)/nほぼ1となります。

次に〔実装方法2〕について考えます。
"新要素(n+1)の末尾への追加"は、 ポインタrearを参照することで1回で末尾のセルへアクセスし、末尾のデータのポインタ部を新しい要素へのポインタにします。したがって、セル移動の回数は1回です。 
"末尾の要素の削除"は、〔実装方法1〕と同様に、ポインタfrontから末尾の要素の一つ前の手前の要素(n-1)までたどり、末尾の要素へのポインタを削除します。この場合では、ポインタrearから末尾のセルへ移動することはできても、「末尾のセルからその一つ手前のセルへはポインタがないため戻ることができない」という点が理解できているかがポイントになります。したがって、セル移動の回数はn-1回です。

〔実装方法2〕の、05_1.gifは、(n-1)/1ほぼnに比例となります。

以上より〔実装方法1〕="ほぼ1となる"、〔実装方法2〕="ほぼ n に比例する"の組合せで「イ」が正解となります。

Pagetop