平成27年度 秋期 基本情報技術者試験 午前 問5
テクノロジ／アルゴリズムポインタを用いた線形リストの特徴のうち，適切なものはどれか。
出典：平成27年度 秋期 基本情報技術者試験 午前 問5
- ア先頭の要素を根とした n 分木で，先頭以外の要素は全て先頭の要素の子である。
- イ配列を用いた場合と比較して，2分探索を効率的に行うことが可能である。
- ウポインタから次の要素を求めるためにハッシュ関数を用いる。
- エポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。
正解：エ
解説
ポインタを用いた線形リスト（連結リスト）では，各要素が次の要素へのポインタをもっており，指定した要素の直後に新しい要素を挿入する場合，前後の要素のポインタを付け替えるだけでよく，要素数や挿入位置に関係なく一定の計算量（O(1)）で処理できます。これは，途中への挿入に多くの要素の移動が必要な配列とは対照的な特徴です。
選択肢ごとの解説
- ア誤り。線形リストは各要素が次の一つの要素だけを指す1次元的な構造であり，木構造（n分木）ではありません。
- イ誤り。線形リストは先頭から順にたどるしかなく，配列のようにインデックスで直接アクセスできないため，2分探索はできません。
- ウ誤り。ポインタは次の要素の格納アドレスを直接指すものであり，ハッシュ関数を使って求めるものではありません。
- エ正しい。指定した要素の後ろへの挿入は，ポインタの付け替えだけで済むため，要素数や位置に関係なく一定の計算量で行えます。