必ず受かる情報処理技術者試験

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験,基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 応用情報技術者
  3. 平成22年度秋季問題一覧
  4. 平成22年度秋季問題6-解答・解説-分析

平成22年度秋季問題

問題6

探索表の構成法を例とともにa~cに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

探索表の構成法を例とともにa~cに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

解答:ア

<解説>

[a コード順に格納した探索表:2分探索]
2分探索は、予めソートされたデータ列を二つに分けて、そのどちらに検索対象が含まれているか判断するという手順を再帰的に繰り返していく検索方法。
⇒aは、 コード順に格納されているので、2分探索法が適している。
[b コードの使用頻度順に格納した探索表:線形探索]
線形探索は、対象データを検索範囲のデータと先頭から順に1つずつ比較し、一致するものを検索する方法。
⇒bは、使用頻度順にならんでいるので先頭から順番に検索すると早く見つけることができるので、線形探索が適している。
[c コードから一意に決まる場所に格納した探索表:ハッシュ探索]
ハッシュ探索は、キーの値を基に格納先(記録媒体上)のアドレスを算出し、そのアドレス位置にあるデータを検索する方法。
⇒cは、コードから格納場所を探索するのでハッシュ探索が適している。

したがって、アが正解である。

分類

キーワード