基本情報技術者試験

[修了認定#01-1]計算問題・思考問題解説(令和元年7月免除)

基本情報技術者試験

問1

数値を2進数で表すレジスタがある。このレジスタに格納されている正の整数xを10倍にする操作はどれか。ここで、桁あふれは起こらないものとする。

【ビットシフト演算・論理シフト演算】

$$ nビット左シフト = 2 ^ n 倍 $$

$$ nビット右シフト = 1/2 ^n 倍 $$

【ア】の選択肢


[ⅰ]まず2ビット左シフトを行う。2ビット左シフトは $ 2^2 $であるから、下記の式が完成する。

$ [ⅰ] x \times 2^2 = x \times 4 = 4x  $

[ⅰ]の式に$ x $ を加算します。

$ [ⅱ] 4x + x = 5x $

最後に[ⅱ]の式を更に1ビット左シフトしましょう。

$[ⅲ] 5x \times 2^1 = 5x \times 2 = 10x $

よって、答えは【ア】となります。

問2

負の整数を表現する代表的な方法として、次の3種類がある。
a:1の補数による表現
b:2の補数による表現
c:絶対値に符号を付けた表現(左端ビットが0:正、1:負)
4ビットのパターン 1101を a ~ c の方法で表現したものと解釈したとき、値が小さい順になるように3つの方法を並べたものはどれか。

【1の補数・2の補数】

1の補数:全ビットを反転する。

2の補数:1の補数に1を加算する。

今回問題文にあるビットパターンをそれぞれ a , b , c で表現しましょう。

1の補数:1101 を全反転 = 0010

絶対値は2で有るから、aのパターンは$ -2 $であると分かる。

2の補数:0010 に1加算 = 0011

絶対値は3であるから、bのパターンは$ -3 $であると分かる。

絶対値表現は左端以外のビットを絶対値表記しましょう。

左端以外は5で、左端ビットは「1=負」ですので $ -5 $であると分かる。

後はこれらを小さい順番に並べれば良いので、

$ -5 < -3 < -2 = c < b < a $となる。よって答えは【エ】。

問3

論理式 $ \overline{A} ・ \overline{B} ・ C + A ・\overline{B}・C + \overline{A}・B・C + A・B・C $と恒等的に等しいものはどれか。ここで、・は論理積、+は論理和、$ \overline{A} $は$A$の否定を表す。

ベン図を書くやり方もありますが、ここはまとめちゃいましょう。

まず論理和毎に分解した時、全てに$ C $が有ることが分かります。これで全てをくくります。

$ C ・( \overline{A}・\overline{B} + A・\overline{B} + \overline{A}・B + A ・ B ) $

そしてもう一回くくりましょう。$\overline{B}$と$B$でそれぞれくくれそうです。

$ C ・\{ \overline{B} ・(\overline{A} + A) + B・(\overline{A} + A)\}$

補集合Aと集合Aは約分的なことが出来そうですね。(正確には $ \overline{A} + A = 1 $ )

$ C ・( \overline{B} + B ) $

補集合Bと集合Bも同様です。よって最後に残るのは $ C $ となり、答えは【エ】となります。

問6

(問題文省略)

1度問題文に関しての処理を行わずに、処理前の表示を考えましょう。

このようになれば正解です。

A→E→C→G→B→(終了) 

これの3番目と4番目に値「H」を入れたい訳です。

H以前・H以降も全て同じ順番で処理しなければならない時、nextをどうすれば良いのかを考える問題がこの問題です。

A[1]→E[5]→C[3]→H[8]→G[7]→B[2

それぞれの値の格納場所は上記の通りです。HからGへ移動するためには、格納場所「7」に移動しなければなりません。よって答えは【ウ】となるわけです。

問7

実際に値を入れてトレースすれば簡単に解ける問題です。

今回は例として $ m(a) = 36 n(b) = 24 $として考えましょう。


方法1:最初に mod した値が $ r $ に格納される。$ r = 12 $

$ r \neq 0 $ なのでループに突入します。

$ m = 24 n = 12 $ となります。

もう一度 mod しましょう。 割り切れるため、$ r = 0 $ となります。

$ r = 0 $ なのでループ終了。よって方法1では $ n $ に最大公約数が求まることが分かる。


方法2:ループの判定は最後に行われるため、無条件にループ内に突入する。

mod した値が $ r $ に格納される。$ r = 12 $

$ m = 24 n = 12 $となります。

$ r \neq 0 $ なのでループ始端に戻ります。

もう一度 mod しましょう。 割り切れるため、$ r = 0 $ となります。

$ m = 12 n = 0 $ となります。

$ r = 0 $ なのでループ終了。よって方法1では $ m $ に最大公約数が求まることが分かる。

よって答えは【ウ】であると分かる。

問8

関数 $ f(x,y) $が次の通り定義されているとき、$ f(775,527) $ の値は幾らか。(中略)
$f(x,y)$ : if y = 0 then return x else return ( y , x mod y)

まず命令句について考えましょう。

A then B はAであればBをせよ。という意味です。今回は条件を満たせば return x ( = xを返せ )と言う意味です。つまり出力値$x$が答えとなります。

この意味さえ分かれば、後は計算するだけです。

1回目: ( 527 , 775 mod 527 ) = ( 527 , 248 )

2回目: ( 248 , 527 mod 248 ) = ( 248 , 31 )

3回目: ( 31 , 248 mod 31 ) = ( 31 , 0 )

$ y = 0 $ になりましたので、$ x $ を return しましょう。よって答えは【イ】となります。

問9

平均命令実行時間が20ナノ秒のコンピュータがある。このコンピュータの性能は何MIPSか。

【時間を表す接頭語】

m(ミリ)→ μ(マイクロ)→ n(ナノ)→ p(ピコ)

MIPSは1秒間に何百万回処理を実行出来るかを示す指標です。

なので、1秒をナノまで変換しましょう。

$ 1s = 1,000ms = 1,000,000\mu = 1,000,000,000n $

1秒は1,000,000,000ナノ秒であると分かりました。後はこれを20で割ってあげれば1秒間に20ナノ秒の処理が何回できるかが分かりますね。

$ 1,000,000,000ns \div 20 = 50,000,000 $

よって答えは50MIPSとなり、【エ】が正答となります。

コメント

タイトルとURLをコピーしました