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

正解

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

正答率 55.2%（435人中 240人が正解）

問題の解説

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

選択肢ごとの解説

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