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

【正解】ア

配列でリストを実現する場合、要素を連続した領域に格納します。一般に、格納できる最大要素数をあらかじめ決め、その個数分の配列領域を確保します。このため、最大100個の配列を用意して実際には10個しか格納していない場合、残り90個分は未使用領域になります。したがって、実際の要素数にかかわらず最大個数に応じた領域が必要になるというアが適切です。

イの説明は誤りです。これはポインタを用いた連結リストの特徴です。連結リストでは、目的の要素まで先頭からポインタを順にたどるため、参照時間は要素数に比例します。一方、配列では添字から格納位置を計算できるので、任意の要素を一定時間で直接参照できます。

ウの説明は誤りです。次の要素を示すポインタ用の領域が必要なのは、ポインタを用いた連結リストです。配列によるリストでは、格納位置の並びによって要素の順序を表します。

エの説明は誤りです。これは挿入位置の直前の要素を指すポインタが分かっている連結リストの特徴です。配列の途中に挿入する場合は、後続要素を一つずつずらす必要があり、要素数に比例する時間がかかることがあります。

【ポイント】 配列は、添字による参照が高速ですが、途中への挿入や削除では要素の移動が必要です。 連結リストは、参照には順次探索が必要ですが、位置が分かっていれば挿入や削除を効率よく行えます。 記憶領域、参照速度、挿入・削除の三つの観点で比較してください。