平成26年度 秋期 午前 問2
アルゴリズム
基数変換法に関する問題
0000 〜 4999 のアドレスをもつハッシュ表があり,レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が 55550 のときのアドレスはどれか。ここでの基数変換法は,キー値を 11 進数とみなし,10 進数に変換した後,下 4 桁に対して 0.5 を乗じた結果(小数点以下は切捨て)をレコードのアドレスとする。
- ア0260
- イ2525
- ウ2775
- エ4405
答えと解説を見る
✓ これが正解ア0260
解説
11 進とみて 10 進に直し、下 4 桁を半分にします。
この問いの手順は設問の中に全部書かれていて、三つの段からできています。第 1 段はキー値を 11 進数とみなして 10 進数に直すこと、第 2 段はその結果の下 4 桁だけを取り出すこと、第 3 段はそこに 0.5 を掛けて小数点以下を切り捨てることです。判定の軸は、三つの段を一つも飛ばさずに順に当てはめられるかという一点です。第 1 段では桁の重みが 14641、1331、121、11、1 になるので、5、5、5、5、0 という並びから 73205 + 6655 + 605 + 55 + 0 で 80520 が得られます。第 2 段でその下 4 桁を取ると 0520 になり、第 3 段で 520 に 0.5 を掛けて 260 が残ります。アドレスは 4 桁で書くので 0260 です。下 4 桁に 0.5 を掛ける段が置かれているのは、値を 0000 から 4999 の範囲に必ず収めるための工夫で、手順の意味もここで通ります。
ほかの選択肢はなぜ違うのか
- イ2525:この数になるには半分にする前の値が 5050 でなければなりませんが、その数は基数の直しでも桁の取り出しでも現れません。設問の手順のどこからも導けない値です。
- ウ2775:基数を直す段を飛ばし、キー値 55550 の末尾 4 桁 5550 にそのまま 0.5 を掛けた形です。11 進数とみなして 10 進数に変換するという最初の指示が働いていません。
- エ4405:変換の向きが逆になった形です。55550 を 10 進数の側とみなして 11 進数へ直すと 38810 になり、その末尾 4 桁 8810 の半分がこの数です。設問はその逆を求めています。
この問題の用語
- ハッシュハッシュ関数で作られた値そのもの。元に戻せないので、中身を見せずに同じかどうかだけを確かめるのに使えます。
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典:平成26年度 秋期 基本情報技術者試験 午前 問2
同じ用語が出る問題
- 令和5年度 科目B 問4:ハッシュに関する問題(ハッシュ)
- 平成31年度 春期 午前 問18:理想的なハッシュ法の説明(アルゴリズム)
- 平成30年度 秋期 午前 問2:排他的論理和に関する問題(アルゴリズム)
- 平成30年度 春期 午前 問7:表探索におけるハッシュ法の特徴(ハッシュ)
- 平成29年度 春期 午前 問27:ソートマージ結合法に関する記述(ハッシュ)
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する(メールが開きます)