平成29年度 春期 基本情報技術者試験 午前 問4
テクノロジ／アルゴリズムデータ構造の一つであるリストは，配列を用いて実現する場合と，ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで，配列を用いたリストは，配列に要素を連続して格納することによって構成し，ポインタを用いたリストは，要素から次の要素へポインタで連結することによって構成するものとする。
出典：平成29年度 春期 基本情報技術者試験 午前 問4
- ア位置を指定して，任意のデータに直接アクセスすることができる。
- イ並んでいるデータの先頭に任意のデータを効率的に挿入することができる。
- ウ任意のデータの参照は効率的ではないが，削除や挿入の操作を効率的に行える。
- エ任意のデータを別の位置に移動する場合，隣接するデータを移動せずにできる。
正解：ア
解説
配列を用いたリストは，メモリ上に要素が連続して並んでいるため，先頭アドレスと添字（位置）が分かれば，計算だけで目的の要素のアドレスを求めて直接アクセスできます。一方，途中への挿入や削除では，後続の要素をずらす必要があるため効率的ではありません。これはポインタを用いたリスト（連結リスト）とは逆の特徴です。
選択肢ごとの解説
- ア正しい。配列は要素が連続して格納されているため，添字を指定するだけで任意の要素に直接アクセスできます。
- イ誤り。先頭に挿入するには既存の要素を全て後ろにずらす必要があり，効率的ではありません。これはポインタを用いたリストの利点です。
- ウ誤り。配列は任意のデータへの参照はO(1)で効率的ですが，削除や挿入は要素の移動が必要で効率的ではありません。記述が逆です。
- エ誤り。配列でデータを移動すると，間の要素も詰めるためにずらす必要があります。移動せずに済むのはポインタを用いたリストの特徴です。