応用情報技術者 2022年 春期 午前2 問05
問題文
リストには、配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として、適切なものはどれか。ここで、配列を用いたリストは配列に要素を連続して格納することによってリストを構成し、ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。
選択肢
ア：リストにある実際の要素数にかかわらず、リストに入れられる要素の最大個数に対応した領域を確保し、実際には使用されない領域が発生する可能性がある。（正解）
イ：リストの中間要素を参照するには、リストの先頭から順番に要素をたどっていくことから、要素数に比例した時間が必要となる。
ウ：リストの要素を格納する領域の他に、次の要素を指し示すための領域が別途必要となる。
エ：リストへの挿入位置が分かる場合には、リストにある実際の要素数にかかわらず、要素の挿入を一定時間で行うことができる。
リストの配列実装の特徴【午前2 解説】
要点まとめ
- 結論：配列で実装したリストは最大要素数分の領域を確保し、未使用領域が生じる可能性があります。
- 根拠：配列は連続したメモリ領域を確保し、サイズ変更が難しいため、最大容量を予め確保します。
- 差がつくポイント：ポインタ実装との違いを理解し、メモリ効率やアクセス速度の特徴を押さえることが重要です。
正解の理由
選択肢アは、配列でリストを実装する際に最大要素数分の領域を確保し、実際の要素数が少ない場合でも未使用の領域が発生することを正しく説明しています。配列はサイズ固定で連続したメモリを使うため、動的にサイズを変えられず、余分な領域が生じやすい特徴があります。
よくある誤解
配列実装のリストは要素の挿入や削除が常に高速だと思われがちですが、実際には挿入位置によっては要素の移動が必要で時間がかかります。
解法ステップ
- 配列実装のリストの特徴を確認する（連続したメモリ領域、サイズ固定）。
- ポインタ実装との違いを理解する（ポインタは動的に要素をつなぐ）。
- 選択肢を比較し、配列特有の「最大容量確保と未使用領域発生」を示すものを選ぶ。
- 他の選択肢がポインタ実装の特徴や誤った説明であることを確認する。
選択肢別の誤答解説
- イ：中間要素の参照に時間がかかるのはポインタ実装（連結リスト）であり、配列はインデックスで直接アクセス可能。
- ウ：次の要素を指すポインタ領域が必要なのはポインタ実装のリストであり、配列実装には不要。
- エ：配列実装では挿入時に要素のシフトが必要で、一定時間での挿入はできない。
補足コラム
配列実装のリストはアクセス速度が速い反面、サイズ変更が難しくメモリの無駄が生じやすいです。一方、ポインタ実装は柔軟なサイズ変更が可能ですが、アクセス速度は遅くなりがちです。用途に応じて使い分けることが重要です。
FAQ
Q: 配列実装のリストはサイズ変更できないのですか？
A: 基本的には固定サイズですが、動的配列（例：ArrayList）では内部で再確保を行いサイズ変更を実現します。
A: 基本的には固定サイズですが、動的配列（例：ArrayList）では内部で再確保を行いサイズ変更を実現します。
Q: ポインタ実装のリストはなぜアクセスが遅いのですか？
A: 要素が連続していないため、目的の要素にたどり着くまで順にポインタを辿る必要があるからです。
A: 要素が連続していないため、目的の要素にたどり着くまで順にポインタを辿る必要があるからです。
関連キーワード: 配列、連結リスト、メモリ管理、データ構造、アクセス速度、挿入削除
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！