平成２５年度 秋期 応用情報技術者試験 問１−２０ 解答編

応用情報

（応用情報技術者試験）

問4 論理式Ｐ、Ｑがいずれも真であるとき、論理式Ｒの真偽にかかわらず真になる式はどれか。ここで、“　”は否定、“∨”は論理和、“∧”は論理積、“→”は含意（“真”→“偽”となるときに限り偽となる演算）を表す。

解答 エ

解説 まず、Ｐ＝真、Ｑ＝真を代入して、各選択肢を簡略化します。 選択肢ア：（（真→真）∧（真→真））→（Ｒ→偽）＝真→（Ｒ→偽） 選択肢イ：（（真→真）∧（真→偽））→（真→Ｒ）＝（真∧偽）→（真→Ｒ）＝真→（真→Ｒ） 選択肢ウ：（（真→偽）∨（真→真））→（Ｒ→偽）＝真→（Ｒ→偽） 選択肢エ：（（真→偽）∨（真→偽））→（真→Ｒ）＝偽→（真→Ｒ） 偽→○の場合は、どんな状態でも真になるので、選択肢エはＲの値に係らず（真→Ｒの値に係らず）真になるといえます。

問5 通信回線を使用したデータ伝送システムにM/M/1の待ち行列モデルを適用すると、平均回線待ち時間、平均伝送時間、回線利用率の関係は、次の式で表すことができる。 平均回線待ち時間 = 平均伝送時間 × 回線利用率/(1-回線利用率) 回線利用率が0%から徐々に上がっていく場合、平均回線待ち時間が平均伝送時間よりも最初に長くなるのは、回線利用率が何%を超えたときか。

ア 40 イ 50 ウ 60 エ 70

解答 イ

解説 まずは、待ち行列モデルのイメージを以下に図示します。 それでは問題に戻ります。この式は、ａ＝ｂ×α (０≦α)という形をしています。このとき、αがどんな値ならａ≧ｂになるかという風に変換することができます。 αが１ならばａ＝ｂとなるので、回線使用率／（１−回線使用率）＝１となる値を計算します。 Ｘ／（１−Ｘ）＝１ １−Ｘ＝Ｘ １＝２Ｘ Ｘ＝０．５ よって、回線使用率が５０％のときに等しくなるといえます。

問6 葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、深さとは根から葉に至るまでの枝の個数を表す。また、節点には根及び葉も含まれる。

ア 枝の個数がnならば、節点の個数もnである。 イ 木の深さがnならば、葉の個数は2n-1である。 ウ 節点の個数がnならば、深さはlog2nである。 エ 葉の個数がnならば、葉以外の節点の個数はn-1である。

解答 エ

解説 まず、木構造を以下にまとめます。今回は完全二分木の問題です。 深さをｎとした時の枝、葉、節点の個数を確認していきます。 ｎ＝１ → 枝：２、葉：２、節点：１＋２＝３ ｎ＝２ → 枝：２＋４＝６、葉４、節点：１＋２＋４＝７ ｎ＝３ → 枝：２＋４＋８＝１４、葉：８、節点：１＋２＋４＋８＝１５ これを元に各選択肢を調べていきます。 選択肢ア：枝がｎならば、節点はｎ＋１となります。 選択肢イ：木の深さがｎならば、葉の個数は２nとなります。 選択肢ウ：節点の個数がｎならば、深さは、（ｌｏｇ2（ｎ＋１））−１となります。 選択肢エ：葉の個数がｎならば、葉以外の節点の数はｎ−１となります。 よって、選択肢エが正解となります。

問7 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n とすると、キーaとbが衝突する条件はどれか。ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。

ア a+bがnの倍数 イ a-bがnの倍数 ウ nがa+bの倍数 エ nがa-bの倍数

解答 イ

解説 まず、実際に値を入れて計算してみたハッシュの例を下に示します。 ハッシュのイメージがつかめたところで計算に移ります。 上の図からもわかるように、二つの値の差がｎの倍数であれば衝突が起こることがわかります。 なお、整数論においては、『ｍｏｄ ｎ』のことを『ｎを法とする』などといいます。

