[問01-10]H28秋期基本情報技術者試験解説

平成28年度秋季FP
問01-問10

H28年度秋季基本情報技術者試験[01-10]

H28年度秋季基本情報技術者試験[問01-10]です。
過去問題は情報処理推進機構(IPA)公式ホームページよりダウンロードすることができます。

問01
8ビットのビット列の下位4ビットが変化しない操作はどれか。
[ア]16進表記0Fのビット列との排他的論理和をとる。
[イ]16進表記0Fのビット列との否定論理積をとる。
[ウ]16進表記0Fのビット列との論理積をとる。
[エ]16進表記0Fのビット列との論理和をとる。
論理演算に関する問題です。
16進数「0F」は、2進数「00001111」です。

ここでは例として「00101110」という8ビット列を用います。
「00001111」との演算で、この下4桁「1110」が変化しないものを選びます。

排他的論理和
「00001111」 XOR 「00101110」 = 「00100001」
否定論理積
「00001111」 NAND 「00101110」 = 「11110001」
論理積
「00001111」 AND 「00101110」 = 「00001110
論理和
「00001111」 OR 「00101110」 = 「00101111」
以上より、「論理積」が正解です。


問02
ある工場では、同じ製品を独立した二つのラインA、B で製造している。ラインAでは製品全体の60%を製造し、ラインBでは40%を製造している。ラインAで製造された製品の2%が不良品であり、ラインBで製造された製品の1%が不良品であることが分かっている。いま、この工場で製造された製品の一つを無作為に抽出して調べたところ、それは不良品であった。その製品がラインAで製造された確率は何%か。
[ア]40
[イ]50
[ウ]60
[エ]75

両ラインで同じ製品を製造しているため、できたものを見ても、それがどちらで製造されたか特定することはできません。そのため、AとBそれぞれの不良品率から予想します。

[ラインA]不良品率 1.2%
ラインAは工場全体の60%を製造、うち2%不良品です。
ここから不良品率が、「0.6 × 0.02 = 0.012」であるとわかります。

[ラインB]不良品率 0.4%
ラインBは工場全体の40%を製造、うち1%が不良品です。
ここから不良品率が、「0.4 × 0.01 = 0.004」であるとわかります。

以上の不良品率を比べて見ると、
0.012 : 0.004 = 3 : 1

つまり、不良品がラインAで製造された確率は、「3 / 4 = 0.75(75%)」となります。

POINT

不良品率を求める場合、まず適当に数字を入れてみることが大切です。
この問題の場合、例えば製造数を「1000個」と過程すれば、個々のラインの不良品率を求めなくても、正解にたどり着くことができます。

【製造数1000個と過程した場合】
[ラインA] 1000個 × 0.6(Aの製造割合) = 600個(Aの製造分)
600個 × 0.02(Aの不良品割合) = 12個(Aの不良品)

[ラインB] 1000個 × 0.4(Bの製造割合) = 400個(Bの製造分)
400個 × 0.01(Bの不良品割合) = 4個(Bの不良品)

以上から、検出される16個の不良品のうち、12個がラインAのものであるため、その確率は「12 / 16 = 0.75(75%)」と求めることができます。こちらのほうが確実かも知れません。


問03
300円の商品を販売する自動販売機の状態遷移図はどれか。ここで、入力と出力の関係を“入力/出力”で表し、入力の“a”は“100円硬貨”を、“b” は“100円硬貨以外”を示し、S0〜S2 は状態を表す。入力が“b”の場合はすぐにその硬貨を返却する。また、終了状態に遷移する際、出力の“1”は商品の販売を、“0”は何もしないことを示す。
[ア]ア
[イ]イ
[ウ]ウ
[エ]エ

状態遷移図は頻繁に出題される問題のひとつです。整理して考えましょう。
まず図中の「a/0」「b/0」は、(入力)/(出力)を表しています。
aとbが入力、0と1が出力です。それぞれの意味を確認します。

入力 a 100円硬貨
b 100円硬貨以外
出力 0 何もしない
1 商品の販売

つまり、「a/1」は「100円硬貨を入れて(入力) / 商品を販売(出力)」。
「b/0」は「100円以外の硬貨を入れて(入力) / 何もしない(出力)」。
となるわけです。

問題には、「300円の商品を販売する」とあります。
すなわち、「a」(100円投入)が3回(300円)呼び出されて、商品が販売(1)されるわけです。
投入金額が300円未満のときは、追加の硬貨を待つわけですから、何もしない(0)ことになります。

以上より、300円で商品を販売する状態遷移図は、初期状態(S0)から、「a/0」(100円投入/何もしない)が2回続いた(200円投入)あと、「a/1」(100円投入/商品販売)に遷移する(300円で商品販売し、初期状態に戻る)ものとわかります。この要件を満たすのは、選択肢アです。

100円未満の硬貨が投入された場合は、何もしません。おそらく払い戻されるのでしょう。この状態遷移図は、まさしくガチャポン(ガチャガチャ)ですね。


問04
32ビットで表現できるビットパターンの個数は、24ビットで表現できる個数の何倍か。
[ア]8
[イ]16
[ウ]128
[エ]256
H26年度秋季試験(3)でも同じ問題が出題されています。

1ビットで表現できるのは、「1」か「0」の2通りでした。2ビットは4(22)通り、3ビットは8(23)通り、4ビットは16(24)通り。
つまり、nビットで表現できるビットパターン数は、 2n 個になります。

32ビットのパターン数は、232、24ビットのパターン数は224
倍数計算では、この乗数部分に注目します。

232÷224=232-24=28=256。

よって「256倍」が正解です。


問05
標本化、符号化、量子化の三つの工程で、アナログをディジタルに変換する場合の順番として、適切なものはどれか。
[ア]標本化、量子化、符号化
[イ]符号化、量子化、標本化
[ウ]量子化、標本化、符号化
[エ]量子化、符号化、標本化
A/D変換(アナログ→デジタル)に関する問題です。
アナログ信号をデジタル変換するためには、

  1. まずその信号(振幅、周波数など)の強度を連続的に測定し、(標本化)
  2. それをコンピュータが理解できる形(整数などの離散値)にし、(量子化)
  3. 2進数にして、あとで元の(類似の)信号に戻せるよう変換します。(符号化)

自然界の音は、空気の振動です。
これをそのまま機械に記録することはできないので、コンピュータの得意な「数字」に置き換えます。空気の振動はやがては消えてしまいますが、数字はデータとして記録・送信することができます。

A/D(アナログ→デジタル)に用いられる機器には、マイクがあります。
D/A(デジタル→アナログ)に用いられる機器には、スピーカーがあります。

CHECK POINT
標本化(Sampling)
連続信号を、一定の間隔をおいて測定することにより、離散信号として収集すること。この間隔(サンプリング周波数)が短いほど、元の連続量により近いデジタルデータが得られる。
標本化
Sampled-Signal(public domain) -wikipedia
量子化(quantization)
標本化で得られたアナログデータを、離散的なデジタルデータとして近似的に表すこと。この値に用いるビット数(量子化ビット数)を増やすことで、元の連続量により近いデジタルデータが得られる。
量子化
Degital-Signal(public domain) -wikipedia
符号化(encode)
量子化で得られたデータを変換して数値化する。

問06
2分探索木になっている2分木はどれか。
[ア]ア
[イ]イ
[ウ]ウ
[エ]エ

2分探索木の構造に関する問題です。

基礎的な制約 「左の子孫の値≦親の値≦右の子孫の値」 が解答のポイント。

[ア] 「15」の右の子孫の値が親より小さいため間違い。
[イ] 条件を満たすため、2分探索木である。
[ウ] 「16」の右の子孫の値が親より小さいため間違い。
[エ] 「18」の右の子孫および「19」の右の子孫の値が親より小さいため間違い。
2分探索木Binary_search_tree(public domain)-wikipedia

問07
整数x,y(x>y≧0)に対して、次のように定義された関数 F(x,y)がある。F(231,15)の値は幾らか。ここで、x mod yはxをyで割った余りである。
H28年度FP07問
[ア]2
[イ]3
[ウ]5
[エ]7
初見で誰もが困惑する問題かと思います。
「再帰関数」に関する問題は、基本情報技術者試験で頻繁に出題されます。

「再帰的」とある通り、xが確定するまで上記の式に代入を繰り返します。
右辺にある(y=0のとき)(y>0のとき)という条件に注目しましょう。

 F(231, 15)
=F(15, 231 mod 15)
=F(15, 6)

=F(6, 15 mod 6)
=F(6, 3)

=F(3, 6 mod 3)
=F(3,0)
=3
y>0
F(y, x mod y)
x = 15, y= 6

y>0 -> F(y, x mod y)
x = 6, y = 3

y>0 -> F(y, x mod y)
x = 3, y = 0
y=0 -> x


問08
Web環境での動的処理を実現するプログラムであって、Webサーバ上だけで動作するものはどれか。
[ア]JavaScript
[イ]Javaアプレット
[ウ]Javaサーブレット
[エ]VBScript
まず始めに「静的ページ」と「動的ページ」を簡単に確認しましょう。
例えば、企業のホームページやブログ記事など、あらかじめ作成したページをそのまま表示させるのは「静的ページ」です。

対して「動的ページ」は、アクション(ボタンクリックなど)や利用者情報、接続時間などによって、表示するコンテンツを動的に生成し表示させます。

