情報処理安全確保支援士令和元年秋期 午前T 問4

午前T 問4

先頭ポインタと末尾ポインタをもち,多くのデータがポインタでつながった単方向の線形リストの処理のうち,先頭ポインタ,末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで,単方向のリストは先頭ポインタからつながっているものとし,追加するデータはポインタをたどらなくても参照できるものとする。
  • 先頭にデータを追加する処理
  • 先頭のデータを削除する処理
  • 末尾にデータを追加する処理
  • 末尾のデータを削除する処理
  • [この問題の出題歴]
  • 応用情報技術者
    令和元年秋期 問6と同題

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

リスト構造は、隣接するデータ同士をポインタで連結して表現するデータ構造です。
am1/06.gif/image-size:284×88
    1. 追加するデータの次ノードポインタに、現在の先頭ポインタの値を設定
    2. 先頭ポインタに、追加するデータを指すポインタを設定
    よって、ポインタをたどる回数は0回です。
    1. 先頭ポインタをたどって先頭データを参照
    2. 先頭ポインタに、先頭データが持つ次ノードポインタの値を設定
    よって、ポインタをたどる回数は「先頭ポインタ→先頭データ」で1回です。
    1. 末尾ポインタをたどって末尾データを参照
    2. 末尾データの次ノードポインタに、追加するデータを指すポインタを設定
    3. 末尾ポインタに、追加するデータを指すポインタを設定
    よって、ポインタをたどる回数は「末尾ポインタ→末尾データ」で1回です。
  • 正しい。末尾のデータを削除するには、末尾の一つ前のデータの次ノードポインタを空にして、末尾ポインタに末尾の一つ前のデータを指すポインタを設定しなくてはなりません。単方向リストでは、末尾のデータから前のデータに遡ることはできないので、先頭から末尾の一つ前まで順番にポインタをたどっていく必要があります。
    つまり「末尾のデータを削除する処理」の場合、ポインタをたどる回数はリストが保持するデータ数にほぼ等しい回数となり、「エ」以外の処理と比較してポインタをたどる回数が極端に多くなることがわかります。
data-full-width-responsive="true">
© 2014-2019 情報処理安全確保支援士ドットコム All Rights Reserved.

Pagetop