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