応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

2.プログラミング > 2.5 探索アルゴリズム

線形探索の問題は
■H26春
問6 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて,与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。
 ここで,検索する従業員番号はランダムに出現し,探索は常に表の先頭から行う。また,与えられた従業員番号がこの表に存在しない確率をaとする。

H26h-問6ans
【正解】エ

■H19春SW
問13 配列上に不規則に並んだ多数のデータの中から,特定のデータを探し出すのに適したアルゴリズムはどれか。
ア 2分探索法 ウ ハッシュ法
イ 線形探索法 エ モンテカルロ法

正解はイ

ハッシュ表探索の問題は以下です。

■H27秋
問5 キーが小文字のアルファベット1文字(a,b,…,zのいずれか)であるデータを,大きさが10のハッシュ表に格納する。ハッシュ関数として,アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは,昇順に連続した2進数が,アルファペット順にコードとして割り当てられている。
ア aとi     イ bとr     ウ cとl     エ dとx
【正解】エ
アルファベットのASCIIコードおよび1の位の数は次のようになります。
アルファベット ASCIIコード 1の位の数
   a    97   7
   b    98   8
   c    99   9
   d    100   0
   ・・・
   i    105   5
   ・・・
   r    114   4
   ・・・
   x    120   0
ただ、ASCIIコードを覚えている人はいないことでしょう。
2つも文字がいくつ離れているのかを考えれば衝突するかがわかります。dとxは、20離れていて、ハッシュ関数は、1の位の数を用いているので、衝突することがわかります。

■H27春
問5 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(r)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x  mod nはxをnで割った余りを表す。
ア a+bがnの倍数
イ a-bがnの倍数
ウ nがa+bの倍数
エ nがa-bの倍数
【正解】イ

■H26春
問19 ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。
H26h-問19
【正解】エ

■H25秋
問7 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x mod n はxをnで割った余りを表す。
ア a+bがnの倍数
ウ nがa+bの倍数
イ a-bがnの倍数
エ nがa-bの倍数

【正解】イ

このページのトップヘ