SC情報処理安全確保支援士試験 午前Ⅰ

令和5年度春期 情報処理安全確保支援士 午前Ⅰ 問6

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。
データ個数とデータ1個当たりの探索時間の関係を示す選択肢ア〜エの四つのグラフ。
データ個数とデータ1個当たりの探索時間の関係を示す選択肢ア〜エの四つのグラフ。

選択肢

  1. ア
    (問題の図表を参照)
  2. イ
    (問題の図表を参照)
  3. ウ
    (問題の図表を参照)
  4. エ
    (問題の図表を参照)
解き方のヒントを見る

探索の計算量とグラフ

データ件数と操作回数の関係を読み取るため、計算量の表し方と探索の前提条件を整理する。

この問題で問われていること

理論的な探索時間を比較する際、入力規模と数える操作をどのように定めるか調べてみよう。

探索の計算量とグラフ

理論的な探索時間を比較する際、入力規模と数える操作をどのように定めるか調べてみよう。

確認ポイント

  • 計算量で使う入力規模nは、探索問題では何の件数を表すか。
  • 逐次探索と二分探索について、データ件数を増やすと比較回数がどう変わるかを調べ、グラフに描けるか。
  • 実測した処理時間と理論的な操作回数はどう違い、計算量ではどのような定数を省略するか。 キー、ハッシュ値、衝突という用語を調べ、問題文の条件がどの用語に関係するか確認できるか。
正解と解説を見る

正解

エ

解説

問6の正解は「エ」です。ハッシュ表では,探索対象のキーからハッシュ値を求め,対応する格納位置を調べる。問題の条件ではハッシュ値の衝突がないので,衝突したデータを追加で調べる処理は不要です。このため,理論的な探索時間は表のデータの個数に依存せず一定となり,計算量はO(1)です。横軸が「表の中のデータの個数」,縦軸が「データ1個当たりの探索時間」であることから,水平なグラフが対応する。

正答

正解は「エ」です。ハッシュ表は,キーをハッシュ関数に通して得たハッシュ値から格納位置を求めるため,探索は位置を計算して1回参照するだけで完了する。問題の条件ではハッシュ値の衝突がないので,同じ位置に複数の要素が並ぶことがなく,比較し直す必要もない。したがって探索回数は要素数nに関係なく常に1回であり,1個当たりの探索時間は一定になる。計算量はO(1)であるため,横軸が要素数,縦軸が1個当たりの探索時間のグラフでは水平な直線が対応する。

誤答の理由

ア:要素数が増えるほど探索時間の増加が急になるグラフです。衝突がないハッシュ表では要素数に関係なく1回で位置が求まるため,探索時間が増え続けることはない。

イ:要素数に比例して探索時間が直線的に増えるグラフです。これは先頭から順に比較していく線形探索の特徴であり,ハッシュ表では順に調べる必要がないので当てはまらない。

ウ:要素数が増えると探索時間も増えるが,増加が次第に緩やかになるグラフです。衝突がない場合は要素数によらず一定の時間になるため,この形は表さない。

整理

ハッシュ表の探索はO(1)(一定時間),線形探索はO(n)(要素数に比例),二分探索はO(log n)(対数的に増加)を対比して覚えると整理しやすい。ハッシュ値の衝突が起きると比較の回数が増えるため,衝突がある場合の平均的な探索時間は衝突の処理方法によって変わる点も押さえておきたい。

選択肢ア

不正解。データの個数が増えるほど,探索時間の増加が急になるグラフである。ハッシュ値の衝突がないハッシュ表の探索時間には当てはまらない。

選択肢イ

不正解。データの個数に応じて探索時間が直線的に増えるグラフである。ハッシュ値の衝突がない場合,データを順に調べる必要はないので,当てはまらない。

選択肢ウ

不正解。データの個数が増えると探索時間も増えるが,その増加が次第に緩やかになるグラフである。ハッシュ値の衝突がない場合の一定の探索時間を表していない。

選択肢エ(正解)

正解。データの個数にかかわらず,データ1個当たりの探索時間が一定である。ハッシュ値の衝突がない場合,ハッシュ値から格納位置を直接特定できるため,このグラフに対応する。

学習のポイント

理論的な探索時間を比較する際、入力規模と数える操作をどのように定めるか調べてみよう。

解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。

出典:独立行政法人 情報処理推進機構(IPA)令和5年度春期 情報処理安全確保支援士試験 午前Ⅰ 問6(公式資料:問題冊子(PDF) / 解答例)

関連する過去問一覧

IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針