トップ過去問一覧応用情報技術者 平成22年・秋 > 問6
問6

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

 a コード順に格納した探索表

 b コードの使用頻度順に格納した探索表

 c コードから一意に決まる場所に格納した探索表

コード

データ

コード

データ

コード

データ

120380

……

120381

……

 

 

120381

……

140140

……

120381

……

120520

……

120520

……

 

 

140140

……

120380

……

120520

……

 

 

 

 

140140

……

 

 

 

 

 

 

 

 

 

 

120380

……

 

 

 

 

 

 

 

.           a           b           c

○正解
×不正解

2 分探索

線形探索

ハッシュ表探索

2 分探索

ハッシュ表探索

線形探索

線形探索

2 分探索

ハッシュ表探索

線形探索

ハッシュ表探索

2 分探索

解説

それぞれの探索方法の特性を押さえて選択しましょう。一般な状況では線形探索は2分探索より計算量は少なくて済みますが出現頻度が偏っている場合は線形探索が早いことがあります。

 

□ 線形探索

先頭から順番に探索していきます。

 

□ 2分探索

探索範囲を半分に分けて探索を繰り返します。順番に並びかえられている必要があります。

 

□ ハッシュ表探索

探索するデータそのものでなく別途計算・処理を行ったものを探索します。探索するデータとは別に計算されたハッシュを用意する又は計算などを行って場所が一意に決まるなどといった必要があります。

 

ここではコード順に格納した一般的な構成表と使用頻度順に並び替えたものがそれぞれ2分探索と線形探索が適切で残るものがハッシュ表探索になります。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。