データ構造 (全39問中23問目)

No.23

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

分類

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

正解

解説

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

Pagetop