情報処理安全確保支援士試験の公開問題
2023 春 午前I 問06
このページはIPA Advancedが運営する非公式の学習用ページです。IPAとの提携・公認を示すものではありません。
問題文
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。
選択肢
- ア: 添付の公式問題ページの問6にある，ラベル「ア」のグラフ。
- イ: 添付の公式問題ページの問6にある，ラベル「イ」のグラフ。
- ウ: 添付の公式問題ページの問6にある，ラベル「ウ」のグラフ。
- エ: 添付の公式問題ページの問6にある，ラベル「エ」のグラフ。
解説の要点
添付の公式解答PDFの午前Ⅰ試験の表では，問6の正解は「エ」です。ハッシュ表では，探索対象のキーからハッシュ値を求め，対応する格納位置を調べる。問題の条件ではハッシュ値の衝突がないので，衝突したデータを追加で調べる処理は不要です。このため，理論的な探索時間は表のデータの個数に依存せず一定となり，計算量はO(1)です。横軸が「表の中のデータの個数」，縦軸が「データ1個当たりの探索時間」であることから，水平なグラフが対応する。
理論的な探索時間を比較する際、入力規模と数える操作をどのように定めるか調べてみよう。
関連する問題一覧
公式出典
訂正・編集方針
解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。