アルゴリズムとプログラミング
基本情報技術者試験｜スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくら…
スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくらか。
ア負荷率は約1.43
イおよそ0.35
ウ0.7
エおおよそ0.5付近
正解
ウ．0.7
ハッシュ表の負荷率はα=格納データ数÷スロット数で定義される。350÷500=0.7となり、表の7割が埋まっている状態を表すため正しい。
?選択肢ごとの解説
ア ×約1.43は500÷350であり、分子と分母を逆に取ったため負荷率が1を超えてしまった誤りである。チェイン法でない限り占有率は1以下になる。
イ ×およそ0.35は350を1000で割るなど分母を取り違えた誤りで、分母は実際のスロット数500とすべきである。
ウ ○ハッシュ表の負荷率はα=格納データ数÷スロット数で定義される。350÷500=0.7となり、表の7割が埋まっている状態を表すため正しい。
エ ×おおよそ0.5付近はスロット数を増減して見積もるなどの概算ミスであり、正確には350÷500=0.7である。
アルゴリズムとプログラミングの他の問題
次のデータ構造で目的の値を1個探索するときの平均計算量を比べる。最も速い(オーダが小さい)ものはどれか。ただし表引き方式は衝…単純選択ソートで要素数nの配列を昇順に整列するとき、要素の比較回数は最悪・平均ともにおよそどれで表されるか。挿入ソートの計算量について最も適切に述べたものはどれか。シェルソートの基本的な考え方を最も適切に説明したものはどれか。ヒープソートの最悪計算量と安定性の組合せとして正しいものはどれか。衝突がほとんど起きないよう設計されたハッシュ表を用いた探索の、平均的な計算量はどれか。補間探索(内挿探索)が二分探索より高速に動作しやすいのは、データがどのような場合か。要素数16の配列をマージソートで整列する。配列を半分ずつに分割していくとき、要素数が1になるまでに必要な分割の段数は何段か。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0131