平成23年度秋季解答

問題1

Xは，0以上65,536未満の整数である。xを16ビットの2進数で表現して上位8ビットと下位8ビットを入れ替える。得られたビット列を2進数とみなしたとき，その値をxを用いた式で表したものはどれか。ここで，a div bはaをbで割った商の整数部分を，a mod bはaをbで割った余りを表す。また，式の中の数値は10進法で表している。

ア	(x div 256)＋(x mod 256)
イ	(x div 256)＋(x mod 256)×256
ウ	(x div 256)×256＋(x mod 256)
エ	(x div 256)×256＋(x mod 256)×256

解答：イ

＜解説＞

シフト演算では、次のように左シフト，右シフトを行う。

• X を n ビット右シフト→X　を 2ⁿで割った商
• X を n ビット左シフト→X　を 2ⁿ倍した積

例として16ビットの2進数 00000000 11111111の上位ビットと下位8ビットを入れ替える。

1. Xの上位8ビットを右シフトするには、X を 256(2⁸)で割る。
2. Xの下位8ビットは、X を 256(2⁸)で割った余りである。
3. 2の結果を8ビット左シフトするには、256(2⁸)倍する。
   

1～3を整理すると次のようになる。

よってイが正解である。

問題へ

問題2

式A＋B×Cの逆ポーランド表記法による表現として，適切なものはどれか。

ア	＋×CBA
イ	×＋ABC
ウ	ABC×＋
エ	CBA＋×

解答：ウ

＜解説＞

逆ポーランド表記法とは、数式やプログラムを記述する方法。演算子を被演算子の後に記述することから、後置記法とも言う。

逆ポーランド記法では、通常の計算順序と同様に除算・乗算を加算・減算の演算子より優先する。

A＋B×Cは、逆ポーランド表記では次のようになる。

1. A＋B×C
2. A＋BC×
3. ABC×＋

よってウが正解である。

問題へ

問題3

符号長7ビット，情報ビット数4ビットのハミング符号による誤り訂正の方法を，次のとおりとする。
　 受信した7ビットの符号語x1x2x3x4x5x6x7(xk=0又は1)に対して

を計算し，c0，c1，c2の中に少なくとも一つは0でないものがある場合には，
　　i = c0＋c1×2＋c2×4
を求めて，左からi ビット目を反転することによって誤りを訂正する。

受信した符号語が1000101であった場合，誤り訂正後の符号語はどれか。

ア	1000001
イ	1000101
ウ	1001101
エ	1010101

解答：エ

＜解説＞

1. c₀，c₁，c₂を算出する。
   
2. 1で算出したc₀，c₁，c₂を、i = c₀＋c₁×2＋c₂×4に代入する。
   i = 1 ＋1×2＋0×4=3
3. 2より3ビット目が誤っていることが分かる。3ビット目を反転する。
   1000101→1010101

したがって、エが正解である。

問題へ

問題4

サンプリング周波数40kHz、量子化ビット数16ビットでA/D変換したモノラル音声の1秒間のデータ量は、何kバイトとなるか。ここで、1kバイトは1,000バイトとする。

ア	20
イ	40
ウ	80
エ	640

解答：ウ

＜解説＞

1秒間のデータ量はサンプリング周波数×量子化ビット数で求められる。

• サンプリング周波数：40kHz＝40,000回/秒のサンプリングを行なう
• 量子化ビット：16ビット＝2バイト

よって、40,000回/秒×2バイト＝80,000バイト/秒=(ウ)80kバイト/秒となる。

問題へ

問題5

自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を

h(x)=x mod n

とすると、キーaとbが衝突する条件はどれか。ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。

ア	a+bがnの倍数
イ	a-bがnの倍数
ウ	nがa+bの倍数
エ	nがa-bの倍数

解答：イ

＜解説＞

下図より、キーaとbが衝突する条件は(イ)a-bがnの倍数である。

問題へ