問5応用情報技術者 令和2年度 10月

解説

正解は4。線形リストは、各要素が次の要素の位置をポインタでもつデータ構造。挿入位置の要素がポインタで分かっていれば、新しい要素のポインタを元の次の要素に向け、元の要素のポインタを新しい要素に付け替えるだけで済む。要素数や位置に関係なく手間は一定（O(1)）になる。

• 1は、木構造の説明で、しかも全要素が根の子という特殊な形であり、線形リストではない。
• 2は、逆。2分探索は中央の要素に一度で届く必要があり、添字で直接参照できる配列のほうが向く。リストは先頭からたどるしかない。
• 3は、ハッシュ表の説明。リストはポインタそのものが次の要素の場所を指すので、ハッシュ関数は使わない。

根拠：線形リストと配列の性質（挿入・削除と探索の計算量）。