アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20210725 実施分 問9
探索表の構成法を例とともに a ～ c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
a コード順に格納した探索表（8 行，上から 4 行に格納）:
b コードの使用頻度順に格納した探索表（8 行，上から 4 行に格納）:
c コードから一意に決まる場所に格納した探索表（8 行）:
選択肢の組合せ表:
| コード | データ |
|---|---|
| 120380 | …… |
| 120381 | …… |
| 120520 | …… |
| 140140 | …… |
| (空) | |
| (空) | |
| (空) | |
| (空) |
| コード | データ |
|---|---|
| 120381 | …… |
| 140140 | …… |
| 120520 | …… |
| 120380 | …… |
| (空) | |
| (空) | |
| (空) | |
| (空) |
| コード | データ |
|---|---|
| (空) | |
| 120381 | …… |
| (空) | |
| 120520 | …… |
| 140140 | …… |
| (空) | |
| 120380 | …… |
| (空) |
| a | b | c | |
|---|---|---|---|
| ア | 2 分探索 | 線形探索 | ハッシュ表探索 |
| イ | 2 分探索 | ハッシュ表探索 | 線形探索 |
| ウ | 線形探索 | 2 分探索 | ハッシュ表探索 |
| エ | 線形探索 | ハッシュ表探索 | 2 分探索 |
- ア a：2 分探索，b：線形探索，c：ハッシュ表探索
- イ a：2 分探索，b：ハッシュ表探索，c：線形探索
- ウ a：線形探索，b：2 分探索，c：ハッシュ表探索
- エ a：線形探索，b：ハッシュ表探索，c：2 分探索
出典：基本情報技術者試験 科目A免除 修了試験 20210725 実施分 問9
答えと解説を見る
正解：ア
覚える知識
2分探索の前提条件(整列済みデータ)
2分探索は整列済みの表に対して中央値と比較し探索範囲を半分に絞る手法である。
この問題で必要なこと
コード順整列済みの表は 2 分探索、頻度順で並べた表は先頭から調べる線形探索、キーから格納位置が一意に決まる表はハッシュ探索。
ひっかけ
整列されていない頻度順表に2分探索を使う誤り、またハッシュと線形探索の取り違え。
この知識の出題：本試験系 2 回・免除試験 4 回（公開問題での観測値）