令和元年秋期試験午前問題 午前Ⅰ 問4

午前Ⅰ 問4解説へ
先頭ポインタと末尾ポインタをもち,多くのデータがポインタでつながった単方向の線形リストの処理のうち,先頭ポインタ,末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで,単方向のリストは先頭ポインタからつながっているものとし,追加するデータはポインタをたどらなくても参照できるものとする。

  • 先頭にデータを追加する処理
  • 先頭のデータを削除する処理
  • 末尾にデータを追加する処理
  • 末尾のデータを削除する処理
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
リスト構造は、隣接するデータ同士をポインタで連結して表現するデータ構造です。
am1/06.gif
    1. 追加するデータの次ノードポインタに、現在の先頭ポインタの値を設定
    2. 先頭ポインタに、追加するデータを指すポインタを設定
    よって、ポインタをたどる回数は0回です。
    1. 先頭ポインタをたどって先頭データを参照
    2. 先頭ポインタに、先頭データが持つ次ノードポインタの値を設定
    よって、ポインタをたどる回数は「先頭ポインタ→先頭データ」で1回です。
    1. 末尾ポインタをたどって末尾データを参照
    2. 末尾データの次ノードポインタに、追加するデータを指すポインタを設定
    3. 末尾ポインタに、追加するデータを指すポインタを設定
    よって、ポインタをたどる回数は「末尾ポインタ→末尾データ」で1回です。
  • 正しい。末尾のデータを削除するには、末尾の一つ前のデータの次ノードポインタを空にして、末尾ポインタに末尾の一つ前のデータを指すポインタを設定しなくてはなりません。単方向リストでは、末尾のデータから前のデータに遡ることはできないので、先頭から末尾の一つ前まで順番にポインタをたどっていく必要があります。
    つまり「末尾のデータを削除する処理」の場合、ポインタをたどる回数はリストが保持するデータ数にほぼ等しい回数となり、「エ」以外の処理と比較してポインタをたどる回数が極端に多くなることがわかります。

Pagetop