応用情報技術者 2020年 秋期 午前2 問05
問題文
ポインタを用いた線形リストの特徴のうち、適切なものはどれか。
選択肢
ア：先頭の要素を根としたn 分木で、 先頭以外の要素は全て先頭の要素の子である。
イ：配列を用いた場合と比較して、 2分探索を効率的に行うことが可能である。
ウ：ポインタから次の要素を求めるためにハッシュ関数を用いる。
エ：ポインタによって指定されている要素の後ろに、 新たな要素を追加する計算量は、要素の個数や位置によらず一定である。（正解）
ポインタを用いた線形リストの特徴【午前2 解説】
要点まとめ
- 結論：ポインタを用いた線形リストでは、要素の追加が位置に関係なく一定時間で可能です。
- 根拠：ポインタで次の要素を直接指すため、末尾の要素のポインタを書き換えるだけで追加が完了します。
- 差がつくポイント：配列と異なり、要素の移動や再配置が不要なため、挿入・削除の計算量が安定している点を理解しましょう。
正解の理由
選択肢エは「ポインタによって指定されている要素の後ろに新たな要素を追加する計算量は、要素の個数や位置によらず一定である」と述べています。
これは単方向リストの末尾に要素を追加する場合、末尾のポインタを直接更新するだけで済むため、計算量はで一定です。
他の選択肢は線形リストの基本的な構造や操作の特徴と異なっているため誤りです。
これは単方向リストの末尾に要素を追加する場合、末尾のポインタを直接更新するだけで済むため、計算量はで一定です。
他の選択肢は線形リストの基本的な構造や操作の特徴と異なっているため誤りです。
よくある誤解
ポインタを使うと必ず高速に探索できるわけではありません。特に線形リストは順次探索が基本で、二分探索は効率的にできません。
また、ポインタ操作にハッシュ関数は不要であり、誤った理解が混乱を招きます。
また、ポインタ操作にハッシュ関数は不要であり、誤った理解が混乱を招きます。
解法ステップ
- 線形リストの基本構造を理解する（要素がポインタで連結されている）。
- 各選択肢の内容が線形リストの特徴に合致しているか検証する。
- 追加操作の計算量が位置に依存しないかを考える。
- 二分探索やハッシュ関数の利用が線形リストに適しているかを判断する。
- 正しい特徴を示す選択肢を選ぶ。
選択肢別の誤答解説
- ア：線形リストは木構造ではなく、n分木の概念は当てはまりません。
- イ：線形リストは連続したメモリ領域ではないため、二分探索は効率的に行えません。
- ウ：ポインタ操作にハッシュ関数は不要であり、誤った説明です。
- エ：正解。ポインタで指定された位置の後ろに要素を追加する操作はで一定時間です。
補足コラム
線形リストは配列と異なり、要素の挿入や削除が容易ですが、ランダムアクセスは苦手です。
末尾に要素を追加する場合、末尾ポインタを保持していれば計算量はですが、末尾ポインタがなければになる点に注意しましょう。
末尾に要素を追加する場合、末尾ポインタを保持していれば計算量はですが、末尾ポインタがなければになる点に注意しましょう。
FAQ
Q: ポインタを使った線形リストで二分探索は可能ですか？
A: いいえ。線形リストは連続したメモリ領域ではないため、二分探索は効率的に行えません。
A: いいえ。線形リストは連続したメモリ領域ではないため、二分探索は効率的に行えません。
Q: 配列と線形リストの主な違いは何ですか？
A: 配列は連続したメモリ領域で高速なランダムアクセスが可能ですが、挿入・削除が遅い。線形リストはポインタで要素が連結されており、挿入・削除が高速ですがランダムアクセスは遅いです。
A: 配列は連続したメモリ領域で高速なランダムアクセスが可能ですが、挿入・削除が遅い。線形リストはポインタで要素が連結されており、挿入・削除が高速ですがランダムアクセスは遅いです。
関連キーワード: ポインタ、線形リスト、計算量、挿入操作、データ構造
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！