令和2年度秋期 応用情報技術者試験 午前 問5
ポインタを用いた線形リストの特徴のうち，適切なものはどれか。
- ア 先頭の要素を根としたn分木で，先頭以外の要素は全て先頭の要素の子である。
- イ 配列を用いた場合と比較して，2分探索を効率的に行うことが可能である。
- ウ ポインタから次の要素を求めるためにハッシュ関数を用いる。
- エ ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。
解答・解説を見る
正解：エ
AI解説
ポインタを用いた線形リストは、各要素が次要素へのポインタを持つデータ構造であり、要素の追加・削除は前後のポインタの繋ぎ替えだけで済むため、挿入位置さえ分かれば要素数や位置によらず一定の計算量で行える。 ア: n分木の説明であり、線形リストは各要素が高々1つの後続要素を持つ一直線の構造であってn分木ではない。 イ: 配列に対する2分探索の説明であり、線形リストは先頭から順にたどるしかなく2分探索を効率的に行うことはできないため誤りである。 ウ: ハッシュ関数を用いるのはハッシュ表(散布法)の説明であり、線形リストはポインタで直接次要素を指すためハッシュ関数は不要である。 エ: 正しい。挿入位置さえ分かれば、要素数や位置に関係なくポインタの付け替えのみで一定の計算量で要素を追加できる。 💡 配列は途中への挿入に要素移動でO(n)の手間がかかるが、線形リストはポインタ操作のみでO(1)という対比で覚えておく。
出典：令和2年度 秋期 応用情報技術者試験 午前 問5 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。