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

• ア: 先頭の要素を根としたn分木で，先頭以外の要素は全て先頭の要素の子である。
  誤り。線形リストは木構造ではなく，各要素がポインタで次の要素を指すリスト構造です。先頭の要素以外が全て先頭の要素の子という表現は不適切です。

• イ: 配列を用いた場合と比較して，2分探索を効率的に行うことが可能である。
  誤り。線形リストは要素が連続的に格納されていないため、ランダムアクセスが不可能であり、2分探索は非効率です。探索は線形探索になります。

• ウ: ポインタから次の要素を求めるためにハッシュ関数を用いる。
  誤り。ハッシュ関数はハッシュテーブルで使用されるものであり，線形リストでは単純にポインタをたどることで次の要素を求めます。

• エ: ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。
  正しい。ポインタを使った線形リストでは、任意の位置に要素を挿入する場合でも、ポインタを変更するだけで済むため、一定の計算量で処理できます。

答え

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