平成22年度秋期 応用情報技術者試験 午前 問6

正解：ア

AI解説

探索手法の平均計算量は、データ構造に応じて異なる。整列済みの配列であれば2分探索（平均O(log n)）、未整列の配列や線形リストであれば線形探索（平均O(n)）、ハッシュ表であればハッシュ表探索（平均O(1)）が最適となる。設問の構成例a～cが示すデータ構造（整列済み表・未整列表・ハッシュ表）に対して、それぞれ最も計算量が小さくなる探索手法を正しく対応付けた組合せが正解となる。 ア: 正しい。整列済みの表には2分探索、未整列の表には線形探索、ハッシュ表にはハッシュ表探索という、各データ構造に対して平均計算量が最小になる探索手法の組合せである。 イ: ハッシュ表探索と線形探索の対応が入れ替わっており、各データ構造に対する最適な探索手法の組合せとして適切でない。 ウ: 2分探索と線形探索の対応が入れ替わっており、整列済みの表に線形探索を当てるなど、最適な組合せになっていない。 エ: 線形探索・ハッシュ表探索・2分探索の対応関係が本来の組合せと異なっており、平均計算量が最小にならない。 💡 探索手法の使い分けは「整列済み配列→2分探索」「未整列→線形探索」「ハッシュ表→ハッシュ探索」という対応をデータ構造とセットで覚えておく。