正答4
解説
正解は4です。
線形リストは、各要素が次の要素の位置を指すポインタをもち、鎖のようにつながったデータ構造です。
要素の挿入や削除をポインタの付け替えだけで行えるのが長所です。
一方で、途中の要素に直接アクセスできないという短所があります。
【選択肢別解説】
1：× 先頭を根として他の全要素がその子になる構造は、木構造の一種の説明です。
線形リストでは要素が一列に並び、各要素は次の1要素だけを指します。
2：× 2分探索は、中央の要素に直接アクセスする必要があるので、添字で任意の位置を参照できる配列向けの方法です。
線形リストは先頭から順にたどるしかないため、2分探索を効率的に行えません。
3：× 次の要素は、各要素がもつポインタの値をたどって求めます。
ハッシュ関数はキーから格納位置を計算するハッシュ表で用いるもので、線形リストでは使いません。
4：○ 指定された要素の後ろに追加するには、新しい要素のポインタと直前の要素のポインタを書き換えるだけで済みます。
要素を移動する必要がないので、計算量は要素数や位置によらず一定（O(1)）です。
【ポイント】
配列は任意位置の参照がO(1)ですが、挿入・削除は要素の移動が必要なのでO(n)です。
線形リストはその逆で、挿入・削除がO(1)、任意位置の参照がO(n)です。