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



このページは

応用情報

（応用情報技術者試験）

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

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


問１ ａを正の整数とし、ｂ＝ａ2とする。ａを２進数で表現すると、ｎビットであるとき、ｂを２進数で表現すると、高々何ビットになるか。
ア ｎ＋１
イ ２ｎ
ウ ｎ2
エ ２n
解答 イ
解説 まず、２桁と３桁で計算してみます。

　　１１
　×１１
　−−ー
　　１１
　１１　
−−−−
１００１

　　　１１１
　　×１１１
　　−−−−
　　　１１１
　　１１１　
　１１１
　−−−−−
１１０００１


２進数におけるｎ桁の最大値は、すべてが１の状態なので、２n−１となります。
つまり、積の最大は（２n−１）2なので、２2n−２・２n＋１となり＜２2nなので、高々２ｎ桁になることがわかります。
問２ 画像（問2）を表示できませんと等価な集合はどれか。ここで∪は和数号、∩は積集合、ＸはＸの補集合を表す。
ア （Ａ∪Ｂ）∩（Ａ∪Ｂ）
イ （Ａ∪Ｂ）∩（Ａ∪Ｂ）
ウ （Ａ∩Ｂ）∪（Ａ∩Ｂ）
エ （Ａ∩Ｂ）∩（Ａ∪Ｂ）
解答 ア
解説 この問題はド・モルガンの定理と呼ばれる以下のような変換法則を利用します。

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

画像（問2）を表示できませんをド・モルガンの定理と分配法則を利用して以下のように変換していきます。

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

よって、選択肢アの式と等価であるといえます。
問３ 図は、偶数個の１を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。ａ，ｂの適切な組合せはどれか。

画像（問3）を表示できません
画像（問3ans）を表示できません
解答 ウ
解説 １の個数が偶数か奇数を調べています。偶数と奇数は１が来るたびに入れ替わるので、【ａ】は１が入ります。０のときは偶数、奇数は変わらないので、【ｂ】には０が入ります
問４ ハミング符号とは、データに冗長ビットを付加して、１ビットの誤りを訂正できるようにしたものである。ここでは、Ｘ1,Ｘ2,Ｘ3,Ｘ4の４ビットから成るデータに、３ビットの冗長ビットＰ3,Ｐ2,Ｐ1を付加したハミング符号Ｘ1Ｘ2Ｘ3Ｐ3Ｘ4Ｐ2Ｐ1を考える。

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


ハミング符号１１１００１１には１ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。
ア ０１１００１１
イ １０１００１１
ウ １１０００１１
エ １１１０１１１
解答 ア
解説 それぞれのパリティの式に代入しながら確認します。なお、排他的論理和はＥＯＲと表記します。

１ ＥＯＲ １ ＥＯＲ ０ ＥＯＲ １ ＝ １
１ ＥＯＲ １ ＥＯＲ ０ ＥＯＲ １ ＝ １
１ ＥＯＲ １ ＥＯＲ １ ＥＯＲ ０ ＝ １

誤りは１ビットしかなく、かつ１ビット確実にあることが保障されているので、すべての式に影響があるＸ1が誤りであることがわかります。
問５ 探索表の構成法を例とともにａ〜ｃに示す。最も適した探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

画像（問5）を表示できません
画像（問5ans）を表示できません
解答 ア
解説 まず、３つの探索法についてまとめます。データ量をｎとしたときのオーダ（検索時間）もあわせてまとめます。

２分探索：ソートされているデータに対して、中間値と目的とを比較することで、大きいグループと小さいグループに分け、１回の検索で探索範囲を半分にしていく。オーダはｌｏｇ2ｎ
線形探索：上から一つずつ比較していく方法。オーダはｎ
ハッシュ検索：ハッシュ関数を使って、格納場所を決める方法。ハッシュ値が同じになる衝突（シノニム）などがなければ、１度で検索場所が決まります。オーダは１

