応用情報技術者試験 応用情報技術者試験 平成30年度秋期 午前 問8: 探索表の構成法を例とともに a ～ c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。 a コード順に格納した探索表

正解

ア. a：2 分探索 b：線形探索 c：ハッシュ表探索

正答率 61.9%（1,182人中 732人が正解）

問題の解説

探索表の並べ方によって、使える探索手法が決まる。コード順に整列された表は、中央の値と比べて探索範囲を半分ずつ絞れる 2 分探索が使え、整列されていない表は先頭から順に調べる線形探索になる。コードから格納位置を計算で一意に決める表は、ハッシュ表探索の構成である。したがって a が 2 分探索、b が線形探索、c がハッシュ表探索となる。

選択肢ごとの解説

• ア正しい。コード順の表は 2 分探索、使用頻度順でコードの大小に規則がない表は線形探索、コードから格納位置を決めた表はハッシュ表探索が適する。
• イコード順の表に 2 分探索を使う点は合っている。しかし、使用頻度順の表はハッシュ表探索に必要な構成ではなく、位置を計算で決めた表に線形探索を使うのも適さない。
• ウ整列済みの表に線形探索を使うと、整列されている利点を生かせない。また、使用頻度順の表はコードの大小順ではないので 2 分探索は使えない。
• エコード順の表に線形探索を使うと整列の利点を生かせず、使用頻度順の表にハッシュ表探索は使えない。位置を計算で決めた表は整列されておらず、2 分探索も使えない。