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

正解

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

正答率 55.1%（439人中 242人が正解）

問題の解説

ポインタを用いた線形リストは、各要素が次の要素の位置 (ポインタ) をもって一列につながるデータ構造である。ある要素の後ろへの追加は、新しい要素を作って前後のポインタを付け替えるだけで済み、要素数や位置に関係なく手間が一定になる。一方、途中の要素へ直接たどり着けないので、添字で飛び越す二分探索には向かない。

選択肢ごとの解説

• ア線形リストは各要素が次の要素を一つだけ指す一列の構造で、先頭の子として全要素がぶら下がる木構造ではない。
• イ二分探索は中央の要素へ直接アクセスできることが前提で、添字で参照できる配列に向く。線形リストは先頭から順にたどるため、むしろ不利である。
• ウ次の要素の位置はポインタ自身が保持しているので、ハッシュ関数による計算は要らない。ハッシュ関数はハッシュ表で使うものである。
• エ正しい。指定された要素のポインタと新要素のポインタを付け替えるだけなので、要素数や位置にかかわらず手間が一定になる。