つぎに、それぞれの表に適した検索法を考えます。
表ａ：コードが順番にならんでいる（ソートされている）ので、線形探索よりも２分探索のほうが高速に検索ができるので、２分探索を利用します。
表ｂ：コードに規則性がないが、使用頻度順にならんでいるということは、上にあるものほど発見しやすいので、線形探索を利用します。
表ｃ：ハッシュにより場所を決めているので、同じ関数を利用して求めるのが一番よいので、ハッシュ表探索を利用します。
問６ ｆｕｎｃ（ｎ）は、非負の整数ｎに対してｎの階乗を返す。ｆａｎｃ（ｎ）の再帰的な定義はどれか。
ア ｉｆ ｎ＝０ ｔｈｅｎ ｒｅｔｕｒｎ ０ ｅｌｓｅ ｒｅｔｕｒｎ ｎ×ｆａｃｔ（ｎ−１）
イ ｉｆ ｎ＝０ ｔｈｅｎ ｒｅｔｕｒｎ ０ ｅｌｓｅ ｒｅｔｕｒｎ ｎ×ｆａｃｔ（ｎ＋１）
ウ ｉｆ ｎ＝０ ｔｈｅｎ ｒｅｔｕｒｎ １ ｅｌｓｅ ｒｅｔｕｒｎ ｎ×ｆａｃｔ（ｎ−１）
エ ｉｆ ｎ＝０ ｔｈｅｎ ｒｅｔｕｒｎ １ ｅｌｓｅ ｒｅｔｕｒｎ ｎ×ｆａｃｔ（ｎ＋１）
解答 ウ
解説 ５の階乗を例に考えます。５の階乗は、５×４の階乗。４の階乗は４×３の階乗のように考えます。（ｎの階乗をｎ！と表記します。）

５！＝５×４！
４！＝４×３！
３！＝３×２！
２！＝２×１！
１！＝１×０！
０！＝１

つまり、１ステップは、ｎ×（ｎ−１）！となります。そして、０！は１と定義されています。（０！＝０ではどんな階乗でも０となるため）
これを、プログラムの式になおすと、選択肢ウのようになります。
問７ 配列Ａに対して次の手続を実行して、２≦ｋ≦１００である素数ｋだけを全て出力したい。ａ，ｂ，ｃに入るループの初期値、終値、増分として、適切な組合せはどれか。

画像（問7）を表示できません
画像（問7ans）を表示できません
解答 イ
解説 このアルゴリズムをエラトステネスの篩といいます。名前を知らなくても、問題を回答することは可能です。

このアルゴリズムは、３つの部分から構成されています。 １．全てを１で初期化する部分
２．ふるいにかける部分
３．要素が０の要素を表示する部分

エラストテネスの篩では、素数は１とその数でしか割り切れないという性質から、２の倍数を素数の対象から外す、３の倍数を素数の対象から外すというように、値の定数倍を素数の対象から外していくという処理を行います。２番目の篩の外側では、２から１０までを順番に処理しています。１０は１００の平方数で、１０は最も大きい約数の候補のため、ここまで調べればすべての素数を探索することができます。

その内側の処理では、特定の値ｍに対して、その定数倍（ｋ）を順番に候補から消しています。つまりｍの次（２ｍ）からｍずつ増やしながら１００までを調べています。
問８ 流れ図に示す処理の動作として、適切なものはどれか。ここで、二重線は並列処理の同期を表す。

画像（問8）を表示できません
ア ＡＢＣ又はＡＣＢを実行してデッドロックになる。
イ ＡＢ又はＡＣを実行してデッドロックになる。
ウ Ａの後にＢＣ又はＣＢ、ＢＣ又はＣＢ、・・・と繰り返して実行する。
エ Ａの後にＢの無限ループ又はＣの無限ループになる。
解答 ウ
解説 まず、処理が開始されるとＡが実行されます。その後、ＢかＣのどちらかが実行されます。そして、同期線をで他方の処理が終わるのをまちます。よって、ＢＣ又はＣＢが実行されます。これを繰り返して実行してきます。
問９ 表に示す命令ミックスによるコンピュータの処理能力は何ＭＩＰＳか。

画像（問9）を表示できません
ア １１
イ ２５
ウ ４０
エ ９０
解答 ウ
解説 まず、ＭＩＰＳ（million instructions per second）とは、１秒間に何百万個の命令が実行できるかを表しています。次に、１命令の平均実行時間を求めると１０×０．５＋５０×０．３＋５０×０．２＝５＋１５＋１０＝３０ナノ秒となります。１つの命令が３０ナノ秒なので、１秒間に実行できる命令の数は、１／３０ナノ秒＝１／（３０×１０-9）≒３３×１０6なので、約３３ＭＩＰＳであるといえます。
問１０ ＣＰＵのパイプラインハザードのうち、制御ハザードの発生原因として、適切なものはどれか。
ア キャッシュミス
イ 先行する命令の結果に依存する演算命令
ウ ハードウェア資源の競合
エ 分岐命令
解答 エ
解説 パイプラインとは、下の図のように命令の段階を少しずつずらして行う方式です。なお各段を多重化したスーパースケーラ（スーパスカラ）方式というのもあります。なお、依存関係や分岐命令などによってパイプラインの順番どおりに処理されないような状況をパイプラインハザードといいます。

パイプラインを表示できません
問１１ 複数のデータに対して１個の命令で同一の操作を同時並列に行う方式で、マルティメディアデータなどを扱うＣＰＵに採用されているものはどれか。
ア ＭＩＭＤ
イ ＭＩＳＤ
ウ ＳＩＭＤ
エ ＳＩＳＤ
解答 ウ
解説 これは、フリンの分類と呼ばれる命令とデータの並列性を基にした分類法です

ＳＩＳＤ：（単一命令、単一データ）命令にもデータにも並列性のない逐次的なコンピュータ
ＳＩＭＤ：（単一命令、複数データ）ベクトル演算機やＧＰＵ等
ＭＩＳＤ：（複数命令、単一データ）命令列が複数あり、それを1 つのデータストリームに適用する形態のコンピュータ。あまり一般的ではない
ＭＩＭＤ：（複数命令、複数データ）複数のプロセッサが同時並行的にそれぞれ異なるデータを異なる命令で処理するコンピュータ
問１２ キャッシュの書込み方式には、ライトスルー方式とライトバック方式がある。ライトバック方式を使用する目的として、適切なものはどれか。
ア キャッシュと主記憶の一貫性（コヒーレンシ）を保ちながら、書込みを行う。
イ キャッシュミスが発生したときに、キャッシュの内容の主記憶への書き戻しを不要にする。
ウ 個々のプロセッサがそれぞれのキャッシュをもつマルチプロセッサシステムにおいて、キャッシュ管理を簡単な回路構成で実現する。
エ プロセッサから主記憶への書込み頻度を減らす。
解答 エ
解説 キャッシュメモリは、主記憶とＣＰＵのレジスタの速度の差を埋めるために用いられるものです。主記憶とキャッシュのの整合性を保つための書込み手法が以下の２種類です。

ライトスルー：キャッシュメモリ及び主記憶の両方に同時に書き込む。
ライトバック：キャッシュメモリにだけ書き込み、対応する主記憶の更新は、キャッシュメモリからデータが追い出されるときに行う。

これをもとに選択肢を順にみていきます。
選択肢ア：ライトバックは、一時的にキャッシュメモリと主記憶の内容が異なります。
選択肢イ：ライトバックは、キャッシュミスが発生した場合に、主記憶へ書き戻しを行います。
選択肢ウ：ライトバックは、同じ情報をキャッシュメモリと主記憶に書き込むライトスルーと違い管理機構が複雑となります。
選択肢エ：ライトバックは、キャッシュミスが発生しない限り主記憶への書込みはないため、主記憶への書込み頻度を減らすことができます。（正解）
問１３ ３層クライアントサーバシステムの各層の役割のうち、適切なものはどれか。
ア データベースアクセス層は、データを加工してプレゼンテーション層に返信する。
イ ファンクション層は、データベースアクセス層で組み立てられたＳＱＬ文を解釈する。
ウ ファンクション層は、データを加工してプレゼンテーション層に返信する。
エ プレゼンテーション層は、データベースアクセス層にＳＱＬ文で問い合わせる。
解答 ウ
解説 サーバとはサービスを提供するもので、クライアントとはサービスを依頼する（受け取る）ものです。まず、２層と３層についてまとめます。

２層：サーバとクライアント
３層：プレゼンテーション層・ファンクション層（アプリケーション層）・データベース層

そして、プレゼンテーション層がクライアントに該当する部分で、ファンクション層とデータベース層がサーバに該当する部分になります。

最後に、主な機能は以下のようになります。
プレゼンテーション層：クライアントへのインタフェース部分
ファンクション層：データの加工
データベース層：データへのアクセス
問１４ 密結合マルチプロセッサの性能が、１台当たりのプロセッサの性能とプロセッサ数の積に等しくならない要因として、最も適切なものはどれか。
ア 主記憶へのアクセスの競合
イ 通信回線を介したプロセッサ間通信
ウ プロセッサのディスパッチ処理
エ 割込み処理
解答 ア
解説 まず、密結合マルチプロセッサと疎結合マルチプロセッサの概要図を以下にまとめます。

密結合マルチプロセッサと疎結合マルチプロセッサを表示できません

密結合マルチプロセッサでは、主記憶を共有するため、必要なデータが競合する可能性があり、他方が待たされることがあります。
これにより、プロセッサ数に完全には比例しない結果となります。

なお、プロセッサ数に比例するような性質をスケーラビリティといいます。
問１５ システムの信頼性向上技術に関する記述のうち、適切なものはどれか。
ア 故障が発生したときに、あらかじめ指定されている安全な状態にシステムを保つことを、フェールソフトという。
イ 故障が発生したときに、あらかじめ指定されている縮小した範囲のサービスを提供することを、フォールトマスキングという。
ウ 故障が発生したときに、その影響が誤りとなって外部に出ないように訂正することを、フェールセーフという。
エ 故障が発生したときに対処するのではなく、品質管理などを通じてシステム構成要素の信頼性を高めることを、フォールトアボイダンスという。
解答 エ
解説 重要な高信頼システム設計法についてまとめておきます。

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

他の選択肢は以下のようになります。
選択肢アは、フェールセーフの説明です。
選択肢イは、フェールソフトの説明です。
選択肢ウは、フォールトマスキングの説明です。
問１６ ３台の装置Ｘ〜Ｚを接続したシステムＡ，Ｂの稼働率について、適切なものはどれか。ここで、３台の装置の稼働率は、いずれも０より大きく１より小さいものとする。

画像（問16）を表示できません
ア 各装置の稼働率の値によって、ＡとＢの稼働率のどちらが高いかは変化する。
イ 常にＡとＢの稼働率は等しい。
ウ 常にＡの稼働率が高い。
エ 常にＢの稼働率が高い。
解答 エ
解説 ３台の装置Ｘ，Ｙ，Ｚの稼働率をそれぞれｘ、ｙ、ｚとして、全体の稼働率を計算し比較して見ます。

Ａ：ＸとＹの並列部×ｚ＝｛１−（１−ｘ）×（１−ｙ）｝ｚ
Ｂ：１−（１−ＸとＹの直列部）×（１−ｚ）＝１−（１−ｘｙ）×（１−ｚ）

次に、それぞれを展開して比較しやすいようにします。×は省略します。
Ａ：ｚ−（１−ｘ）（１−ｙ）ｚ＝ｚ−（１−ｘ−ｙ＋ｘｙ）ｚ＝ｚ−（ｚ−ｘｚ−ｙｚ＋ｘｙｚ）＝ｚ−ｚ＋ｘｚ＋ｙｚ−ｘｙｚ＝ｘｚ＋ｙｚ−ｘｙｚ
Ｂ：１−（１−ｘｙ−ｚ＋ｘｙｚ）＝１−１＋ｘｙ＋ｚ−ｘｙｚ＝ｘｙ＋ｚ−ｘｙｚ

つまり、稼働率の比較は【ｘｚ＋ｙｚ−ｘｙｚとｘｙ＋ｚ−ｘｙｚ】を比較すればよいことになります。簡略化するために、両方にｘｙｚを加えてｘｚを引くと【ｘｚとｚ】の比較となります。

