平成25年度 春期 基本情報技術者試験 問1−20 解答編




このページは

基本情報

(基本情報技術者試験)

解答と解説のページです。

問題だけで勉強したい方は目次へ戻ってください




問1 16ビットの2進数nを16進数の各桁に分けて、下位の桁から順にスタックに格納するために、次の手順を4回繰り返す。a,bに入る適切な語句の組合せはどれか。ここで、XXXX16は16進数XXXXを表す。

【手順】
(1) 【 a 】をxに代入する。
(2) xをスタックにプッシュする。
(3) nを【 b 】論理シフトする。
画像(問1ans)を表示できません
解答
解説 16進数1桁は2進数4桁に相当します。よって、[ a ]で下位4ビットを取り出すために、000F16でマスク処理をします。値を入れ終わったあとは、次の4ビットが最下位4ビットになるようにシフトをするので、右に4ビットシフトします。

問2 1秒間に一定間隔で16個のパルスを送ることができる通信路を使って、0〜9、A〜Fの16種類の文字を送るとき、1秒間に最大何文字を送ることができるか。ここで1ビットは1個のパルスで表し、圧縮は行わないものとする。
解答
解説 1秒間に16個のパルスを送信できるということは、216の情報を送信できるということになります。一方で16種類の文字を表現するためには、16=24なので4ビット必要となります。よって16/4=4文字を送信できるといえます。

問3 アナログ音声をPCM符号化したとき、1秒当たりのデータ量は64,000ビットであった。量子化ビット数を8ビットとするとき、サンプリング間隔は何マイクロ秒か。
0.125
125
512
解答
解説 PCM(Pulse Code Modulation:パルス符号変調)とは音声などのアナログ信号をディジタル信号に変換する手法の一つです。
まず、アナログデータ(時間も振幅も連続)をディジタルデータに変換するためには、標本化→量子化→符号化という作業を行います。各作業を簡単に以下にまとめます。

標本化:時間を離散化する。(一般的には最大周波数の2倍で行います)
量子化:振幅を離散化する。
符号化:量子化したデータを特定の符号に対応付けする。

符号化と量子化は、多くのサンプリングポイントを取ることで、よりオリジナルに近いデータを作り出すことができます(データ量は多くなります)

それでは、計算していきます。
64000/8=8000回サンプリングポイントがあります。、
つまり、1/8000=0.000125=125マイクロ秒となります。

問4 通信回線の伝送誤りに対処するパリティチェック方式(垂直パリティ)の記述として、適切なものはどれか。
1ビットの誤りを検出できる。
1ビットの誤りを訂正でき、2ビットの誤りを検出できる。
奇数パリティならば1ビットの誤りを検出できるが、偶数パリティでは1ビットの誤りも検出できない。
奇数パリティならば奇数個のビット誤りを、偶数パリティならば偶数個のビット誤りを検出できる。
解答
解説 垂直パリティは、垂直方向へパリティを付加したもので、1ビットの誤りを検出できます。

代表的な誤り制御方式を下にまとめます。
奇数パリティ:1(あるいは0)の個数が奇数個になるように、1ビットを付加するもの
偶数パリティ:1(あるいは0)の個数が偶数個になるように、1ビットを付加するもの
水平パリティ:転送を2次元の配列とみなしたときに、水平方向へのパリティを付加するもの。
垂直パリティ:転送を2次元の配列とみなしたときに、垂直方向へのパリティを付加するもの。
チェックサム:送信データを数値に対応させ、その合計を計算し付加するもの。 ハミング符号:データに冗長ビットを付加して、2ビットの誤り検出と1ビットの誤り訂正機能を持たせたもの。
巡回冗長検査(CRC):送信列から生成多項式とよばれる式をつくり、受信側で計算式の余りが0かどうかを調べる。

問5 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構築するためには、削除された要素の位置にどの要素を移動すればよいか。

画像(問5)を表示できません
10
13
14
解答
解説 2分木は「左の子の値<親の値<右の子の値」となっており、これに適合するかを各選択肢を見ていきます。調べていきます。

選択肢ア:9を移動した場合は、10<9に違反するので不整合です。
選択肢イ:10を移動した場合は、さらに移動が必要になり、問題文の『別の要素を移動するだけで(1回の移動だけ)』に反するので間違いです。
選択肢ウ:13を移動した場合は、10<13<14となり正しくなります。
選択肢エ:14を移動した場合は、さらに移動が必要になり、問題文の『別の要素を移動するだけで(1回の移動だけ)』に反するので間違いです。

問6 図は、逆ポーランド表記法で書かれた式abcd+++をスタックで処理するときのスタックの変化の一部を表している。この場合、スタックの深さは最大で4となる。最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。

画像(問6)を表示できません
ab+c+d+
ab+cd++
abc++d+
abc+d++
解答
解説 それぞれの選択肢の演算をスタックを利用して求めると以下のようになります。

画像(問6kai)を表示できません

よって、選択肢アが深さ2で計算ができます。

問7 10進法で5桁の数a12345を、ハッシュ法を用いて配列に格納したい。ハッシュ関数をmod(a12345,13)とし、求めたハッシュ値に対応する位置の配列要素に格納する場合、54321は配列のどの位置に入るか。ここで、mod(x,13)はxを13で割った余りとする。

画像(問7)を表示できません
411
解答
解説 実際に値を代入して計算します。mod(5+4+3+2+1,13)=mod(15,13)=2となります。

なお、以下のように同じ値になることをシノニムが起こるといいます。シノニムは、二つの値の差がnの倍数であれば衝突が起こることがわかります。

ハッシュを表示できません

問8 xとyを自然数とするとき、流れ図で表される手続を実行した結果として、適切なものはどれか。

画像(問8)を表示できません
画像(問8ans)を表示できません
解答
解説 実際にxとyに値をいれて計算してみます。

x=10、y=3とします。
q←0
r←10
10<3はNo
r←10−3
q←0+1

7<3はNo
r←7−3
q←1+1

4<3はNo
r←4−3
q←2+1

1<3はYes
終了

処理を確認すると、rにはxからyを引けるだけ引いた余りが入っています。qには引いた回数が入っています。
そのため、rはx÷yの余り、qには引いた回数(商)が入るといえます。

問9 50MIPSのプロセッサの平均命令実行時間は幾らか。
20ナノ秒
50ナノ秒
2マイクロ秒
5マイクロ秒
解答
解説 MIPS(Million Instructions Per Second)は1秒間に何百万個の命令が実行できるかという指標です。そして、その実行時間は1/クロック数となります。

よって、1/(50×106) = 1/50×1/106
つまり、0.2×10-6 = 20×10-9つまり、20ナノ秒となります。

問10 主記憶のデータを図のように参照するアドレス指定方式はどれか。

画像(問10)を表示できません
関節アドレス指定
指標アドレス指定
相対アドレス指定
直接アドレス指定
解答
解説 4つの方式を以下にまとめます。

直接アドレス:値をアドレスと見なして、そのアドレスの値を有効値とする方式です。
間接アドレス:値をアドレスと見なして、そのアドレスの値もアドレスと見なし、そのアドレス値を有効値とする方式です。
指標アドレス:値と指標値を足した値をアドレスと見なして、その値を有効値とする方式です。
相対アドレス:値とプログラムカウンタの値を足しして、その値をアドレスと見なして、有効値とする方式
即値オペランド:値を有効値とする方式です。

アドレスを表示できません


上記の例を考えると、直接アドレスは、101のアドレスの内容で102。間接アドレスは、101のアドレスの内容(102)の内容で、103。指標付きアドレスは、101+5=106の内容で500。即値オペランドは値そのものなので、101となります。間接アドレスは、2重、3重とすることができます。また、指標付きアドレスは、相対アドレスや再配置可能プログラムを考える上で重要になります。


問11 MPUの割込みには外部割込みと内部割込みがある。外部割込みの例として、適切なものはどれか。
0で除算をしたときに発生する割込み
ウォッチドッグタイマのタイムアウトを起こしたときに発生する割込み
未定義命令を実行しようとしたときに発生する割込み
メモリやデバイスが存在しない領域にアクセスしたときに発生する割込み
解答
解説 まず、割り込には大きく分けて内部割りこみと外部割り込みがあります。内部割り込はゼロによる除算に代表されるソフトウェア的な原因。外部割り込みは、入出力の完了や電圧異常などに代表されるハードウェア的な原因です。

また、割り込みを受け付けるとCPUはレジスタのデータを主記憶等に退避させ、割り込みの処理を実行します。さらに、複数の割り込みに優先順位をつけ、順位の低いものが、順位の高いものに割り込みを行わないようにマスク処理をする場合もあります。

ウォッチドッグタイマとは、制御工学における規則正しいパルスが送られなくなると、正常な状態に戻すためのリセットを行うタイマのことです。主に組込みシステムや利用されます。なお、ウォッチドッグとは番犬の意味で、タイマをクリアする動作をウォッチドッグ操作と呼びます。

選択肢ア、ウ、エは内部割込みに分類されます。

問12 図に示す構成で、表に示すようにキャッシュメモリと主記憶のアクセス時間だけが異なり、他の条件は同じ2種類のCPU XとYがある。あるプログラムをCPU XとYでそれぞれ実行したところ、両者の処理時間が等しかった。このときキャッシュメモリのヒット率は幾らか。ここで、CPUの処理以外の影響はないものとする。

画像(問12)を表示できません
0.75
0.90
0.95
0.96
解答
解説 キャッシュメモリは、CPUのレジスタと主記憶とのアクセス速度の差を埋めるために用いられるものです。

ここでヒット率をaとすると
CPUXのアクセス時間=40×a+400(1−a)
CPUYのアクセス時間=20×a+580(1−a)

ここで、2つのCPUのアクセス時間は等しいので
40×a+400(1−a)=20×a+580(1−a)
20a=180(1−a)
20a=180−180a
200a=180
a=180/200=0.9

よって、ヒット率は0.9であるといえます。

問13 Bluetoothの説明として、適切なものはどれか。
1台のホストは最大127台のデバイスに接続することができる。
規格では、1,000m以上離れた場所でも通信が可能であると定められている。
通信方向に指向性があるので、接続対象の機器同士を向かい合わせて通信を行う。
免許不要の2.4GHz帯の電波を利用して通信する。
解答
解説 Bluetoothとは、2.4GHz帯という免許のいらない周波数帯を利用して近距離での無線通信を行う規格です。通信は双方向性で、通信距離は最大100mで最大接続数は7台となっています。

問14 フォールトトレラントシステムの説明として、適切なものはどれか。
システムが部分的に故障しても、システム全体として必要な機能を維持するシステム
地域的な災害などの発生に備えて、遠隔地に予備を用意しておくシステム
複数のプロセッサがネットワークを介して接続され、資源を共有するシステム
複数のプロセッサで一つのトランザクションを並行して処理し、結果を照合するシステム
解答
解説 重要な高信頼システム設計法についてまとめておきます。

フォールトトレラント:障害時に全体が停止するということなく、動作し続けるようなシステムを設計すること。
フォールトアボイダンス:システムの構成要素の信頼性を高め, 元から故障が極力発生しないように設計すること。
フォールトマスキング:障害が発生したときに、その部分を他の機器から隠蔽したり、自律回復するように設計すること。
フェールセーフ:障害が発生した場合、常に安全側に制御・停止すること。
フェールソフト:障害が発生した場合、故障した個所を切り離すなどして、稼動を続けること。
フェールオーバ:障害が発生した場合、ユーザに切り替えを意識させないように、別のシステムに引き継がせること。
フールプルーフ:ユーザが誤った操作をした場合、危険に晒されることがないように、事前に安全策を行うこと。

他の選択肢は以下のようになります。
選択肢イ:遠隔地バックアップ
選択肢ウ:疎結合マルチプロセッサ
選択肢エ:デュアルシステム

問15 MFBFが45時間でMTTRが5時間の装置がある。この装置を二つ直列に接続したシステムの稼働率は幾らか。
0.81
0.90
0.95
0.99
解答
解説 まず、2つの用語と稼働率についてまとめます。

