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

正解 エ

線形リストは、指定された要素の後ろへの追加をポインタの付け替えだけで行えるので、計算量は要素数や位置によらず一定（O(1)）です。

ポインタを用いた線形リストは、各要素が次の要素の位置を示すポインタをもち、要素を一列につないだデータ構造です。指定された要素の後ろに新しい要素を追加するときは、新要素のポインタに元の次要素を設定し、指定要素のポインタを新要素に向けるだけで済みます。配列のように後続の要素をずらす必要がないため、計算量は要素の個数や位置によらず一定です。一方、任意の位置の要素に直接アクセスできないので、探索は先頭から順にたどる必要があります。

ア：根の下に全要素がぶら下がる構造は木構造の一種です。線形リストは要素が一列につながる構造で、木ではありません。

イ：2分探索は中央の要素に直接アクセスする必要があるため、添字で直接アクセスできる配列のほうが効率的です。線形リストは先頭から順にたどるしかありません。

ウ：ハッシュ関数は、キーから格納位置を計算するハッシュ表で使います。線形リストは、要素がもつポインタをそのまま使って次の要素をたどります。

出典：令和2年度 10月 応用情報技術者試験 問5