データ構造 (全39問中3問目)
No.3
リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。
出典：令和4年春期 問5
- リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
- リストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくことから，要素数に比例した時間が必要となる。
- リストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
- リストへの挿入位置が分かる場合には，リストにある実際の要素数にかかわらず，要素の挿入を一定時間で行うことができる。
- [出題歴]
- 基本情報技術者 H25秋期 問6
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ア
解説
- 正しい。配列で実現するリストの特徴です。配列を用いる場合は最大の要素数を格納できるだけのメモリ領域をあらかじめ確保する必要があります。1,000要素分確保しても実際の格納数が10要素程度だとすると、残りの990要素分のメモリ領域が無駄になってしまいます。
- ポインタで実現するリストの特徴です。配列リストでは要素をメモリ上の連続した領域に格納するので、添字と一要素のデータサイズから参照すべきメモリアドレスをすぐに計算することができます。したがって、要素の格納位置にかかわらず参照時間は一定になります。
- ポインタで実現するリストの特徴です。配列リストでは連続したメモリ領域に添字順に要素を格納するので、次の要素の位置を容易に計算することができます。したがって、ポインタリストのように次の要素へのポインタを保持しておく必要はありません。
- 配列リストに要素を挿入する場合、挿入位置より後ろに格納されている要素を1つずつ後ろの領域へ移動しなくてはなりません。また削除する場合は削除位置より後ろに格納されている要素を1つずつ前に移動する必要があります。挿入や削除の対象要素が配列リストの前方であるほど、後方に存在する要素が多くなるので処理に時間がかかることになります。