平成23年度秋季解答

問題1

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

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

解答：ウ

＜解説＞

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

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

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

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

よってウが正解である。

問題へ

問題2

符号長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

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

問題へ

問題3

自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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の倍数である。

問題へ

問題4

メモリインタリーブの説明として、適切なものはどれか。

ア	新しい情報をキャッシュメモリに取り出すとき、キャッシュ上では不要になった情報を主記憶に書き込む。
イ	主記憶のアクセス時間と磁気ディスクのアクセス時間とのギャップを補う。
ウ	主記憶の更新と同時にキャッシュメモリの更新を行う。
エ	主記憶を幾つかの区画に分割し、連続したメモリへのアクセスを高速化する。

解答：エ

＜解説＞

キャッシュメモリ (cache memory) は、CPUなど処理装置がデータや命令などの情報を取得/更新する際に主記憶装置やバスなどの遅延／低帯域を隠蔽化させ、処理装置と記憶装置の性能差を埋めるために用いる高速小容量メモリのことである。

ア	×	ライトバック方式のキャッシュメモリのリフレッシュ動作の説明である。
イ	×	ディスクキャッシュの説明である。
ウ	○	ライトスルー方式のキャッシュメモリの説明である。
エ	×	メモリインタリーブの説明である。

問題へ

問題5

ジョブの多重度が1で、到着順にジョブが実行されるシステムにおいて、表に示す状態のジョブA～Cを処理するとき、ジョブCが到着してから実行が終了するまでのターンアラウンドタイムは何秒か。ここで、OSのオーバヘッドは考慮しないものとする。

ア	11
イ	12
ウ	13
エ	14

解答：ア

＜解説＞

ターンアラウンドタイムは，ジョブの入力を開始してからCPUで処理された結果がすべて出力されるまでの時間である。

下図より、ジョブCが到着してから実行が終了するまでのターンアラウンドタイムは(ア)11秒である。

問題へ