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

応用情報

（応用情報技術者試験）

問１ 通信回線を使用したデータ転送システムにＭ／Ｍ／１の待ち行列モデルを適応すると、平均回線待ち時間、平均伝送時間、回線利用率の関係は、次の式で表すことができる。 回線利用率が０％から徐々に上がっていく場合、平均回線待ち時間が平均伝送待ち時間よりも最初に長くなるのは、回線利用率が何％を超えたときか。

ア ４０ イ ５０ ウ ６０ エ ７０

解答 イ

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

問３ 次に示す有限オートマトンが受理する入力列はどれか。ここで、Ｓ1は初期状態を、Ｓ3は受理状態を表している。

ア １０１１ イ １１００ ウ １１０１ エ １１１０

解答 ウ

解説 実際に状態を遷移しながら解いていきます。 選択肢ア：Ｓ1 −(1)→ Ｓ2 −(0)→ Ｓ2 −(1)→ Ｓ1 −(1)→ Ｓ2 選択肢イ：Ｓ1 −(1)→ Ｓ2 −(1)→ Ｓ1 −(0)→ Ｓ3 −(0)→ Ｓ2 選択肢ウ：Ｓ1 −(1)→ Ｓ2 −(1)→ Ｓ1 −(0)→ Ｓ3 −(1)→ Ｓ3 選択肢エ：Ｓ1 −(1)→ Ｓ2 −(1)→ Ｓ1 −(1)→ Ｓ2 −(0)→ Ｓ2

問６ 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーｘのハッシュ関数ｈ（ｘ）を ｈ（ｘ）＝ｘ ｍｏｄ ｎ とすると、キーａとｂが衝突する条件はどれか。ここで、ｎはハッシュ表の大きさであり、ｘ ｍｏｄ ｎはｘをｎで割った余りを表す。

ア ａ＋ｂがｎの倍数 イ ａ−ｂがｎの倍数 ウ ｎがａ＋ｂの倍数 エ ｎがａ−ｂの倍数

解答 イ

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

問７ 文字列を引数とする関数len,first,butfirstを用いて、関数compを再帰的に定義した。comp("11","101")を呼び出したとき、返されるものはどれか。

ア −１ イ ０ ウ １ エ エラー

解答 ア

解説 まず、プログラムの解説をします。 最初の３行で、一方（あるいは両方）の文字列が空になったときの大小関係を見ています。 両方０なら０を返す。Ｂの方が長いなら１を返す。Ａの方が長いならＢを返す。 次の２行で、先頭の文字を比較しています。 Ｂの方が大きいなら１を返す。Ａの方が大きいならー１を返す 最後の１行は、この段階では大小が決まらなかったので、先頭の１文字を除いた残りの部分でもう一度チェックする これを踏まえて、プログラムを追っていきます。 まず、最初の（“１１”と“１０１”）は長さが両方とも１以上で先頭が両方とも１で同じなのでｒｅｔｕｒｎ文に行きます。 つぎに、（“１”と“０１”）は長さが両方とも１以上で、１＞０なので、−１が戻ります。 ｃｏｍｐという関数名から何らかの比較をすることが推測できますが、一般的で単純な２進数の大小関係の比較ではないことに注意しましょう。（３と５なら１が戻るはずです。）

問１１ メモリインタリーブの説明はどれか。

ア ＣＰＵと磁気ディスク装置との間に半導体メモリによるデータバッファを設けて、磁気ディスクアクセスの高速化を図る。 イ 主記憶のデータの一部をキャッシュメモリにコピーすることによって、ＣＰＵと主記憶とのアクセス速度のギャップを埋め、メモリアクセスの高速化を図る。 ウ 主記憶へのアクセスを高速化するため、アクセス要求、データの読み書き及び後処理が終わってから、次のメモリアクセスの処理に移る。 エ 主記憶を複数の独立したグループに分けて、各グループに交互にアクセスすることによって、主記憶へのアクセスの高速化を図る。

解答 エ

解説 メモリインタリーブとは、複数のバンクと呼ばれる単位に分けておくことで、高速にアクセスできます。アクセス幅が１の場合は３語分、アクセス幅が２の場合は６語分に同時にアクセスできます。

