基本情報技術者平成29年春期 午前問4

午前問4

データ構造の一つであるリストは,配列を用いて実現する場合と,ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで,配列を用いたリストは,配列に要素を連続して格納することによって構成し,ポインタを用いたリストは,要素から次の要素へポインタで連結することによって構成するものとする。
  • 位置を指定して,任意のデータに直接アクセスすることができる。
  • 並んでいるデータの先頭に任意のデータを効率的に挿入することができる。
  • 任意のデータの参照は効率的ではないが,削除や挿入の操作を効率的に行える。
  • 任意のデータを別の位置に移動する場合,隣接するデータを移動せずにできる。

分類

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

正解

解説

  • 正しい。配列を用いたリストでは各要素の位置を"先頭から何番目"というように指定して参照できます。リスト構造では、目的の要素に到達するまで先頭または後方から順番にポインタをたどっていく必要があります。
    04a.gif/image-size:332×131
  • 配列の先頭にデータを挿入するためには、現在の要素全体を挿入されるデータの分だけ後ろにずらす必要があります。要素の個数が多ければその分だけ挿入に伴う処理量は増加します。リスト構造では数個のポインタを付け替えるだけで容易に先頭への挿入ができます。
    04i.gif/image-size:332×219
  • 任意のデータの参照には直接アクセス可能な配列構造が有利です。しかし削除や挿入は要素の移動回数が多くなるため非効率です。
  • 配列内のデータの移動では、移動対象を一旦退避し、空いた箇所を詰めるように隣接データをずらす必要があります。
    04e.gif/image-size:332×229
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop