ウカマル応用情報技術者ログイン

平成26年度 春期 応用情報技術者 問19

テクノロジ系

ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。

選択肢

選択肢の図

図の内容(文字)
ア
縦軸:データ1個当たりの探索時間,横軸:表の中のデータの個数(原点0)。データの個数が増えるにつれ,探索時間が緩やかに増加し始め,その後急激に増加する曲線(下に凸)。
イ
縦軸:データ1個当たりの探索時間,横軸:表の中のデータの個数(原点0)。データの個数に比例して探索時間が増加する右上がりの直線。
ウ
縦軸:データ1個当たりの探索時間,横軸:表の中のデータの個数(原点0)。データの個数が増えるにつれ,探索時間が急に増加した後,増加が緩やかになり一定値に近づく曲線(上に凸)。
エ
縦軸:データ1個当たりの探索時間,横軸:表の中のデータの個数(原点0)。データの個数にかかわらず探索時間が一定の水平な直線。
正解と解説

正解 エ

衝突がなければ、ハッシュ表はキーからハッシュ値を計算して格納位置へ直接アクセスできます。そのため、探索時間はデータの個数にかかわらず一定(O(1))です。

ハッシュ表では、キーにハッシュ関数を適用して格納位置を求め、その位置を1回で参照します。問題文に「複数のデータが同じハッシュ値になることはない」とあるので、衝突の処理は起きません。データの個数が増えても、1個当たりの探索時間は変わりません。グラフは縦軸の探索時間が横軸の個数に関係なく一定になる水平な直線、つまりエです。

ア:データ数が増えるほど探索時間が急に増えるグラフです。衝突がないハッシュ表では、探索時間はデータ数に左右されません。

イ:データ数に比例して探索時間が増えるのは線形探索で、計算量はO(n)です。

ウ:増加が次第に緩やかになるのは、計算量がO(log n)の二分探索に近い形です。

出典:平成26年度 春期 応用情報技術者試験 問19

全年度から出題。10問で実力を判定します。登録不要。

出典:平成26年度 春期 応用情報技術者試験 問19(独立行政法人情報処理推進機構)

解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方