令和2年度 10月 応用情報技術者試験 午前 問5

解説

ポインタを用いた線形リストは，各要素が次の要素のアドレス（ポインタ）を保持して一列につながったデータ構造です。挿入位置の直前の要素が既に分かっていれば，ポインタを付け替えるだけで挿入でき，要素の移動が不要なので計算量は要素数や位置によらず一定です。

下線の用語は 用語集 で意味を確認できます。

選択肢ごとの解説

• ア誤り。先頭を根とする n 分木の説明であり，線形リストは各要素が次の要素を一つだけ指す一列の構造です。
• イ誤り。2 分探索は添字によって任意の位置へ直接アクセスできる配列に適した手法です。線形リストは先頭からたどる必要があるため，2 分探索には向きません。
• ウ誤り。ハッシュ関数で格納位置を求めるのはハッシュ表（ハッシュ法）です。線形リストは次要素のアドレスをポインタとして直接保持します。
• エ正しい。挿入はポインタの付け替えだけで済むため，計算量は要素の個数や位置によらず一定（O(1)）です。