平成２３年度 春期 基本情報技術者試験 問１−２０ 解答編



このページは

基本情報

（基本情報技術者試験）

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

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


問１ 画像（問1）を表示できません
ア Ａ・Ｂ＋Ａ・Ｃ
イ Ａ・Ｂ＋Ａ・Ｃ
ウ （Ａ＋Ｂ）・（Ａ＋Ｃ）
エ （Ａ＋Ｂ）・（Ａ＋Ｃ）
解答 ア
解説 この問題はド・モルガンの定理と呼ばれる以下のような変換法則を利用します。

（Ａ＋Ｂ） ＝ Ａ・Ｂ
（Ａ・Ｂ） ＝ Ａ＋Ｂ

つまり、以下のようにド・モルガンの定理を２回利用して変換します。

画像（問3kai）を表示できません

あとは、＋より・の方が優先順位が高いので（ ）が省略され、二重否定を除くとＡ・Ｂ＋Ａ・Ｃとなります。

どうしても分からない場合は、真理値表などから求めるのも一つの手です。
問２ 三つの実数Ｘ〜Ｚとそれぞれの近似値が次の場合、相対誤差の小さい順に並べたものはどれか。

画像（問2）を表示できません
ア Ｘ，Ｙ，Ｚ
イ Ｙ，Ｚ，Ｘ
ウ Ｚ，Ｘ，Ｙ
エ Ｚ，Ｙ，Ｘ
解答 エ
解説 誤差には、絶対誤差と相対誤差があります。
絶対誤差とは、真の値と測定値の差になりますが、これでは、『１と０』と『１００００と１０００１』が同じ誤差になってしまうので、相対的な誤差を求めることが多いです。絶対誤差と相対誤差の計算式を下にまとめます。

絶対誤差｜真の値−近似値｜ 相対誤差｜真の値−近似値｜／真の値

それでは、Ｘ，Ｙ，Ｚの相対誤差を計算していきます。
Ｘ：｜１．０２−１｜／１．０２＝０．０２／１．０２≒０．０２／１＝２％
Ｙ：｜１．９７−２｜／１．９７＝０．０３／１．９７≒０．０３／２＝１．５％
Ｚ：｜５．０５−５｜／５．０５＝０．０５／５．０５≒０．０５／５＝１％

よって、Ｚ，Ｙ，Ｘの順に相対誤差が小さいといえます。
問３ 表は、文字Ａ〜Ｅを符号化したときのビット表記と、それぞれの文字の出現確率を表したものである。１文字当たりの平均ビット数は幾らになるか。

画像（問3）を表示できません
ア １．６
イ １．８
ウ ２．５
エ ２．８
解答 イ
解説 １文字あたりの平均ビット長とは、１文字の出現確率とビット数を掛け合わせた平均（確率的な期待値）をいいます。

Ａ：１ビット×０．５＝０．５
Ｂ：２ビット×０．３＝０．６
Ｃ：３ビット×０．１＝０．３
Ｄ：４ビット×０．０５＝０．２
Ｅ：４ビット×０．０５＝０．２

よって、０．５＋０．６＋０．３＋０．２＋０．２＝１．８となります。
問４ 次の表は、文字列を検査するための状態遷移表である。検査では、初期状態をａとし、文字列の検査中の状態がｅになれば不合格とする。

解答群で示される文字列のうち、不合格となるものはどれか。ここで、文字列は左端から検査し、解答群中の△は空白を表す。

画像（問4）を表示できません
ア ＋００１０
イ −１
ウ １２．２
エ ９．△
解答 ウ
解説 選択肢をひとつずつ追っていきます。

選択肢ア：ａ → ｃ → ｂ → ｂ → ｂ → ｂ
選択肢イ：ａ → ｃ → ｂ
選択肢ウ：ａ → ｂ → ｂ → ｄ → ｅ
選択肢エ：ａ → ｂ → ｄ → ａ

