[0479] 基数変換法

平成14年度春期 基本情報処理技術者試験より
0000 ~ 4999 のアドレスをもつハッシュ表があり,レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が 55550 のときのアドレスはどれか。ここで,基数変換法ではキー値を 11進数と見なし,10進数に変換した後,下4けたに対して 0.5 を乗じた結果(小数点以下は切捨て)をレコードのアドレスとする。
0260
2525
2775
4405

正解

解説

 レコードを記憶域に登録する場合,格納方法を工夫しないと,登録される記憶域に偏りが発生することがあります。例えば,商品コードをキーとして,そのキー値の範囲によって格納する記憶域を決定する場合,商品コードの値が偏っていると,記憶域のデータ格納数に偏りが発生します。格納効率,アクセス速度といった点で非効率的な状態であるといえます。




 データを全ての記憶域にまんべんなく分散させる方法として,ハッシングがあります。データのキー値にハッシュ関数と呼ばれる演算を施して,ある一定範囲のランダムな数値に変換してしまいます。0 ~ 3 までの 4個の記録域へ商品データを登録する場合,商品コードから 計算結果が 0 ~ 3 となる値を生成することで各記録域へまんべんなくデータを配置することが可能です。




 ハッシングを行なう計算手順は,除算法,重ね合わせ法,基数変換法などがあります。この問題では,基数変換法を利用してハッシュ値を求めます。計算手順は,問題文の通り,(1)「キー値を11進数と見なし,10進数に変換した後」,(2)「下4けたに対して0.5を乗じた結果(小数点以下は切捨て)をレコードのアドレスとする」の手順で行ないます。

(1)キー値を11進数と見なし,10進数に変換

キー値は 55550 で,これが 11進数であるとみなすと,
    55550(11)
    = 5 × 114 + 5 × 113 + 5 × 112 + 5 × 111
    = 5 × 11 ×( 113 + 112 + 111 + 110
    = 5 × 11 ×( 1331 + 121 + 11 + 1 )
    = 55 × 1464
    80520
(2)下4けたに対して0.5を乗じた結果(小数点以下は切捨て)をレコードのアドレスとする

下4桁は 0520 なので,
    520 × 0.5 = 260
 よって,求めるアドレスは 0260 のアが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題