平成27年度 秋期 基本情報技術者試験 午前 問5

解説

ポインタを用いた線形リスト（連結リスト）では，各要素が次の要素へのポインタをもっており，指定した要素の直後に新しい要素を挿入する場合，前後の要素のポインタを付け替えるだけでよく，要素数や挿入位置に関係なく一定の計算量（O(1)）で処理できます。これは，途中への挿入に多くの要素の移動が必要な配列とは対照的な特徴です。

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

選択肢ごとの解説

• ア誤り。線形リストは各要素が次の一つの要素だけを指す1次元的な構造であり，木構造（n分木）ではありません。
• イ誤り。線形リストは先頭から順にたどるしかなく，配列のようにインデックスで直接アクセスできないため，2分探索はできません。
• ウ誤り。ポインタは次の要素の格納アドレスを直接指すものであり，ハッシュ関数を使って求めるものではありません。
• エ正しい。指定した要素の後ろへの挿入は，ポインタの付け替えだけで済むため，要素数や位置に関係なく一定の計算量で行えます。