リストには,配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として,適切なものはどれか。ここで,配列を用いたリストは配列に要素を連続して格納することによってリストを構成し,ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。
- リストにある実際の要素数にかかわらず,リストに入れられる要素の最大個数に対応した領域を確保し,実際には使用されない領域が発生する可能性がある。
- リストの中間要素を参照するには,リストの先頭から順番に要素をたどっていくことから,要素数に比例した時間が必要となる。
- リストの要素を格納する領域の他に,次の要素を指し示すための領域が別途必要となる。
- リストへの挿入位置が分かる場合には,リストにある実際の要素数にかかわらず,要素の挿入を一定時間で行うことができる。
解答
ア
解説
- リストにある実際の要素数にかかわらず,リストに入れられる要素の最大個数に対応した領域を確保し,実際には使用されない領域が発生する可能性がある。
ー - リストの中間要素を参照するには,リストの先頭から順番に要素をたどっていくことから,要素数に比例した時間が必要となる。
ー - リストの要素を格納する領域の他に,次の要素を指し示すための領域が別途必要となる。
ー - リストへの挿入位置が分かる場合には,リストにある実際の要素数にかかわらず,要素の挿入を一定時間で行うことができる。
ー
参考情報
分野・分類
分野 | テクノロジ系 |
大分類 | 基礎理論 |
中分類 | アルゴリズムとプログラミング |
小分類 | データ構造 |
出題歴
- AP 令和4年度春期 問5