例えば、Amazonなどのショッピングサイトを利用する際、画面の端にはアカウント名が表示されているはずです。私のために開発者があらかじめ記述してくれたのでしょうか?もちろん違います。そのページは、あなたのユーザ情報およびその購買履歴など様々な情報から動的に生成されたWebページなのです。

問題は、この「動的処理」がどこで行われるかという点です。
これを「サーバ側」で動作させる手法には、サーブレットやJSPなどがあります。

対して「クライアント側(ブラウザ)」で動作させる手法には、Javaアプレットなどがあります。
ブラウザで動的処理を行う、というのはイメージが難しいかもしれませんが、例えば「Radish Network Speed Testing」など、回線速度測定ページなどではJavaアプレットが用いられ、実行の承諾が表示されます。
radish Network speed testing Radish Network Speed Testing

CHECK POINT
Javaアプレット
Java言語で記述されたプログラム。サーバからダウンロードされ、”Webブラウザ(クライアント側)”上に組み込まれて実行されるプログラム。
Javaサーブレット
Java言語で記述されたプログラム。”Webサーバ”上で実行されるプログラムのこと。

問09
主記憶のデータを図のように参照するアドレス指定方式はどれか。
H28f09 [ア]間接アドレス指定
[イ]指標アドレス指定
[ウ]相対アドレス指定
[エ]直接アドレス指定
H27春季(9)、H25年春季(10)、H23年秋季(9)で同文出題されている頻出問題です。
いずれの年度でも「間接アドレス指定」が解答になっています。

間接アドレス指定方式
間接アドレス指定方式のアドレス部では、「処理対象データが格納されている記憶場所のアドレスが格納されている記憶場所のアドレス」(H28秋季応用技術者09)が指定されます。

問題の図は、対象データを間接的に指定しているので、用語を知らなくても直感で正解できる問題でしょう。

CHECK POINT
直接アドレス指定
命令のアドレス部に記載された値をそのままメモリ上の位置とするもの。
指標アドレス指定(indexed addressing)
命令のアドレス部の値にインデックスレジスタ(指標レジスタ)の値を加えたものをデータの位置とするもの。
相対アドレス方式(relative addressing)
命令のアドレス部の値にプログラムカウンタの値を超えたものをデータの位置とするもの。

問10
CPUにおける投機実行の説明はどれか。
[ア]依存関係にない複数の命令を、プログラム中での出現順序に関係なく実行する。
[イ]パイプラインの空き時間を利用して二つのスレッドを実行し、あたかも二つのプロセッサであるかのように見せる。
[ウ]二つ以上のCPUコアによって複数のスレッドを同時実行する。
[エ]直接アドレス指定分岐命令の分岐先が決まる前に、予測した分岐先の命令の実行を開始する。

「投機」という言葉に馴染みがなければ、”speculative”の別の意味である「思索的な、推論的な、不確かな」の意味で考えると理解しやすいでしょう。

「投機実行」は、CPU処理高速化のため「予測した分岐先命令をあらかじめ実行しておく」手法です。

CPUは、複数の命令を並行実行するなどして処理の高速化を図ります。しかし、プログラムの途中に「条件分岐」があると、当然その「条件」を得るまでは、[処理A]か[処理B]どちらを実行するべきか判断できません。せっかく並行実行したのに、分岐点で処理が足止めされてしまうわけです。

投機(speculative)に「推論的な、不確かな」という意味があるとおり、投機実行では「条件」が確立していない段階で、見切り発車的に予測分岐先の処理を実行します。これにより、 並行処理を分岐点より先に進めることができる のです。もし予測が当たっていたら、その処理が適用され、外れた場合は、見切り発車した分の処理を破棄して正しい分岐先の命令を実行します。

例えば、「ごはん派 or パン派」という条件分岐があります。
過去の実行履歴から85%の確率で「ごはん派」が選ばれることがわかっています。
投機実行では、分岐点に到達する前に、あらかじめ「ごはん派」の先の処理を進めます。やはり「ごはん派」に分岐しました。予測が的中したことで、命令処理全体の実行時間を短縮することができました。

仮に誤って実行確率の小さい「パン派」を実行してしまうと、結局処理が巻き戻ってしまいます。そのため投機実行では、過去の実行履歴など、分岐予測の精度が重要なポイントになってきます。

CHECK POINT
投機実行
プログラムが途中で条件分岐しているときに、分岐した先の処理をあらかじめ実行しておくこと。
(出典)IT用語辞典 e-Words

[H28年度秋期基本情報技術者試験]

午前
01-10 11-20 21-30 31-40
41-50 51-60 61-70 71-80

2016/11/17 問2、問3の解説を追加