平成21年度春季解答

問題1

数値を2進数で格納するレジスタがある。このレジスタに正の整数 x を設定した後, "レジスタの値を2ビット左にシフトして，ｘを加える”操作を行うと，レジスタの値は x の何倍になるか。ここで，あふれ（オーバフロー）は，発生しないものとする。

ア	3
イ	4
ウ	5
エ	6

解答：ウ

＜解説＞

1 ビット左シフトするごとに 2 倍になるので，x を 2 ビット左シフトしたものに x を加えると，x×2×2＋x＝5x→ 5 倍になる。よってウが正解である。

下記より、(3)₁₀から(15)₁₀になる（5倍）ことが分かる。

1. レジスタの値を2ビット左にシフトする。
   

   (11)2	→	(1100)2
   (3)10	→	(12)10

2. xを加える
   

   (12)10+(3)10

   =

   (15)10

問題へ

問題2

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

ア	0260
イ	2525
ウ	2775
エ	4405

解答：ア

＜解説＞

1. 55550を11進数とみなし10進数に変換する。
   

   	55550(11)
   =	5×114+5×113+5×112+5×111+0×110
   =	73205+6655+605+55+0
   =	80520(10)

2. 下4けたに対して0．5を乗じた結果がレコードのアドレスとなる。
   

   =	0520×0.5
   =	0260

キーの値が55550のとき，アドレスは0260となるので正解はアである。

問題へ

問題3

論理式 と等しいものはどれか。ここで，・論理積，＋は論理和，x は X の否定を表す。

ア	A ・ B ＋ A ・ C
イ	A ・ B ＋ A ・ C
ウ	(A ＋ B) ・ (A ＋ C)
エ	(A ＋ B) ・ (A ＋ C)

解答：ア

＜解説＞

ド･モルガンの法則により論理式を等価変換すると，次のようになる。

問題へ

問題4

文字列中で同じ文字が繰り返される場合，繰返し部分をその反復回数と文字の組に置き換えて文字列を短くする方法はどれか。

ア	EBCDIC 符号
イ	巡回符号
ウ	ハフマン符号
エ	ランレングス符号化

解答：エ

＜解説＞

ランレングス符号化は、データ列を可逆圧縮する符号化の1つ。連続する同一の値の列を，その連なり（run）の長さ（length）を示す数字に置き換える。例えば，「AAAAAAAAABBCDDDD」というデータ列を，Aが9回，Bが2回，Cが1回，Dが4回並んでいることから，「A9B2C1D4」というデータ列に圧縮する。

ア	×	EBCDICは、IBM社が策定した8ビットの文字コード体系である。。汎用大型コンピュータなどで利用されている。
イ	×	巡回符号は、符号理論における誤り訂正符号の一種である。
ウ	×	ハフマン符号化は、可逆圧縮の代表的なアルゴリズム。一定ビットごとに文字列を区切り、区切られた後の文字列を統計的に処理して、出現確率がより高いパターンに対してより短い符号を与える方式。
エ	○

問題へ

問題5

関数や手続を呼び出す際に，戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。

ア	2分探索木
イ	キュー
ウ	スタック
エ	双方向連結リスト

解答：ウ

＜解説＞

スタックは後入先出のデータ構造で，戻り番地やデータを一時的に保存する事に利用される。

問題へ