正答4
解説
正解は4です。
ポインタを用いた線形リスト（連結リスト）の特徴を問う問題です。
線形リストは、各要素が次の要素の位置を示すポインタを持ち、要素が一列につながったデータ構造です。
【選択肢別解説】
1：× 先頭を根として他の要素がすべてその子になる構造は、木構造の説明です。
線形リストは要素が一列に並ぶ構造です。
2：× 2分探索には、中央の要素へ直接アクセスする必要があります。
線形リストは先頭から順にたどるしかないので、2分探索は配列のほうが効率的です。
3：× 線形リストでは、次の要素の位置はポインタそのものが示します。
ハッシュ関数を使うのはハッシュ表です。
4：○ 指定された要素の後ろへの追加は、ポインタを2か所付け替えるだけで済みます。
要素の個数や位置によらず計算量は一定です。
【ポイント】
線形リストは挿入・削除が速く、配列は位置を指定した参照や2分探索が速いという対比が頻出です。
配列で途中に挿入する場合は、後ろの要素をずらす必要があるので要素数に比例した時間がかかります。