応用情報技術者過去問題 平成21年春期 午後問2

⇄問題文と設問を画面2分割で開く⇱問題PDF⇱解答用紙PDF

問2 プログラミング

探索アルゴリズムであるハッシュ法の一つ,チェイン法に関する次の記述を読んで,設問1〜4に答えよ。

 配列に対して,データを格納すべき位置(配列の添字)をデータのキーの値を引数とする関数(ハッシュ関数)で求めることによって,探索だけではなく追加や削除も効率よく行うのがハッシュ法である。
 通常,キーのとり得る値の数に比べて,配列の添字として使える値の範囲は狭いので,衝突(collision)と呼ばれる現象が起こり得る。衝突が発生した場合の対処方法の一つとして,同一のハッシュ値をもつデータを線形リストによって管理するチェイン法(連鎖法ともいう)がある。

 8個のデータを格納したときの例を図1に示す。
 このとき,キー値は正の整数,配列の添字は0〜6の整数,ハッシュ関数は引数を7で割った剰余を求める関数とする。
pm02_1.gif/image-size:470×264
 このチェイン法を実現するために表に示す構造体配列及び関数を使用する。
pm02_2.gif/image-size:490×204
 構造体を参照する変数からその構造体の構成要素へのアクセスには"."を用いる。例えば,図1のキー値 25 のデータは table[4].data でアクセスできる。また,構造体の実体を生成するには,次のように書き,生成された構造体への参照が値になる。
 new Node(key,data,nextNode)

〔探索関数 search〕
 探索のアルゴリズムを実装した関数 search の処理手順を次の(1)〜(3)に,そのプログラムを図2に示す。
  • 探索したいデータのキー値からハッシュ値を求める。
  • ハッシュ表中のハッシュ値を添字とする要素が参照する線形リストに着目する。
  • 線形リストのノードに先頭から順にアクセスする。キー値と同じ値が見つかれば,そのノードに格納されたデータを返す。末尾まで探して見つからなければ null を返す。
pm02_3.gif/image-size:414×222
〔追加関数 addNode〕
 データの追加手続を実装した関数 addNode の処理手順を次の(1)〜(3)にプログラムを図3に示す。図3中のには,図2中のと同一のものが入る。
  • 追加したいデータのキー値からハッシュ値を求める。
  • ハッシュ表中のハッシュ値を添字とする要素が参照する線形リストに着目する。
  • 線形リストのノードに先頭から順にアクセスする。キー値と同じ値が見つかれば,キー値は登録済みであり追加失敗として false を返す。末尾まで探して見つからなければ,リストの先頭にノードを追加して true を返す。
pm02_4.gif/image-size:463×261
〔チェイン法の計算量〕
 チェイン法の計算量を考える。
 計算量が最悪になるのは,場合である。しかし,ハッシュ関数の作り方が悪くなければ,このようなことになる確率は小さく,実際上は無視できる。
 チェイン法では,データの個数をnとし,表の大きさ(配列の長さ)をmとすると,線形リスト上の探索の際にアクセスするノードの数は,線形リストの長さの平均n/mに比例する。mの選び方は任意なので,nに対して十分に大きくとっておけば,計算量がとなる。この場合の計算量は2分探索木によるO(log n)より小さい。

設問1

衝突(collision)とはどのような現象か。"キー"と"ハッシュ関数"という単語を用いて,35字以内で述べよ。

-解答入力欄-


-解答例・解答の要点-

  • 違うキーの値でも,ハッシュ関数を適用した結果が同じになること (30文字)

-解説-

この設問の解説はまだありません。

設問2

〔探索関数 search〕について,(1),(2)に答えよ。
  • 図1の場合,キー値が23のデータを探索するために,ノードにアクセスする順序はどのようになるか。"key1→key2→…→23"のように,アクセスしたノードのキー値の順序で答えよ。
  • 図2中のに入れる適切な字句を答えよ。

-解答入力欄-

    • ア:
    • イ:
    • ウ:

-解答例・解答の要点-

    • 16→37→23
    • ア:node.keyがkeyと等しい
    • イ:node ← node.nextNode
    • ウ:null

-解説-

この設問の解説はまだありません。

設問3

〔追加関数 addNode〕のプログラム,図3中のに入れる適切な字句を答えよ。

-解答入力欄-

  • エ:
  • オ:

-解答例・解答の要点-

  • エ:key, data, table[hash]
  • オ:table[hash]

-解説-

この設問の解説はまだありません。

設問4

〔チェイン法の計算量〕について,(1),(2)に答えよ。
  • カに入れる適切な字句を25字以内で答えよ。
  • キに入れる計算量を O 記法で答えよ。

-解答入力欄-

    • カ:
    • キ:

-解答例・解答の要点-

    • カ:すべてのキーについてハッシュ値が同じになる (21文字)
    • キ:O(1)

-解説-

この設問の解説はまだありません。
問2成績

平成21年春期 午後問題一覧

問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 採点講評
© 2010-2021 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop