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

応用情報

（応用情報技術者試験）

問３ 符号長７ビット、情報ビット数４ビットのハミング符号による誤り訂正の方法を、次のとおりとする。 受信した符号語が１０００１０１であった場合、誤り訂正後の符号語はどれか。

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

解答 エ

解説 ひとつづつ計算していきます。 Ｃ0=（１＋０＋１＋１）％２＝１ Ｃ1=（０＋０＋０＋１）％２＝１ Ｃ2=（０＋１＋０＋１）％２＝０ となり、i=１＋２＋０で３ビット目が誤っているので、１０１０１０１が正解となります。なお、ｍｏｄのことを法、１１０の誤り検出ベクトルをシンドロームと言ったりもします。

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

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

解答 イ

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

問７ ｎ個の正の整数ｘ1，ｘ2，・・・ｘnが並んだ線形リストを[ｘ1，ｘ2，・・・ｘn]で表し、空リストは[]で表す。次のように再帰的に定義される関数ｆｕｎｃ（Ｌ）をＬ＝[１，３，２]を実引数として呼び出したとき、ｐｒｉｎｔ文によって表示される数字はどれか。ここで、プログラム中の＝は等号、：＝は代入を表す。

ア １２３ イ １３３ ウ ２２３ エ ２３３

解答 エ

解説 順番に追いかけていきます。 Ｌ＝[１，３，２]として、１回目のｆｕｎｃ（Ｌ）を実行する。 Ｌ＝[]ではないので、下へ Ａ＝１ Ｂ＝Ｆｕｎｃ（[３，２]） 　Ｌ＝[３，２]として、２回目のＦｕｎｃ（Ｌ）を実行する。 　Ｌ＝[]ではないので、下へ 　Ａ＝３ 　Ｂ＝Ｆｕｎｃ（[２]） 　　Ｌ＝[２]として、３回目のＦｕｎｃ（Ｌ）を実行する。 　　Ｌ＝[]ではないので、下へ 　　Ａ＝２ 　　Ｂ＝Ｆｕｎｃ（[]） 　　　Ｌ＝[]として、４回目のＦｕｎｃ（Ｌ）を実行する。 　　　Ｌ＝[]なので、０を返す。 　　３回目のＢは０が代入される。 　　Ｃ＝ｍａｘ（２，０）で２が代入される 　　２が表示される。 　２回目のＢには２が代入される 　Ｃ＝ｍａｘ（３，２）で３が代入される 　３が表示される １回目のＢには３が代入される Ｃ＝ｍａｘ（１，３）で３が代入される ３が表示される。 よって、２３３となります。なお、このプログラムは配列を後ろから比較しながら最大のものを順次表示しています。

問８ データが昇順にソートされた配列Ｘ[ｉ]（ｉ＝０，１，・・・，ｎ−１）を２分探索する。流れ図のａに入るものとして、適切なものはどれか。ここで、流れ図の中の割り算は小数点以下を切り捨てるものとする。

ア ｌｅｆｔ ＜ ｒｉｇｈｔ イ ｌｅｆｔ ≦ ｒｉｇｈｔ ウ ｌｅｆｔ＋１ ＜ ｒｉｇｈｔ エ ｌｅｆｔ＋１ ≦ ｒｉｇｈｔ

解答 イ

解説 ２分探索とは、ソートされているデータに対して、中間値と目的とを比較することで、大きいグループと小さいグループに分け、１回の検索で探索範囲を半分にしていく探索法です。オーダはｌｏｇ2ｎです。 ループの継続条件の左側（ｓｃｈ＝−１）は値がまだ見つかっていないことを意味しています。そして、右側には検索対象の配列の左端と右端の関係が入ります。ｌｅｆｔは０からｎ−１に向かって、ｒｉｇｈｔはｎ−１から０に向かって変化していきます。よってこの関係が続く限り処理を続けますので、ｌｅｆｔ＞ｒｉｇｈｔになると終了することになります。つまり、ｌｅｆｔ≦ｒｉｇｈｔの限りループを続けます。＝の場合も同じ要素を指しているので検索は行います。

問９ ＣＰＵのパイプライン処理を有効に機能させるプログラミング方法はどれか。

ア ＣＡＳＥ文を多くする。 イ 関数の個数をできるだけ多くする。 ウ 分岐命令を少なくする。 エ メモリアクセス命令を少なくする。

