アルゴリズムとプログラミング
基本情報技術者試験｜ハッシュ表の衝突処理におけるチェイン法(連鎖法)の説明
ハッシュ表の衝突処理におけるチェイン法(連鎖法)の説明として最も適切なものはどれか。
ア衝突が起きたら表の別の空きスロットを規則的に探し、データ自体を表内に格納する
イ同じハッシュ値のデータを連結リストでつなぎ、各スロットがそのリストの先頭を指す
ウ衝突時にハッシュ関数を使わず先頭から順に空きを線形探索して全件比較する
エ衝突が起きた瞬間に表全体を2倍に拡張し、全データを必ず再配置してから格納する
正解
イ．同じハッシュ値のデータを連結リストでつなぎ、各スロットがそのリストの先頭を指す
チェイン法は各スロットに連結リストを持たせ、ハッシュ値が衝突したデータを同じリストにつなぐ。スロットはリストの先頭を指し、探索時はそのリストをたどるため正しい。
?選択肢ごとの解説
ア ×衝突時に表内の別の空きスロットを規則的に探してデータを表内に置くのはオープンアドレス法(開番地法)の説明であり、チェイン法とは別方式である。
イ ○チェイン法は各スロットに連結リストを持たせ、ハッシュ値が衝突したデータを同じリストにつなぐ。スロットはリストの先頭を指し、探索時はそのリストをたどるため正しい。
ウ ×ハッシュ関数を使わず先頭から線形探索して全件比較するのは単なる線形探索であり、ハッシュ値で振り分けるチェイン法の説明ではない。
エ ×衝突のたびに表を2倍拡張して全再配置するのはリハッシュ(拡張)の話で、衝突を都度連結リストで吸収するチェイン法の基本動作とは異なる。
アルゴリズムとプログラミングの他の問題
要素数nの単方向連結リストにおいて、先頭ノードへのポインタが分かっているとき、リストの先頭に新しい要素を1個挿入する処理の計…平衡が保たれた2分探索木に約100万個の要素を格納したとき、根から葉までの高さ(段数)はおよそどの程度になるか。なおlog2…スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくらか。次のデータ構造で目的の値を1個探索するときの平均計算量を比べる。最も速い(オーダが小さい)ものはどれか。ただし表引き方式は衝…単純選択ソートで要素数nの配列を昇順に整列するとき、要素の比較回数は最悪・平均ともにおよそどれで表されるか。挿入ソートの計算量について最も適切に述べたものはどれか。シェルソートの基本的な考え方を最も適切に説明したものはどれか。ヒープソートの最悪計算量と安定性の組合せとして正しいものはどれか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0128