基本情報技術者 予想問題｜B 第71問

解説

正解はア。連結リストは、データ本体と次要素へのポインタ（参照）を持つノードを数珠つなぎにしたデータ構造である。要素を連続したメモリ領域に置く必要がなく、挿入・削除は前後のポインタの付替えだけで済むため、位置が分かっていればO(1)で行える。一方、目的の要素へは先頭からポインタを順にたどる必要があり、アクセスにはO(n)かかる。イの「固定サイズのメモリ領域に要素を並べる」は配列の説明で、添字によるランダムアクセスがO(1)でできる点が連結リストと対照的である。ウの木構造は親子の階層関係を表す別の構造、エの「キーと値のペアで管理する」はハッシュ表（連想配列）の説明である。配列と連結リストの長所・短所の比較（アクセス速度と挿入・削除コストのトレードオフ）は科目A・Bともに頻出である。