解答 ウ

解説 まず、パイプラインの例を下に示します。 なお、分かれた段階の個数をパイプラインの深さといい、１つの段階にかかる時間をパイプラインピッチといいます。 見てわかるとおり、パイプラインは、きれいに各段階が１つずつずれているのが理想的ですが、実際はこのようにきれいにはなりません。それは、依存関係や分岐命令によって、順番どおりに処理できない場合が生じるからです。逆に言えば、依存関係や分岐命令を極力減らすことでパイプラインを効果的に利用することができるといえます。 依存関係や分岐命令などによってパイプラインの順番どおりに処理されないような状況をパイプラインハザードといいます。

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

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

解答 エ

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

問１２ プロセッサと複数のメモリとを図のように接続した組込みシステムがある。１６進数で表記したアドレス２Ｆ０番地を読み出したとき、データを出力するメモリはどれか。ここで、デコーダは右の表のとおりに信号出力を行うものとし、データバスなどの信号線は省略している。

ア メモリ１ イ メモリ２ ウ メモリ３ エ メモリ４

解答 ウ

解説 まず、１６進数の３桁が１桁目＝Ａ０〜Ａ３、２桁目＝Ａ４〜Ａ７、３桁目がＡ８、Ａ９に対応しています。つまりアドレス２Ｆ０はＡ９〜Ａ０に「１０ １１１１ ００００」のように対応します。次にＡ９＝Ｐ＝１、Ａ８＝Ｑ＝０となっています。 右の対応表で見ると、対応を見ると Ａ＝１ Ｂ＝０ Ｃ＝１ Ｄ＝１ となっています。 Ａ、Ｂ、Ｃ、Ｄがそれぞれメモリ１、メモリ２、メモリ３、メモリ４に接続されています。 現在Ｂだけが、０なので、メモリ２のデータをアクセスするということが分かります。 ＣＳとは一般的にチップセレクトの略で、入力の切り替え用の信号として利用されることが多いです。

問１７ ジョブの多重度が１で、到着順にジョブが実行されるシステムにおいて、表に示す状態のジョブＡ〜Ｃを処理するとき、ジョブＣが到着してから実行が終了するまでのターンアラウンドタイムは何秒か。ここで、ＯＳのオーバヘッドは考慮しないものとする。

ア １１ イ １２ ウ １３ エ １４

解答 ア

解説 到着順とは、その名の通りジョブが到着した順に処理が行われ、優先度や処理時間などは考慮されません。ジョブの状態は以下のようになります。赤が処理中、青が待機中を表しています。 ジョブＣは、時刻３に到着し時刻１４に終了するので、１４−３で１１秒かかるといえます。

問２０ 三つの資源Ｘ〜Ｚを占有して処理を行う四つのプロセスＡ〜Ｄがある。各プロセスは処理の進行に伴い、表中の数値の順に資源を占有し、実行終了時に三つの資源を一括して解放する。プロセスＡとデッドロックを起こす可能性のあるプロセスはどれか。

ア Ｂ，Ｃ，Ｄ イ Ｃ，Ｄ ウ Ｃだけ エ Ｄだけ

解答 イ

解説 データ更新中にデータを参照しようとすると、更新が失敗したり正しいデータが参照できなかったりします。よって、更新処理が完了するまで参照を待たせます。これを占有ロックといいます。また、データを読み出す場合に、書き換えられないようにかけるロックを共有ロックといいます。そして、ロックを互いにかけたまま処理が進まなくなる場合もあり、これをデッドロックといいます。デッドロックの例を下に示します。 それでは解答を考えます。 まず、プロセスＡは、Ｘ→Ｙ→Ｚの順に資源を確保します。 プロセスＢは、プロセスＡと同じ順番に資源を確保するので、デッドロックは発生しません。 プロセスＣは、Ｚ→Ｘ→Ｙの順に資源を確保するので、プロセスＡがＸを確保しプロセスＢがＺを確保すると、プロセスＡがＹを確保した時点でデッドロックとなります。 プロセスＤは、Ｚ→Ｙ→Ｘの順に資源を確保するので、プロセスＡがＸを確保しプロセスＢがＹを確保するとデッドロックとなります（ＹとＺでも発生する可能性があります） プロセスが一括で資源を解放するところに注意してください。