よって、ｅで終わる選択肢ウが正解となります。
問５ 空の２分探索木に、８，１２，５，３，１０，７，６の順にデータを与えたときにできる２分探索木はどれか。
画像（問5ans）を表示できません
解答 エ
解説 ２分探索木とは、すべてのノードについて、左の子の値≦親の値≦右の子の値となっているものを指します。（大小関係が逆の場合もあります）

この関係を崩さないようにデータを追加していくと以下のようになります。

画像（問5kai）を表示できません

よって、正解は選択肢エとなります。
問６ 関数ｆ（ｘ，ｙ）が次のように定義されているとき、ｆ（７７５，５２７）の値は幾らか。ここで ｘ ｍｏｄ ｙはｘをｙで割った余りを返す。

ｆ（ｘ，ｙ）：ｉｆ ｙ＝０ ｔｈｅｎ ｒｅｔｕｒｎ ｘ ｅｌｓｅ ｒｅｔｕｒｎ ｆ（ｙ，ｘ ｍｏｄ ｙ）
ア ０
イ ３１
ウ ２４８
エ ５２７
解答 イ
解説 順番に追いかけていきます。

ｆ（７７５，５２７）：Ｙ≠０なので、ｆ（５２７，２４８）
ｆ（５２７，２４８）：Ｙ≠０なので、ｆ（２４８，３１）
ｆ（２４８，３１　）：Ｙ≠０なので、ｆ（３１，０）
ｆ（３１　，０　　）：Ｙ＝０なので、Ｘ＝３１が戻り値になる。
問７ 次の流れ図は、１から１００までの整数の総和を求め、結果を整数ｘに代入するアルゴリズムを示したものであるが、一部誤りがある。どのように訂正すればよいか。

画像（問7）を表示できません
ア @の処理を“０→ｘ”にする。
イ Aの条件判定を“ｉ：９９”にする。
ウ Bの処理を“ｘ＋ｉ→ｉ”にする。
エ Cの処理を“ｘ＋１→ｘ”にする。
解答 ア
解説 現状での流れ図を追跡していきます。

１→ｘ
１→ｉ

ｉ＝１≦１００により下へ
ｘ＋ｉ＝１＋１→ｘ
ｉ＋１＝１＋１→ｉ

ｉ＝２≦１００により下へ
ｘ＋ｉ＝２＋２→ｘ
ｉ＋１＝２＋１→ｉ

ｉ＝３≦１００により下へ
ｘ＋ｉ＝４＋３→ｘ
ｉ＋１＝３＋１→ｉ


これまでの流れで、ｉがループカウンタ、ｘが総和を求める変数だとわかります。
そして、１回目の条件で１＋１＝２となっています。この段階ではｘは１になっていなければおかしいので、ｘの初期値が間違いであることに気づきます
よって、１→ｘではなく、０→ｘとするべきです。
問８ 整列アルゴリズムの一つであるクイックソートの記述として、適切なものはどれか。
ア 対象集合から基準となる要素を選び、これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことで、整列を行う。
イ 対象集合から最も小さい要素を順次取り出して、整列を行う。
ウ 対象集合から要素を順次取り出し、それまでに取り出した要素の集合に順序関係を保つように挿入して、整列を行う。
エ 隣り合う要素を比較し、逆順であれば交換して、整列を行う。
解答 ア
解説 代表的なソート法を下にまとめます。

挿入ソート：既に整列済みのデータ列の正しい位置に、データを追加する操作を繰り返していく
選択ソート：データ中の最小値を求め、次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく
バブルソート：隣り合ったデータの比較と入替えを繰り返すことによって、小さな値のデータを次第に端の方に移していく
クイックソート：適当な基準値を選び、それより小さな値のグループと大きな値のグループにグループを分割する。この操作を繰り返していく
シェルソート：ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が１になるまでこれを繰り返す
ヒープソート：未整列の部分を順序木に構成し、そこから最大値又は最小値を取り除いて既整列の部分に移す。これらの操作を繰り返して、未整列部分を縮めていく

選択肢イは選択ソート、選択肢ウは挿入ソート、選択肢エはバブルソートの説明です。
問９ 外部割込みが発生するものはどれか。
ア 仮想記憶管理での、主記憶に存在しないページへのアクセス
イ システムコール命令の実行
ウ ゼロによる除算
エ 入出力動作の終了
解答 エ
解説 割り込み(Interrupt)とは、現在の処理を中断して、割り込んできた新しい処理を行うことをいいます。異常事態が発生した場合や、現在行っている処理よりも優先度の高い処理が発生し場合に割込みが発生します。

そして、割り込みは以下の２つに分類されます。
内部割込み（実行中のプログラムに係る割込み）：オーバーフローやゼロによる除算、不正なメモリアドレスへのアクセス等
外部割込み（実行中のプログラムに関係のない割込み）：Ｉ／Ｏの操作、ネットワークからのデータ受信、電源の異常等
問１０ “ＬＯＡＤ ＧＲ，Ｂ，ＡＤ”はＡＤが示す番地にベースレジスタＢの内容を加えた値を有効アドレスとして、その有効アドレスが示す主記憶に格納されているデータを汎用レジスタＧＲにロードする命令である。

図の状態で、次の命令を実行したとき、汎用レジスタＧＲにロードされるデータはどれか。

ＬＯＡＤ ＧＲ，１，２００

画像（問10）を表示できません
ア １２０１
イ １３００
ウ ２２００
エ ２３００
解答 イ
解説 命令ではＢ＝１，ＡＤ＝２００となっています。これを元に、問題文に追従しながら、アドレスを計算します。
ＡＤが示す番地（２００）にベースレジスタＢ（ベースレジスタ１）の内容（１００）を加えた値を有効アドレス（２００＋１００＝３００）として、その有効アドレスが示す主記憶に格納されているデータ（３００番地に格納されている値は１３００）をＧＲにロードする。

よって、ＧＲには１３００がロードされます。
問１１ 主記憶のアクセス時間６０ナノ秒、キャッシュメモリのアクセス時間１０ナノ秒のシステムがある。キャッシュメモリを介して主記憶にアクセスする場合の実効アクセス時間が１５ナノ秒であるとき、キャッシュメモリのヒット率は幾らか。
ア ０．１
イ ０．１７
ウ ０．８３
エ ０．９
解答 エ
解説 ヒット率をａとして計算します。

１０×ａ＋６０×（１−ａ）＝１５
１０ａ＋６０−６０ａ＝１５
５０ａ＝４５

よって、ａ＝０．９（９０％）となります。
問１２ メモリインタリーブの説明はどれか。
ア ＣＰＵと磁気ディスク装置との間に半導体メモリによるデータバッファを設けて、磁気ディスクアクセスの高速化を図る。
イ 主記憶のデータの一部をキャッシュメモリにコピーすることによって、ＣＰＵと主記憶とのアクセス速度のギャップを埋め、メモリアクセスの高速化を図る。
ウ 主記憶へのアクセスを高速化するため、アクセス要求、データの読み書き及び後処理が終わってから、次のメモリアクセスの処理に移る。
エ 主記憶を複数の独立したグループに分けて、各グループに交互にアクセスすることによって、主記憶へのアクセスの高速化を図る。
解答 エ
解説 メモリインタリーブとは、主記憶を複数の独立したグループに分けて、各グループに交互にアクセスすることによって、主記憶へのアクセスの高速化を図るものです。以下の例ではアクセス幅が１の場合は３語分、アクセス幅が２の場合は６語分に同時にアクセスできます。

メモリインタリーブを表示できません

選択肢アは、ディスクキャッシュの説明です。
選択肢イは、キャッシュメモリの説明です。
選択肢ウの手法では、高速化できません。
問１３ ＲＦＩＤタグの特徴として、適切なものはどれか。
ア 磁性体に記録された情報を接触によって読み取る。
イ 赤外線を用いて情報を非接触で読み取る。
ウ 電磁波を用いて情報を非接触で読み取る。
エ バーコードで記録された情報を光学的に読み取る。
解答 ウ
解説 ＲＦＩＤ（Radio Frequency Identification）とは、小型のＩＣチップを無線で認識することにより、対象物を認識する技術です。非接触であり、バーコードに変わる技術として注目されています。汚れに強い上に、梱包の外からもデータを読み取ることができます。現在では図書館などの本の管理などで実用化され始めています。

選択肢アは、ＨＤＤや磁気カード等の説明です。
選択肢イは、ＩｒＤＡの説明です。
選択肢エは、バーコードの説明です。
問１４ アナログ音声信号を、サンプリング周波数４４．１ｋＨｚのＰＣＭ方式でディジタル録音するとき、録音されるデータ量は何によって決まるか。
ア 音声信号の最高周波数
イ 音声信号の最大振幅
ウ 音声データの再生周波数
エ 音声データの量子化ビット数
解答 エ
解説 ＰＣＭ（Pulse Code Modulation：パルス符号変調）とは音声などのアナログ信号をディジタル信号に変換する手法の一つです。
アナログデータ（時間も振幅も連続）をディジタルデータに変換するためには、標本化→量子化→符号化という作業を行います。各作業を簡単に以下にまとめます。

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

符号化と量子化は、多くのサンプリングポイントを取ることで、よりオリジナルに近いデータを作り出すことができます（データ量は多くなります）
問１５ コンピュータシステムの構成に関する記述のうち、密結合マルチプロセッサシステムを説明したものはどれか。
ア 通常は一方のプロセッサは待機しており、本稼動しているプロセッサが故障すると、待機中のプロセッサに切り替えて処理を続行する。
イ 複数のプロセッサが磁気ディスクを共用し、それぞれ独立したＯＳで制御される。ジョブ単位で負荷を分散することで処理能力を向上させる。
ウ 複数のプロセッサが主記憶を共用し、単一のＯＳで制御される。システム内のタスクは、基本的にどのプロセッサでも実行できるので、細かい単位で負荷を分散することで処理能力を向上させる。
エ 並列に接続された２台のプロセッサが同時に同じ処理を行い、相互に結果を照合する。１台のプロセッサが故障すると、それを切り離して処理を続行する。
解答 ウ
解説 複数のＣＰＵが主記憶やＯＳ、データを共有する形態を密結合マルチプロセッサといいます。逆に、各々のＣＰＵが占有の主記憶、ＯＳ、データをもち、バスで接続されている形態を疎結合マルチプロセッサといいます。

選択肢アは、デュプレックスシステムの説明です。
選択肢イは、疎結合マルチプロセッサシステムの説明です。
選択肢エは、デュアルシステムの説明です。
問１６ 装置ａとｂのＭＴＢＦとＭＴＴＲが表のとおりであるとき、ａとｂを直列に接続したシステムの稼働率は幾らか。

画像（問16）を表示できません
ア ０．７２
イ ０．８０
ウ ０．８５
エ ０．９０
解答 ア
解説 まずは、個々に計算してみましょう。稼働率はＭＴＢＦ／（ＭＴＢＦ＋ＭＴＴＲ）で求めます。
装置a：80/(80+20)=0.8
装置b：180/(180+20)=0.9

これらが直列に接続されているので0.8×0.9=0.72となります。
問１７ システムの信頼性設計のうち、フールプルーフを採用した設計はどれか。
ア オペレータが不注意による操作誤りを起こさないように、操作の確認などに配慮した設計
イ システムの一部に異常や故障が発生したとき、その影響が小さくなるような設計
ウ 障害の発生を予防できるように、機器の定期保守を組み入れた運用システムの設計
エ 装置を二重化し、一方が故障してもその装置を切り離してシステムの運用を継続できる設計
解答 ア
解説 重要なシステム設計法についてまとめておきます。

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

