スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

基本情報技術者 過去問 線形探索法、2分探索法、ハッシュ法

■H14春FE問1

探索に要する平均探索回数が最も少ないものはどれか。

ア 2分探索木を用いた探索
イ 衝突の確率が無視できるほど小さいハッシュ表を用いた探索
ウ 整列済みの配列を用いた2分探索
エ 重複登録のないリストを用いた線形探索


■H13春SW問11

不規則に配列されている多数のデータの中から、特定のデータを探し出すのに適切なアルゴリズムはどれか。

ア 2分探索法
イ 線形探索法
ウ ハッシュ法
エ モンテカルロ法




■H14春FE問1
答え:イ

データの件数を n とすると、逐次探索ではn/2回、2分探索ではlog2n回となる。

ハッシュ表を用いた探索では、探索キーでハッシュ関数の値を計算した結果が探索するデータの場所を示す。このとき、複数のキー値から同じハッシュ値になればデータが衝突するので新たな探索が必要になるが、衝突を無視すれば平均比較回数は1回といってよい。

■H13春SW問11
答え:イ

多数のデータが不規則に配列されている点に注目すると、適切なアルゴリズムは線形探索法になる。2文探索法やハッシュ法は、あらかじめデータを適切に並べておく必要がある。

ここまでは、以下の問題集を参照したものです。

基本情報技術者予想問題集〈2006〉 (情報処理技術者試験対策書)
基本情報技術者予想問題集〈2006〉 (情報処理技術者試験対策書)
アイテック情報処理技術者教育センター 2005-12
売り上げランキング : 651453


Amazonで詳しく見る
by G-Tools


ここからは下記の『定本 Cプログラマのためのアルゴリズムとデータ構造』からの引用・まとめです。ブックオフで105円で購入したものですが、勉強になりますし結構役に立っています。

内容としては、初学者にとっては決して簡単なものではありませんが、基礎的な知識を押さえていれば、理解しながら読み進めていくことができます。

僕はC言語はわかりませんが、プログラミングの基礎を多少でも知っていれば、例として出ているソースコードも100%じゃないにしろ、大雑把に理解することはできます。

お勧めの一冊です。

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
ソフトバンククリエイティブ 1998-03
売り上げランキング : 39376

おすすめ平均 star
star今は亡き、Cmagazineの連載
star基礎をやさしく学べる
star職業としてプログラマを目指す以外の人はこれで十分

Amazonで詳しく見る
by G-Tools


線形探索法 linear search
配列を端から順番にスキャンしながらキーの比較を行う。
例として下記のコードがあげられています。

struct {
int key;
int data;
} table[100];

int n;

int search(int key)
{
int i;

i = 0;
while (i < 0){
if (table[i],key == key)
return (table[i].data);
i++;
}
return -1;
}



2分探索法 Binary Search
線形探索法は、O(n)のアルゴリズムですが、探索を行うアルゴリズムにはもっと性能がいいものもあります。2分探索法(Binary Search)です。

2分探索法とは、あらかいjめキーの昇順(降順でもOK)に整列されている配列に対足て、ある特定のキーをもつデータを探し出す探索法です。

例えば、要素1000個が登録されている配列からデータを探すケースの場合、
線形探索法では、平均n/2 = 1000/2 500回。
それに対し、2分探索法では、log2n =log2 1000 で約 10となるわけですね。(2の8乗(1バイト)が256で×2(9乗)で512、×2(10乗)で1024)。

ハッシュ法 hashing
データの探索を話題にするのにハッシュ法(hashing)に触れないわけにはいかないでしょう。ハッシュ法では、キーの値から配列の添え字を得る関数(ハッシュ関数)を使って高速に探索を行うことができます。例えば、大きさ100の配列を使って整数のキーをもつデータを扱うには、ハッシュ関数h(key)を、

h(key) = key % 100

と定めます。

key =2034のデータは、

h(2034) = 2034 % 100 =34

とうことで、配列の添え字34の要素に格納されていることになります。


アルゴリズムに関しては、下記のシリーズも参考になります。

Part1 アルゴリズムと計算量を理解する
http://itpro.nikkeibp.co.jp/article/lecture/20061127/254837/?ST=lecture&P=1

(44min)


スポンサーサイト

コメントの投稿

非公開コメント

写真素材 PIXTA
価格.com自動車保険 比較・見積もり
Search
Profile

itandenglish

Author: Makoto
外資金融系企業のIT部門で働いています。キャリアップを目指してIT系、英語系を中心に資格取得を目指して勉強中。
趣味は写真撮影、など。

Calendar
09 | 2017/10 | 11
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -
Latest Entry
Archive
Category
Latest Comment
Latest Trackback
e-Words
RSS
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。