基本情報技術者試験 基本情報技術者試験 平成29年度 春期 午前 午前 問4: データ構造の一つであるリストは，配列を用いて実現する場合と，ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで，配列を用いたリ

問題本文

データ構造の一つであるリストは，配列を用いて実現する場合と，ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで，配列を用いたリストは，配列に要素を連続して格納することによって構成し，ポインタを用いたリストは，要素から次の要素へポインタで連結することによって構成するものとする。

選択肢

• ア.位置を指定して，任意のデータに直接アクセスすることができる。
• イ.並んでいるデータの先頭に任意のデータを効率的に挿入することができる。
• ウ.任意のデータの参照は効率的ではないが，削除や挿入の操作を効率的に行える。
• エ.任意のデータを別の位置に移動する場合，隣接するデータを移動せずにできる。

正解

ア. 位置を指定して，任意のデータに直接アクセスすることができる。

解説

配列実装のリストは要素が連続配置されているため、インデックスから O(1) で直接アクセスできるのが特徴。アが正解。

選択肢ごとの解説

• ア.添字で任意要素に直接アクセス可能。配列リストの主な特徴で正解。
• イ.先頭への挿入はポインタリストが効率的 (O(1))。配列は O(n) 必要。
• ウ.挿入削除が効率的なのはポインタリストの特徴。
• エ.別位置へ移動でも配列はデータ移動が必要。ポインタリストならポインタだけ変更で済む。