選択肢イは、フェールセーフの説明です。
選択肢ウは、フォールトアボイダンスの説明です。
選択肢エは、フォールトトレランスの説明です。
問１８ ＣＰＵが１台で、入出力装置（Ｉ／Ｏ）が同時動作可能な場合の二つのタスクＡ，Ｂのスケジューリングは図のとおりであった。この二つのタスクにおいて、入出力装置がＣＰＵと同様に、一つの要求だけを発生順に処理するように変更した場合、両方のタスクが終了するまでのＣＰＵ使用率はおよそ何％か。

画像（問18）を表示できません
ア ４３
イ ５０
ウ ６０
エ ７５
解答 ウ
解説 まずは、Ｉ／Ｏが重複しないようにスケジューリングを調整すると以下のようになります。

画像（問18kai）を表示できません

全体の時間は２５で、タスクＡのＣＰＵ使用時間は８、タスクＢのＣＰＵ使用時間は７なので、（８＋７）／２５＝０．６＝６０％となります。
問１９ Ｗｅｂサーバとデータベースサーバ各１台で構成されているシステムがある。次の運用条件の場合、このシステムでは最大何ＴＰＳ処理できるか。ここで、各サーバのＣＰＵは、１個とする。

[運用条件]
（１） トランザクションは、Ｗｅｂサーバを経由し、データベースサーバでＳＱＬが実行される。
（２） Ｗｅｂサーバでは、１トランザクション当たり、ＣＰＵ時間を１ミリ秒使用する。
（３） データベースサーバでは、１トランザクション当たり、データベースの１０データブロックにアクセスするＳＱＬが実行される。１データブロックのアクセスに必要なデータベースサーバのＣＰＵ時間は、０．２ミリ秒である。
（４） ＣＰＵ使用率の上限は、Ｗｅｂサーバが７０％、データベースサーバが８０％である。
（５） トランザクション処理は、ＣＰＵ時間だけに依存し、Ｗｅｂサーバとデータベースサーバは互いに独立して処理を行うものとする。
ア ４００
イ ５００
ウ ７００
エ １，１００
解答 ア
解説 まず、ＴＰＳ（Transaction Per Second）とは、１秒間に処理できるトランザクションの量を表す単位です。それでは、ＷｅｂサーバとデータベースサーバのＴＰＳを計算していきます。

Ｗｅｂサーバ：１トランザクション当たり１ミリ秒なので、１秒間に１０００件処理できます。しかし、ＣＰＵ使用率上限が７０％なので、７００ＴＰＳとなります。
データベースサーバ：１トランザクション当たり１０データブロックにアクセス、１データブロック当たり０．２ミリ秒。よって、１トランザクション当たり２ミリ秒なので、１秒間に５００件処理できます。しかし、ＣＰＵ使用率の上限が８０％なので、４００ＴＰＳとなります。

Ｗｅｂサーバでは１秒間に７００件のトランザクションを処理できますが、データベースサーバでは１秒間に４００件しか処理できません。
よって、データベースサーバがボトルネックとなり、全体では４００ＴＰＳとなります。
問２０ ページング方式の説明として、適切なものはどれか。
ア 仮想記憶空間と実記憶空間を、固定長の領域に区切り、対応付けて管理する方式
イ 主記憶装置の異なった領域で実行できるように、プログラムを再配置する方式
ウ 主記憶装置を、同時に並行して読み書き可能な複数の領域に分ける方式
エ 補助記憶装置に、複数のレコードをまとめて読み書きする方式
解答 ア
解説 ページングとは、仮想記憶において固定長のページという単位でデータを入れ替えたりすることをいいます。

選択肢イは、ダイナミックリロケーションの説明です。
選択肢ウは、メモリインタリーブの説明です。
選択肢エは、ブロック化の説明です。