平成24年度秋季解答

問題1

8ビットの2進数 11010000 を右に2ビット算術シフトしたものを,00010100 から減じた値はどれか。ここで,負の数は2の補数表現によるものとする。

ア	00001000
イ	00011111
ウ	00100000
エ	11100000

解答：ウ

＜解説＞

1. 2進数11010000を右に2ビット算術シフトする。
   
2. 負の数→正の数へ変換する。
   
3. 00010100に加算する。
   

問題へ

問題2

与えられた正の整数 x₀,x₁(x₀>x₁)の最大公約数を,次の手順で求める。x₀=175,x₁=77の場合,手順(2)は何回実行するか。ここで,「A→B」は,AをBに代入することを表す。

ア	3
イ	4
ウ	6
エ	7

解答：イ

＜解説＞

実際に計算すると次のようになる。したがって、イが正解である。

問題へ

問題3

探索方法とその実行時間のオーダの適切な組合せはどれか。ここで,探索するデータの数をnとし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また,実行時間のオーダがn²であるとは,n個のデータを処理する時間がcn²(cは定数)で抑えられることをいう。

解答：ア

＜解説＞

探索方法と実行時間のオーダは次のようになる。

問題へ

問題4

英字の大文字(a～z)と数字(0～9)を同一のビット数で一意にコード化するには,少なくとも何ビットが必要か。

ア	5
イ	6
ウ	7
エ	8

解答：イ

＜解説＞

1. 英字の大文字(A～Z)は26文字である。
2. 数字(0～9)は10文字である。
3. 26+10=36→36個のコードが必要である。
4. 6ビットで、64文字を表示できる。

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

問題へ

問題5

四つのデータA,B,C,Dがこの順に入っているキューと空のスタックがある。手続き pop_enq, deq_push を使ってキューの中のデータをD,C,B,Aの順に並び替えるとき,deq_push の実行回数は最小で何回か。ここで,pop_enq はスタックから取り出ししたデータをキューに入れる操作であり,deq_push はキューから取り出したデータをスタックに入れる操作である。

ア	2
イ	3
ウ	4
エ	5

解答：イ

＜解説＞

次の①～⑥の順に実行すれば、deq_pushは全部で3回実行する。

問題へ