応用情報技術者試験 令和2年秋 午前問5 解説付き過去問

この問題は、ポインタを用いた線形リストの特徴として正しいものを選ぶ問題です。
線形リストの構造的な特性と、他のデータ構造との違いを理解することが重要です。

1. 線形リストの構造
   線形リストは、各要素が次の要素へのポインタを持つことによって構成されるデータ構造です。
   通常、単方向リストでは各ノードが「データ」と「次のノードへの参照」を持ちます。
   このような構造により、挿入や削除などの操作を柔軟に行うことができます。
   
   
2. 特定の位置への要素追加
   挿入位置の要素が既に分かっていれば、次のような操作で新しい要素を追加できます。
   
   1. 新しいノードを作成する
      
      
   2. 新しいノードのポインタを、元の要素が指していた次のノードに設定する
      
      
   3. 元の要素のポインタを、新しいノードに付け替える
      
      
   この処理は探索を伴わずに行えるため、計算量はO(1)（一定時間）となります。
   これが、ポインタを使った線形リストの挿入操作の大きな利点です。
   
   
3. 他の選択肢の検討
   
   • 「先頭を根としたn分木」
     これは木構造の説明です。線形リストは直線的に要素が並ぶ構造であり、親子関係のある木構造とは異なります。
     
     
   • 「2分探索を効率的に行える」
     線形リストは、各要素に順番にアクセスする必要があるため、2分探索のような高速探索はできません。
     2分探索が可能なのは、ランダムアクセスと整列済みが前提の配列や2分探索木などです。
     
     
   • 「ハッシュ関数を用いる」
     ポインタは、次の要素のメモリアドレスを直接保持しているものであり、ハッシュ関数のような計算処理は不要です。
     この選択肢は、ハッシュ表と混同しており誤りです。
     
     
   
   
4. 結論
   挿入対象の要素が分かっている場合、ポインタを使った線形リストではその直後に新たな要素を一定時間で追加可能です。
   この性質は、配列などの構造に比べて動的な操作に優れており、問題文の記述と一致します。
   
   

したがって、ポインタによって指定された要素の直後に新たな要素を追加する操作は、要素数や位置に依存せず一定時間で行えるという説明が正解となります。