応用情報技術者試験 応用情報技術者試験 令和2年度 午前 問5: ポインタを用いた線形リストの特徴のうち，適切なものはどれか。

問題本文

ポインタを用いた線形リストの特徴のうち，適切なものはどれか。

選択肢

• ア.先頭の要素を根とした n 分木で，先頭以外の要素は全て先頭の要素の子である。
• イ.配列を用いた場合と比較して，2 分探索を効率的に行うことが可能である。
• ウ.ポインタから次の要素を求めるためにハッシュ関数を用いる。
• エ.ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。

正解

エ. ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。

解説

ポインタを用いた線形(連結)リストは、各要素が次の要素の格納場所(ポインタ)を持つ構造で、配列と対比して挿入・削除がポインタの付け替えだけで済む点が特徴。要素を追加するときは、対象要素のポインタを新要素に、新要素のポインタを元の次要素に向け直すだけでよく、後続要素をずらす必要がないため計算量は要素数や位置によらず一定(O(1))となる。よってエが正解。

選択肢ごとの解説

• ア.線形リストは各要素が次の1要素だけを指す一列の構造であり、根の下に多数の子がぶら下がる n 分木とは異なるため誤り。
• イ.2分探索は添字で中央要素へ直接アクセスできる配列でこそ効率的であり、先頭から順にたどるしかない線形リストでは効率的に行えないため誤り。
• ウ.次の要素はポインタが直接その格納場所を指しており、ハッシュ関数で位置を計算するのはハッシュ表探索の仕組みであって線形リストとは無関係なため誤り。
• エ.要素追加はポインタの付け替えだけで完了し、後続要素の移動が不要なので計算量は要素の個数や位置によらず一定であり、正しい。