問１５ 物理的に複数のサーバを用意したときと比較した場合、仮想化によって１台のサーバに統合したときの特徴はどれか。ここで、物理的な資源とは、ＣＰＵ，主記憶、磁気ディスクなどのコンピュータを構成する装置を指す。

解答 ア

解説 サーバを作る場合に、Ｗｅｂサーバ、メールサーバ、ＬＤＡＰサーバ、ＳＳＨサーバ、など役割ごとに別のマシンにし、ＤＭＺなどに導入するのが一般的ですが、これらを１つの統合サーバとして管理することもできます。これにより、管理が簡単になる反面、アクセスが集中するので、利用率が高くなりオーバヘッドも増えます。さらに、障害によりすべての機能が使えなくなるというリスクも増大します。

問１６ ３台の装置Ｘ〜Ｚを接続したシステムＡ、Ｂの稼働率について、適切なものはどれか。ここで、３台の装置の稼働率は、いずれも０より大きく１より小さいものとする。

ア 各装置の稼働率の値によって、ＡとＢの稼働率のどちらかが高いかは変化する。 イ 常にＡとＢの稼働率は等しい ウ 常にＡの稼働率が高い エ 常にＢの稼働率が高い。

解答 エ

解説 Ｘ、Ｙ、Ｚの稼働率をｘ、ｙ、ｚとしてＡとＢの稼働率を計算します。 Ａ：並列部×ｚ＝｛１−｛（１−ｘ）×（１−ｙ）｝｝×ｚ＝｛１−（１−ｘ−ｙ＋ｘｙ）｝×ｚ＝｛１−１＋ｘ＋ｙ−ｘｙ｝×ｚ＝ｘｚ＋ｙｚ−ｘｙｚ Ｂ：ｘｙとｚの並列＝１−（１−ｘｚ）×（１−ｙ）｝＝１−（１−ｙ−ｘｚ＋ｘｙｚ）＝ｙ＋ｘｚ−ｘｙｚ Ｂ−Ａ＝（ｙ＋ｘｚ−ｘｙｚ）−（ｘｚ＋ｙｚ−ｘｙｚ）＝ｙ＋ｘｚ−ｘｙｚ−ｘｚ−ｙｚ＋ｘｙｚ＝ｙ−ｙｚ＝ｙ（１−ｚ） ｘ、ｙ、ｚ＞０なので、 ｙ（１−ｚ）＝正×正＞０となります。 つまり、Ｂ−Ａ＞０なので、Ｂ＞Ａが導けます。

問１７ ＣＰＵと磁気ディスク装置で構成されるシステムで、表に示すジョブＡ、Ｂを実行する。この二つのジョブが実行を終了するまでのＣＰＵの使用率と磁気ディスク装置の使用率との組合せのうち、適切なものはどれか。ここで、ジョブＡ、Ｂはシステムの動作開始時点ではいずれも実行可能状態にあり、Ａ、Ｂの順で実行される。ＣＰＵ及び磁気ディスク装置は、ともに一つの要求だけを発生順に処理する。ジョブＡ、Ｂとも、ＣＰＵの処理を終了した後、磁気ディスク装置の処理を実行する。

解答 イ

解説 処理を図示すると以下のようになります。 なので、全体で２５かかり、ＣＰＵは３＋１２で１５、１５／２５＝０．６、ＨＤは７＋１０で１７で、１７／２５＝０．６８となります。

問２０ データ構造のキューを実現する方法において、片方向リンクに比べた場合の双方向リンクの特徴として、適切なものはどれか。

ア 片方向リンクよりオーバヘッドが小さい。 イ 追加は、最後尾だけに対して行える。 ウ 途中への挿入・取出しが容易に行える。 エ 取出しは、先頭だけに対して行える。

解答 ウ

解説 まず、片方向リストと双方向リストの例を下に示します。 追加や削除はどちらも任意の場所で行えます。オーバヘッドは、前へのリンクが増えた分修正に時間が掛かります。途中への挿入・取り出しはポインタを数ヶ所変えるだけで行えます。