平均故障間隔(MTBF:Mean Time Between Failure)は故障と故障の間の動作していた時間の平均
平均故障時間(MTTR:Mean Time To Repair)は実際に故障していた時間の平均
稼働率(=MTBF/(MTBF+MTTR)はシステムが稼働している割合

まず、単一の装置の稼働率をもとめると45/50=0.9となります。
つぎに、この装置が直列に接続されている全体のシステムの稼働率を求めると0.9×0.9=0.81となります。

問16 コンピュータシステムによって単位時間当たりに処理される仕事の量を表す用語はどれか。
スループット
ターンアラウンドタイム
タイムスライス
レスポンスタイム
解答
解説 それぞれの用語を以下にまとめます。

スループット:単位時間当たりの仕事の量
ターンアラウンドタイム:処理の依頼を行ってから完了するまでの時間
タイムスライス:タイムシェアリングシステムやラウンドロビン方式になどで細分化したCPUの使用時間
レスポンスタイム:処理の要求を出してから、応答が帰ってくるまでの時間

なお、一般的にレスポンスタイムはターンアラウンドタイムに含まれます。

問17 アプリケーションの変更をしていないにもかかわらず、サーバのデータベース応答性能が悪化してきたので、表のような想定原因と、特定するための調査項目を検討した。調査項目cとして、適切なものはどれか。

画像(問17)を表示できません
遅い処理の特定
外的要因の変化の確認
キャッシュメモリのヒット率
データの格納状況の確認
解答
解説 フラグメンテーションとは、ファイルが断片化されHDDの様々な部分に格納されることで、ファイルの読み出しに余計に時間がかかる現象です。そのため、細ぎれになった未使用領域がないかを調べるため、データの格納状況を確認するのが、調査項目として適切です。

問18 三つのタスクの優先度と、各タスクを単独で実行した場合のCPUと入出力装置(I/O)の動作順序と処理時間は、表のとおりである。三つのタスクが同時に実行可能な状態になってから、全てのタスクの実行が終了するまでの、CPUの遊休時間は何ミリ秒か。ここで、I/Oは競合せず、OSのオーバヘッドは考慮しないものとする。また、表の()内の数字は処理時間を示す。

画像(問18)を表示できません
解答
解説 以下のように図で表現するとわかりやすいです。

画像(問18kai)を表示できません

図より、2+1で3ミリ秒の遊休時間が発生することがわかります。

問19 主記憶の管理方式とマルチプログラミングでのプログラムの多重度の組合せで、スラッシングが発生しやすいのはどれか。
画像(問19ans)を表示できません
解答
解説 スラッシングとは、仮想記憶方式において、実メモリの容量が少なくデータの入れ替え(スワップインとスワップアウト)ばかりに時間がとられ、処理が進まないことをいいます。よって、仮想記憶方式において、データの入れ替えが多くなる多重度が高い場合に、スラッシングが発生しやすくなります。

問20 仮想記憶管理におけるページ置換えの方式のうち、LRU制御方式はどれか。
各ページに参照フラグと変更フラグを付与して管理し、参照なしかつ変更なしのページを優先して置き換える。
主記憶にある全てのページを同一の確率でランダムに選択し、置き換える。
最も長い時間参照されていないページを置き換える。
最も長い間主記憶にあったページを置き換える。
解答
解説 ページ(ブロック)の置換えには幾つかのアルゴリズムがあります。下にまとめます。

NRU(Not Recently Used):最近使われていないものから順に置き換える
LRU(Least Recently Used):最後に参照されてから最も時間が経過したものから順に置き換える
LFU(Least Frequently Used):最も使用頻度の低いものから順に置き換える
FIFO(First In First Out):最初に読んだものから順に置き換える
LIFO(Last in First Out)は、最後に入れたものを最初に使うというもので、再帰プログラムやスタックとかかわりが深いものです。ページの置換えには使われません。

他の選択肢は以下のようになります。
選択肢ア:LFU方式
選択肢イ:ランダム方式
選択肢エ:FIFO方式