基本情報技術者 2014年秋期午前（科目A）問02

問題文

0000~4999のアドレスをもつハッシュ表があり、レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が55550のときのアドレスはどれか。ここでの基数変換法は、キー値を11進数とみなし、10進数に変換した後、下4桁に対して0.5を乗じた結果(小数点以下は切捨て)をレコードのアドレスとする。

選択肢

ア：0260（正解）

イ：2525

ウ：2775

エ：4405

基数変換法を用いるハッシュ表のアドレス算出【午前2 解説】

要点まとめ

結論：キー値55550を11進数として10進に直すと80520になり、下4桁0520の0.5倍でアドレスは0260になります。
根拠：11進数の桁重みは $1 1^{0}, 1 1^{1}, 1 1^{2}, 1 1^{3}, 1 1^{4}$ で、各桁を重みで乗じて合計し下4桁を切り出す規則に従います。
差がつくポイント：進数変換の桁重みを間違えないことと、下4桁の取り扱い（先頭0を保持）と小数点以下切捨てに注意すること。

正解の理由

キー値を11進数とみなして10進に変換します。
55550（11進）の各桁に重みを掛けると、

5 \times 1 1^{4} + 5 \times 1 1^{3} + 5 \times 1 1^{2} + 5 \times 11 + 0 = 80520

となります。
この10進数の下4桁は0520（すなわち520）で、これに0.5を乗じると260.0、切捨てても260。4桁表記すると「0260」なので、正解はアです。

よくある誤解

「そのまま10進数として処理する」：55550を十進数扱いにすると下4桁5550の0.5倍で2775と誤答になります。
「桁重みを1桁ずらす／指数を間違える」：11進のそれぞれの桁に対応する $1 1^{k}$ を誤ると変換値が大きくずれます。
「下4桁の先頭0を無視する」：0520を520と扱って表示桁数を揃えないと出力フォーマットで不一致になります。

解法ステップ

問題の「キー値を11進数とみなす」を確認する。
各桁に対応する重みを用いて10進数に変換する： $5 \times 1 1^{4} + 5 \times 1 1^{3} + 5 \times 1 1^{2} + 5 \times 11 + 0$ 。
得られた10進数から下4桁（= 10,000で割った余り）を取り出す。
その下4桁に0.5を乗じ、小数点以下を切り捨てる。
得られた数値を4桁表示（必要なら先頭に0を付加）してアドレスとする。

選択肢別の誤答解説

ア: 0260 — 正解。上記手順で得られる値です。
イ: 2525 — 誤答。これは下4桁が5050と誤認して半分にした場合に出る値で、桁計算ミスが原因です。
ウ: 2775 — 誤答。キーを11進数ではなく十進数とみなし、下4桁5550の0.5倍を計算した結果（5550×0.5=2775）です。
エ: 4405 — 誤答。進数変換や下4桁の抽出で複数箇所誤った場合に生じる不正解で、典型的には桁重みの乗算ミスや桁ずらしの混同によります。

補足コラム

基数変換法では「キーを指定基数の数として解釈してから10進に戻す」手順が重要です。一般化すると、桁列

d_{n} d_{n - 1} \dots d_{0}

を基数

b

として解釈する場合の10進値は

\sum_{k = 0}^{n} d_{k} b^{k}

です。本問では

b = 11

、下位4桁を取るために最終的に

mod 10000

を取ってから0.5を掛けています。実装例（Python）も参考にしてください。

def compute_address_from_base11(key_str):
    # key_strは"55550"のような文字列
    b = 11
    dec = sum(int(d) * (b ** i) for i, d in enumerate(reversed(key_str)))
    lower4 = dec % 10000
    addr = lower4 // 2  # 0.5を乗じて切捨てと同義
    return f"{addr:04d}"

print(compute_address_from_base11("55550"))  # -> "0260"

FAQ

Q. 下4桁の取り出しはなぜ10,000で割った余りなのですか？
A. 下4桁とは10進で4桁分（

1 0^{4}

）の位より下を指すため、10,000で割った余りが下4桁に相当します。

Q. 0.5を掛ける操作で切捨てるのはどう扱えばよいですか？
A. 小数点以下を切捨てるので、整数演算であれば下4桁を2で整数除算（切捨て）するのと等価です。

Q. 表示は必ず4桁にする必要がありますか？
A. 問題のアドレス空間表記が0000～4999なので、先頭0を含めた4桁表示が求められます。

関連キーワード: ハッシュ表、基数変換法、進数変換、11進数、アドレス計算、桁重み、下位桁抽出、整数演算、切捨て、試験対策

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！