平成25年度春期 応用情報技術者試験 午前 問5

正解：ア

AI解説

探索手法は表の構成で決まる。a：コード順に整列され空きのない表→大小比較で範囲を半分に絞れるので2分探索。b：整列されていない表→先頭から順に調べる線形探索しかできない。c：コードから計算した位置に格納し空きがある表→コードをハッシュ関数で位置に変換して一発で当てるハッシュ表探索。よってアの組合せが正しい。 ア: 正しい。整列済み＝2分探索、未整列＝線形探索、計算位置格納（空きあり）＝ハッシュ表探索という対応である。 イ: bとcが逆である。空きのある計算位置格納の表がハッシュ用で、未整列の詰めた表は線形探索用である。 ウ: aとbが逆である。2分探索は整列済みの表にしか適用できない。 エ: 2分探索を空きのある表に、ハッシュを未整列の表に割り当てており、いずれの特徴とも合わない。 💡 「2分探索＝整列済みが前提」「ハッシュ＝表に空きがあり格納位置をコードから計算」「線形＝何の前提もいらない」と特徴で覚える。計算量はO(log n)、O(1)（平均）、O(n)の順である。