問8 再帰的に定義された手続procで、porc(5)を実行したとき、印字される数字を順番に並べたものはどれか。

ア 543212345 イ 5432112345 ウ 54321012345 エ 543210012345

解答 イ

解説 順番に追いかけていくと以下のようになります。 ｐｒｏｃ（５） ｎ＝０でないので、５を印字する 　ｐｒｏｃ（４）をを呼び出す 　ｎ＝０でないので、４を印字する 　　ｐｒｏｃ（３）をを呼び出す 　　　ｎ＝０でないので、３を印字する 　　　ｐｒｏｃ（２）をを呼び出す 　　　ｎ＝０でないので、２を印字する 　　　　ｐｒｏｃ（１）をを呼び出す 　　　　ｎ＝０ではないので、１を印字する 　　　　　ｐｒｏｃ（０）を呼び出す 　　　　　ｎ＝０なので、戻る 　　　　ｐｒｏｃ（１）に戻って１を印字する 　　　ｐｒｏｃ（２）に戻って２を印字する 　　ｐｒｏｃ（３）に戻って３を印字する 　ｐｒｏｃ（４）に戻って４を印字する ｐｒｏｃ（５）に戻って５を印字する よって、５，４，３，２，１、と印字し、１，２，３，４，５と印字するので、選択肢イのようになります。

問9 未整列の配列a[i](i=1,2,3...,n)を、流れ図で示すアルゴリズムによって昇順に整列する。n=6でa[1]〜a[6]の値がそれぞれ、21,5,53,71,3,17の場合、流れ図において、a[j-1]とa[j]の値の入替えは何回行われるか。

ア 3 イ 6 ウ 8 エ 15

解答 ウ

解説 順番にトレースしていきます。 ループ１：ｉ＝１ 　　ループ２：ｊ＝６　３＜１７なので入れ替えない（２１，５，５３，７１，３，１７） 　　ループ２：ｊ＝５　７１＞３なので１回目の入れ替えを行う（２１，５，５３，３，７１，１７） 　　ループ２：ｊ＝４　５３＞３なので２回目の入れ替えを行う（２１，５，３，５３，７１，１７） 　　ループ２：ｊ＝３　５＞３なので３回目の入れ替えを行う（２１，３，５，５３，７１，１７） 　　ループ２：ｊ＝２　２１＞３なので４回目の入れ替えを行う（３，２１，５，５３，７１，１７） ループ１：ｉ＝２ 　　ループ２：ｊ＝６　７１＞１７なので５回目の入れ替えを行う（３，２１，５，５３，１７，７１） 　　ループ２：ｊ＝５　５３＞１７なので６回目の入れ替えを行う（３，２１，５，１７，５３，７１） 　　ループ２：ｊ＝４　５＜１７なので入れ替えない（３，２１，５，１７，５３，７１） 　　ループ２：ｊ＝３　２１＞５なので７回目の入れ替えを行う（３，５，２１，１７，５３，７１） ループ１：ｉ＝３ 　　ループ２：ｊ＝６　５３＜７１なので入れ替えない（３，５，２１，１７，５３，７１） 　　ループ２：ｊ＝５　１７＜７１なので入れ替えない（３，５，２１，１７，５３，７１） 　　ループ３：ｊ＝４　２１＞１７なので８回目の入れ替えを行う（３，５，１７，２１，５３，７１） この段階で整列が終わったため、入替え処理は実施されせん。 よって、８回が正解となります。

問10 メモリインタリーブの説明として、適切なものはどれか。

ア 新しい情報をキャッシュメモリに取り出すとき、キャッシュ上では不要になった情報を主記憶に書き込む。 イ 主記憶のアクセス時間と磁気ディスクのアクセス時間とのギャップを補う。 ウ 主記憶の更新と同時にキャッシュメモリの更新を行う。 エ 主記憶を幾つかの区画に分割し、連続したメモリアドレスへのアクセスを高速化する。

解答 エ

解説 メモリインタリーブとは、複数のバンクと呼ばれる単位に分けておくことで、高速にアクセスできます。アクセス幅が１の場合は３語分、アクセス幅が２の場合は６語分に同時にアクセスできます。 他の選択肢は以下のとおりです。 選択肢ア：キャッシュメモリと主記憶の同期方式の１つであるライトバック方式 選択肢イ：ディスクキャッシュ 選択肢ウ：キャッシュメモリと主記憶の同期方式の１つであるライトスルー方式

問11 容量がaMバイトでアクセス時間がxナノ秒のキャッシュメモリと、容量がbMバイトでアクセス時間がyナノ秒の主記憶をもつシステムにおいて、CPUからみた、主記憶とキャッシュメモリとを合わせた兵器なくセス時間を表す式はどれか。ここで、読み込みたいデータがキャッシュメモリに存在しない確率をrとし、キャッシュメモリ管理に関するオーバヘッドは無視できるものとする。

解答 イ

解説 キャッシュメモリは、主記憶装置（＝メインメモリ）とＣＰＵのレジスタとの処理速度の差を埋めるために用いられるメモリです。メインメモリはまず、キャッシュメモリにデータを探しに行き、そのデータがある場合は、キャッシュメモリから、ない場合はメインメモリからデータを読み出します。よって、存在しない確率 ×メインメモリの読み込み速度＋存在する確率×キャッシュメモリの読み込み速度となります。両者の容量はアクセス速度には関係がありません。

問15 1件のデータを処理する際に、読取りには40ミリ秒、CPU処理には30ミリ秒、書込みには50ミリ秒掛かるプログラムがある。このプログラムで、n件目の書込みと並行してn+1件目のCPU処理とn+2件目の読取りを実行すると、1分当たりの最大データ処理件数は幾つか。ここで、OSのオーバヘッドは考慮しないものとする。

ア 500 イ 666 ウ 750 エ 1,200

解答 エ

解説 この問題は、パイプラインに関する問題です。まず、パイプラインの概念を以下にまとめます。 つぎに、処理の流れを少し書き出してみます。 １．１件目の読み出し ２．１件目のＣＰＵ処理 ３．１件目の書き込み、２件目の読み出し ４．２件目の書き込み、３件目のＣＰＵ処理、４件目の読み出し ５．３件目の書き込み、４件目のＣＰＵ処理、５件目の読み出し つまり、４０ミリ秒＋３０ミリ秒＋５０ミリ秒×ｎが１分（６００００ミリ秒）以下になるようにｎをできるだけ大きくしたいということです。 また、４０、３０は６００００に比べて十分小さいので無視して計算しても大丈夫です。 ６００００／５０＝１，２００となります。

問17 稼働率がα(0＜a＜1)の装置を三つ用いて図のようにシステムを設計するとき、システムの稼働率が装置単体の稼働率を上回るものはどれか。ここで、並列に接続されている部分は、いずれの経路が稼働していればシステムは稼働しているものとする。

ア AとB イ AとC ウ BとC エ 全て

解答 イ

解説 順番に稼働率を計算していきます。便宜上稼働率を０．９として計算します。 Ａ：３台のうち１台以上が動作している確率＝１−（３台とも故障している確率）＝１−（１−０．９）3＝１−０．００１＝０．９９９ Ｂ：０．９×並列部＝０．９×（１−（１−０．９）2）＝０．９×０．９９＝０．８９１ Ｃ：０．９と（直列部）の並列＝０．９と（０．９×０．９）の並列＝１−（１−０．９）×（１−０．８１）＝１−０．１×０．１９＝０．９８１ よって、ＡとＣが単体よりも稼働率が高くなるといえます。 なお、単体と全体の稼働率については以下のようなことがいえます。 単体と機器が直列に繋がっている場合、単体よりも全体の稼働率は低下します。 単体と機器が並列に繋がっている場合、単体よりも全体の稼働率は向上します。（並列部が1台以上動作していればよい場合)