基本情報技術者試験まとめ

基本情報技術者試験に出題される内容をまとめました。

探索アルゴリズム

線形探索法

 先頭から順番に目的のデータと比較し、一致するデータを探すアルゴリズム

 整列されていない状態で目的のデータを探索するには向いているが、大量のデータを探索するには不向き。

 線形探索法では、 n個のデータの中から目的のデータを見つけるまでに、最小で1回、最大でn回、データの比較を行う必要がある。したがって、平均比較回数は(n+1)/2回となる。

 

番兵

 線形探索法で配列構造のデータを探索する場合、探索する前にあらかじめ最後のデータの後ろに目的のデータを入れておくこと

 

2分探索法

 あらかじめデータが大きい順もしくは小さい順に整列されている場合に使う。まずデータを2等分し、探索範囲の中央の値と探索データを比較する。探索データの方が小さければ、目的データの場所を前半に絞り込む。これを繰り返す。

 平均比較回数はlog2n

 

ハッシュ探索法

 データ格納場所のアドレス値を、あらかじめ関数を使った計算で決めておくアルゴリズム

 格納先を決めるために用いられる関数をハッシュ関数ハッシュ関数によって求められるアドレス値をハッシュ値と言う。データを探索する際には、ハッシュ関数を計算してハッシュ値を求めることで、格納場所を割り出す。衝突が発生しない限り、必ず1回でデータを見つけることができる。

 衝突が起こった場合には、配列の各要素をリスト構造にして、新しい場所にデータを格納する。

 

一様分布

 ハッシュ探索法において、衝突の確率が最も低くなるのは、ハッシュ値が一様分布にある時である。一様分布とは、サイコロの目の出る確率など、全ての事象が起こる確率が等しい現象である。