情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和4年度春期 午前Ⅰ 問2: リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要

問題本文

リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。

選択肢

• ア.リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
• イ.リストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくことから，要素数に比例した時間が必要となる。
• ウ.リストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
• エ.リストへの挿入位置が分かる場合には，リストにある実際の要素数にかかわらず，要素の挿入を一定時間で行うことができる。

正解

ア. リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。

解説

配列でリストを実現すると、要素を連続領域に詰めるため添字で任意要素へO(1)で参照できる反面、最大要素数分の領域をあらかじめ確保する必要があり、未使用領域が生じうる。アはこの固定領域確保の欠点を正しく述べる。イ・ウ・エはポインタ実現の特徴で誤り。データ構造の選択は参照速度と挿入削除の柔軟性のトレードオフを意識することが実務でも重要。

選択肢ごとの解説

• ア.配列は最大個数分の領域を事前確保するため未使用領域が発生しうる。配列実現の特徴で正しい。
• イ.配列は添字で中間要素へ直接アクセスでき、先頭からたどる必要はない。ポインタ実現の説明で誤り。
• ウ.次要素を指すポインタ用の領域が要るのはポインタ実現の特徴であり、配列実現には当てはまらず誤り。
• エ.配列では挿入時に後続要素をずらす必要があり一定時間にならない。ポインタ実現の特徴で誤り。