ｘ、ｚはともに１より小さいのでｘｚ＜ｚ（０．ａ，０．ｂ＜０．ａ×０．ｂ）となります。（接続的な意味を考えると｛ｘとｚの直列｝と｛ｚ｝の稼働率はｚのほうが高いという意味です。）よってＢの稼働率のほうが常に稼働率は高くなります。
問１７ 五つのジョブＡ〜Ｅに対して、ジョブの多重度が１で、処理時間順方式のスケジューリングを適用した場合、ジョブＢのターンアラウンドタイムは何秒か。ここで、ＯＳのオーバヘッド考慮しないものとする。

画像（問17）を表示できません
ア ８
イ ９
ウ １０
エ １１
解答 エ
解説 処理時間順方式とは、処理に掛かる時間が最も短いと予想されるタスクを優先的に処理する方式です。この方式に従ってタスクを処理すると以下のようになります。

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

タスクＢは処理開始から、１秒後に到着し１２秒後に終了するため、ターンアラウンドタイムは１１秒になるといえます。処理時間順方式は、処理に長い時間が掛かるタスクはずっと待たされてしまうため、ある程度時間が経過すると優先順位を上げる（エイジング）などの仕組みが必要となります。
問１８ ページング方式の仮想記憶において、ページフォールト発生時のオーバヘッドによる１命令当たりの平均遅れ時間を求める式はどれか。

【記号の説明】
ｔ：１回当たりのページフォールト処理時間
ｆ：ページフォールト発生率
ｍ；１命令当たりの平均主記憶アクセス回数
ア ｔ−ｆ×ｍ
イ ｔ×ｆ×ｍ
ウ ｔ×ｆ÷ｍ
エ ｔ÷ｆ÷ｍ
解答 イ
解説 ページング方式とは、仮想記憶において、固定長のページという単位で仮想と物理のデータを入れ替えることをいいます。必要とするデータがない場合には、ページフォールトとなりデータを入れ替える必要があります。

ページフォールト時には、主記憶へアクセスし（ｍ）ページフォールト処理（ｔ）を行います。そのため、１命令の平均遅れ時間は、これに発生確率（ｆ）を掛けたｔ×ｆ×ｍとなります。
問１９ 仮想記憶方式におけるプログラムやデータの格納方法に関する記述のうち、適切なものはどれか。
ア 一つのプログラムや一連のデータは、主記憶装置及び補助記憶装置で必ず連続した領域に格納される。
イ 頻繁に参照されるプログラムやデータが主記憶装置に格納されているので、仮想記憶を用いない場合に比べて主記憶の平均アクセス時間が短くなる。
ウ プログラムやデータを補助記憶装置に格納し、必要に応じて主記憶に読み込むので、主記憶の見かけの容量を拡大できる。
エ ページアウトされたプログラムやデータがシステムの停止後も補助記憶装置に保持されるので、再起動後に主記憶の内容が復元される。
解答 ウ
解説 仮想記憶方式とは、主記憶の容量が少なくプログラムが実行できないときなどに利用される技術です。ハードディスクの一部を主記憶のように使うことで、主記憶の見かけ上の容量が増加しますが、実際にはハードディスクを利用するわけですから、アクセス速度は低下します。
問２０ メインプログラムを実行した後、メインプログラムの変数Ｘ，Ｙの値は幾つになるか。ここで、仮引数Ｘは値呼び出し（call by value）、仮引数Ｙは参照呼出し（call by reference）であるとする。

画像（問20）を表示できません
画像（問20ans）を表示できません
解答 イ
解説 まず、値渡しの場合は、呼び出した関数側の変数（仮引数）へ値がコピーされて利用されるので、呼び出された側で値が書き換えられても呼び出した側の関数には反映されません。参照呼出しの場合は、アドレスが渡るので、呼び出された側で値が書き換えられた場合は、呼び出した側の値も書き換えられます。

ａｄｄ（２，２）がメインプログラムで実行され、Ｘ＝２＋２によりＸ＝４となります。つぎに、Ｙ＝４＋２によりＹ＝６となります。Ｘはメイン関数に反映されず、Ｙだけがメイン関数に反映されるので、Ｘは２のまま、Ｙは書き換えられた６となります。