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

正解：ア

AI解説

探索手法は表の構成に依存する。キーの値の順に整列された表なら中央と比較して範囲を半分に絞る2分探索、整列されていない表なら先頭から順に調べる線形探索、キーから計算した位置に格納する(空きが混在する)表ならハッシュ表探索が適する。例a〜cの構成にこの対応を当てはめると、a:2分探索、b:線形探索、c:ハッシュ表探索のアが正しい。 ア: 正しい。aはコードが整列済みの表なので2分探索、bは整列されていない表なので線形探索、cはコードから計算した位置に空きを設けて格納する表なのでハッシュ表探索が最適である。 イ: bとcの対応が逆である。空きを含みキーから格納位置が決まる表がハッシュ表であり、未整列の表には線形探索を使う。 ウ: aとbの対応が逆である。2分探索は整列済みの表にしか適用できない。 エ: 2分探索を空き混在のハッシュ的な表に割り当てており、整列表・未整列表との対応も崩れているため誤りである。 💡 「整列済み→2分探索」「未整列→線形探索」「キーから位置を計算・空きあり→ハッシュ」の3対応を覚える。2分探索は整列が前提という点が最大の判断基準である。