平成１９年度 春期 ソフトウェア開発技術者試験 問１−２０ 解答編



このページは

ソフ開

（ソフトウェア開発技術者試験）

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

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


問１ 負数を２の補数で表現する３２ビットの二つの整数データを加算したとき、あふれが生じる必要十分条件はどれか。
ア ともに正で和が２31以上、又はともに負で絶対値の和が２31以上
イ ともに正で和が２31以上、又はともに負で絶対値の和が２31より大きい
ウ ともに正で和が２31より大きい、又はともに負で絶対値の和が２31以上
エ ともに正で和が２31より大きい、又はともに負で絶対値の和が２31より大きい
解答 イ
解説 ２の補数での最大の数値は「０１１１・・・１１１」なので、３２ビットでは、２31−１です。また、負数の最大は「１０００・・・０００」なので、３２ビットでは−２31となります。つまり、正＋正では、２31以上になるとオーバーフローとなり、負＋負（＝負−正）では、２31より大きい値になるとオーバーフローとなります。
問２ Ｒａｎｄｏｍ（）は、０以上１未満の一様乱数を発生する関数である。次の一連の手続きで得られるＺの値が従う分布の概形はどれか。

Ｘ＝Ｒａｎｄｏｍ（）
Ｙ＝Ｒａｎｄｏｍ（）
Ｚ＝Ｘ＋Ｙ
画像（問2ans）を表示できません
解答 イ
解説 ０〜１の実数を簡略化して、０、１、２で考えて見ます。Ｚの値とＸ、Ｙの組合せの種類は、以下のようになります。

０：Ｘ＝０、Ｙ＝０（１種類）
１：Ｘ＝１、Ｙ＝０。Ｘ＝０、Ｙ＝１（２種類）
２：Ｘ＝２、Ｙ＝０。Ｘ＝１、Ｙ＝１。Ｘ＝０、Ｙ＝２（３種類）
３：Ｘ＝２、Ｙ＝１。Ｘ＝１、Ｙ＝２（２種類）
４：Ｘ＝２、Ｙ＝２（１種類）

よって、徐々に種類が増えていき、頂点を境に徐々に減っていきます。
問３ 表は、ある地方の天気の移り変わりを示したものである。例えば、晴れの翌日の天気は、４０％の確率で晴れ、４０％の確率で曇り、２０％の確率で雨であることを表している。天気の移り変わりが単純マルコフ過程であると考えたとき、雨の２日後が晴れである確率は何％か。

画像（問3）を表示できません
ア １５
イ ２７
ウ ３０
エ ３３
解答 エ
解説 雨の２日後が晴れである確率は以下の３つの可能性の和であらわすことができます。

雨⇒晴れ⇒晴れ：３０％×４０％＝１２％
雨⇒曇り⇒晴れ：５０％×３０％＝１５％
雨⇒雨⇒晴れ：２０％×３０％＝６％

つまり、１２＋１５＋６＝３３％であるといえます。
問４ 四つの整数を引数とする関数ｄ（Ｘ1,Ｙ1,Ｘ2,Ｙ2）を、次のように定義する。

ｄ（Ｘ1,Ｙ1,Ｘ2,Ｙ2）＝｜Ｘ1−Ｘ2｜＋｜Ｙ1−Ｙ2｜

この関数は、２点（Ｘ1,Ｙ1）と（Ｘ2,Ｙ2）との間の２次元正方格子上の最短経路長を求めるものである。その性質に関する記述のうち、適切なものはどれか。


画像（問4）を表示できません
ア ｄ（０,０,Ｘ2,Ｙ2）≦１を満たす整数の組は（Ｘ2,Ｙ2）は、全部で四つある。
イ ｄ（２Ｘ1,２Ｙ1,２Ｘ2,２Ｙ2）＝４ｄ（Ｘ1,Ｙ1,Ｘ2,Ｙ2）である。
ウ ｄ（Ｘ1,Ｙ1,Ｘ2,Ｙ2）＝０ならば、Ｘ1＝Ｙ1＝Ｘ2＝Ｙ2である。
エ ｄ（Ｘ1,Ｙ1,Ｘ2,Ｙ2）＝ｄ（Ｘ2,Ｙ2,Ｘ1,Ｙ1）である。
解答 エ
解説 それぞれの選択肢を順に見ていきます。

選択肢ア：距離が１のものが(1，0)、(0，1)、(-1，0)、(0，-1)の四つと距離が０（同じ座標）のもの(0，0)が１つあるので、合計で五つとなります。
選択肢イ：反例として、(0,0,1,1)として考えます。(2*0,2*0,2*1,2*1)＝(0,0,2,2)＝４、4*(0,0,1,1)＝４×２＝８なので、成立しません。
選択肢ウ：距離は｜Ｘ1−Ｘ2｜＋｜Ｙ1−Ｙ2｜なので、Ｘ1−Ｘ2かつＹ1−Ｙ2ならば、距離が０となります。
選択肢エ：｜Ｘ1−Ｘ2｜＋｜Ｙ1−Ｙ2｜＝｜Ｙ1−Ｙ2｜＋｜Ｘ1−Ｘ2｜なので、成立します。

このような距離をマンハッタン距離といいます。
問５ Ａ，Ｂ，Ｃ，Ｄを論理変数とするとき、次のカルノー図と等価な論理式はどれか。ここで、・は論理積、＋は論理和、ＸはＸの否定を表す。

画像（問5）を表示できません
ア Ａ・Ｂ・Ｄ＋Ｂ・Ｄ
イ Ａ・Ｂ・Ｃ・Ｄ＋Ｂ・Ｄ
ウ Ａ・Ｂ・Ｄ＋Ｂ・Ｄ
エ Ａ・Ｂ・Ｃ・Ｄ＋Ｂ・Ｄ
解答 ウ
解説 カルノー図とは、多変数の論理式を簡単化するのに用いられる図で、変数が多くなるとベン図では表現しにくくなり、カルノー図が用いられることが多いです。

例として、ＡＢＣ＋ＡＢＣ＋ＡＢＣ＋ＡＢＣが与えられたとします。真を１、偽を０に対応させると以下のようになります。

カルノー図を表示できません

そこで、隣り合うもの同士をまとめると、緑の部分がＡＣ、青の部分がＢＣ、赤の部分がＡＢとなります。

よって、ＡＣ＋ＢＣ＋ＡＢとなり、元の式の簡約化ができました。

それでは、問題のカルノー図を考えます。以下のように色分けをします。端同士がつながっていることや、グループ化は２の倍数個で行われることに注意してください。

5ansを表示できません

赤い線の部分が、Ｂ・Ｄ。青い部分がＡ・Ｂ・Ｄとなり、これを＋でつないだものが等しい論理式となります。
問６ 図に示す論理回路と等価な真理値表はどれか。

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


画像（問6）を表示できません
画像（問6ans）を表示できません
解答 ウ
解説 回路の出力を順に追いかけていくと、以下のようになります。

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

ＡとＢが同じ場合（０，０と１，１）に出力される回路となっているので、選択肢ウの真理値表が対応します。
問７ 図は、偶数個の１を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。ａ，ｂの正しい組み合わせはどれか。

画像（問7）を表示できません
画像（問7ans）を表示できません
解答 ウ
解説 １の個数が偶数と奇数を調べています。偶数と奇数は１が来たときに入れ替わるので、ａは１が入ります。０のときは偶数、奇数は変わらないので、ｂには０が入ります。
問８ あるプログラム言語において、識別子（identifier）は、先頭が英字で始まり、それ以降に任意個の英数字が続く文字列である。これをＢＮＦで定義したとき、ａに入るものはどれか。

画像（問8）を表示できません
ア ＜letter＞｜＜digit＞｜＜identifier＞＜letter＞｜＜identifier＞＜digit＞
イ ＜letter＞｜＜digit＞｜＜letter＞＜identifier＞｜＜identifier＞＜digit＞
ウ ＜letter＞｜＜identifier＞＜digit＞
エ ＜letter＞｜＜identifier＞＜digit＞｜＜identifier＞＜letter＞
解答 エ
解説 ＢＮＦ（Backus Naur Form）とは文脈自由言語を定義する言語で、正規表現などを記述するのに用いられています。

＜Ａ＞：＝＜ａ＞＜ｂ＞の場合は、Ａはａｂをそれぞれを置き換えるという意味です。
＜Ｂ＞：＝＜ｃ＞｜＜ｄ＞の場合は、ＢはＡ又はｂで置き換えるという意味です。
＜Ｃ＞：＝＜Ｃ＞＜ｅ＞の用に、元の記号がある場合は、再帰的な表現となります。

まず、選択肢ア、イは、｜＜ｄｉｇｉｔ＞｜があるので、先頭に数字が来る可能性があります。
選択肢ウとエの違いは、｜＜identifier＞＜leter＞｜があるかないかですが、これがないと、最後が文字列で終わるものを作れないので必要です。
よって、選択肢ウでは不十分であり、選択肢エが正解となります。
問９ すべての葉が同じ深さであり、かつ葉以外のすべての節点が二つの子をもつ要素数ｎの完全２分木がある。どの部分木をとっても左の子孫は親より小さく、右の子孫は親より大きいという関係が保たれている。２分木で探索する場合、ある要素を探索するときの最大比較回数のオーダはどれか。
ア ｌｏｇ2ｎ
イ ｎｌｏｇ2ｎ
ウ ｎ
エ ｎ2
解答 ア
解説 まず、左図で木についてまとめます。そして、完全２分木とは右図のような特殊な木で、２分探索などに用いることができます。

木を表示できません

２分木で大小関係が決まっているということは、１回の比較で、右半分か左半分のどちらかに絞り込むことができるということです。つまり、ｎ回の比較で２n個を調べることができます。つまり、ｎ個検索対象を調べる場合には、ｌｏｇ2ｎ回の最大で比較が行われることになります。（検索している値が葉でない場合はもっと早く終了します。）
問１０ 配列Ａ[１],Ａ[２], ・・・ , Ａ[ｎ]で、Ａ[１]を根とし、Ａ[ｉ]の左の子をＡ[２ｉ]、右の子をＡ[２ｉ＋１]とみなすことによって、２分木を表現する。このとき、配列を先頭から順に調べていくことは、２分木の探索のどれに当たるか。
ア 行きがけ順（先行順）深さ優先探索
イ 帰りがけ順（後行順）深さ優先探索
ウ 通りがけ順（中間順）深さ優先探索
エ 幅優先探索
解答 エ
解説 木と配列の関係をまとめると以下のようになります。

木と配列を表示できません

つまりこれは、１段目をさがし、２段目をさがし、３段目をさがし・・・となるので、幅優先探索となります。
問１１ ｎ個のデータを整列するとき、比較回数が最悪の場合でＯ（ｎ2）、最良の場合でＯ（ｎ）となるものはどれか。
ア クイックソート
イ 単純選択法
ウ 単純挿入法
エ ヒープソート
解答 ウ
解説 まず、代表的なソート法を下にまとめます。

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

つぎに、選択肢のソート法のオーダーについて考えます。
選択肢ア：最悪の場合はＯ（ｎ2）、最良の場合はＯ（ｎｌｏｇ2ｎ）です。
選択肢イ：常に、２重ループで比較をしていくのでＯ（ｎ2）です。
選択肢ウ：最悪の場合はＯ（ｎ2）、最良（ソートされている状態）の場合はＯ（ｎ）です。
選択肢エ：ｎ個のデータに対して、ヒープの再構築Ｏ（ｌｏｇ2ｎ）を行うので、Ｏ（ｎｌｏｇ2ｎ）です。
問１２ ２整数Ｘ、Ｙをキーとするデータを、ハッシュ関数ｈ（Ｘ，Ｙ）を使って、要素数２５６の１次元配列に格納する。Ｘは値１〜２５６を一様にとり、Ｙは値１〜１６を一様にとる。ハッシュ関数として最も不適切なものはどれか。ここでＮ＝２５６であり、Ａ ｍｏｄ ＢはＡをＢで割った剰余を表す。
ア Ｘ ｍｏｄ Ｎ
イ Ｙ ｍｏｄ Ｎ
ウ （Ｘ＋Ｙ） ｍｏｄ Ｎ
エ （Ｘ×Ｙ） ｍｏｄ Ｎ
解答 イ
解説 まず、実際に値を入れて計算してみたハッシュの例を下に示します。

ハッシュ

ハッシュ関数は、できる限り値を一様に生成する性質がもとめられます。

選択肢ア：１〜２５６が０〜２５５になります。
選択肢イ：１〜１６が１〜１６になります。
選択肢ウ：２から２７２が０〜２５５になります。
選択肢エ：１〜４０９６が０〜２５５になります。

よって、選択肢イが生成される値の範囲が最も狭く、不適切であるといえます。
問１３ 配列上に不規則に並んだ多数のデータの中から、特定のデータを探すのに適したアルゴリズムはどれか。
ア ２分探索法
イ 線形探索法
ウ ハッシュ法
エ モンテカルロ法
解答 イ
解説 それぞれの手法を以下にまとめます。

２分探索法：昇順または降順にソートされたデータ列に対して、中央値と比較しながら範囲を半分ずつにしていく手法です。
線形探索法：データを１つずつ順番に探していく方法です。
ハッシュ法：ハッシュ関数を使って、データの格納場所を決める方法です。
モンテカルロ法：乱数を利用して、シミュレーションなどを行う手法です。
問１４ 非負の整数ｘに対して、次のとおりに定義された手続きＦ（ｘ）がある。Ｆ（１０）で印刷される結果はどれか。ここで、ｐ ｄｉｖ ｑはｐをｑで割った商の整数部分、ｐ ｍｏｄ ｑはｐをｑで割った剰余、ｐｒｉｎｔ（ｐ）はｐの値を印刷することを表す。印刷は、左から右に行う。

画像（問14）を表示できません
ア ０１２
イ １０
ウ １２
エ ２１
解答 ウ
解説 順番に追いかけていきます。

１：Ｆ（１０）が実行されます。
２：Ｆ（１０）の中のＦ（１０ ｄｉｖ ８）＝Ｆ（１）が実行されます。
３：Ｆ（１）の中のＦ（１ ｄｉｖ ８）＝Ｆ（０）が実行されます。
４：Ｆ（０）の中において、ｉｆ（ｘ＞０）なので、Ｆ（０）を終了して、Ｆ（１）に戻ります。
５：Ｆ（１）の中のｐｒｉｎｔ（１ ｍｏｄ ８）＝１が出力されます。
６：Ｆ（１）が終了して、Ｆ（１０）に戻ります。
７：Ｆ（１０）の中のｐｒｉｎｔ（１０ ｍｏｄ ８）＝２が出力されます。

よって、１２が出力されます。
問１５ 処理１と処理２が交互に繰り返し実行される流れ図はどれか。ここで、二重線は並列処理の同期を表す。
画像（問15ans）を表示できません
解答 イ
解説 それぞれの選択肢を見ていきます。

選択肢ア：左側の一番上に処理が来ないので、処理が途中で止まってしまいます。
選択肢イ：互いが同期線に囲まれているので、確実に交互に実行されます。
選択肢ウ：同期の後、処理１と処理２のどちらが先に実行されるかわからないので、交互に実行される保証はありません。
選択肢エ：同期の後、処理１と処理２のどちらが先に実行されるかわからないので、交互に実行される保証はありません。
問１６ すべての命令が５サイクルで完了するように設計された、パイプライン制御のコンピュータがある。２０命令を実行するのに何サイクル必要となるか。ここで、すべての命令は途中で停止することなく実行できるものとする。
ア ２０
イ ２１
ウ ２４
エ ２５
解答 ウ
解説 パイプラインとは、下の図のように命令の段階を少しずつずらして多重化する方式です。

パイプラインを表示できません

１つめの命令は、５クロックで終了します。２つめの命令は、６クロック目で終了します。３つめの命令は、７クロック目で終了します。よって、Ｎ命令は５＋（Ｎ−１）クロックで終了します。なので５＋１９＝２４クロックで２０命令が終了するといえます。
問１７ 表に示す命令ミックスによるコンピュータの処理性能は、約何ＭＩＰＳか。

画像（問17）を表示できません
ア ９
イ ３０
ウ ３３
エ １１０
解答 ウ
解説 まず、ＭＩＰＳ（million instructions per second）とは、１秒間に何百万個の命令が実行できるかを表しています。次に、１命令の平均実行時間を求めると１０×０．５＋５０×０．３＋５０×０．２＝５＋１５＋１０＝３０ナノ秒となります。１つの命令が３０ナノ秒なので、１秒間に実行できる命令の数は、１／３０ナノ秒＝１／（３０×１０-9）≒３３×１０6なので、約３３ＭＩＰＳであるといえます。
問１８ キャッシュメモリのアクセス時間が１０ナノ秒、主記憶のアクセス時間が７０ナノ秒、キャッシュメモリのヒット率が９０％のとき、実効アクセス時間は何ナノ秒か。
ア ９
イ １６
ウ ４０
エ ６４
解答 イ
解説 キャッシュメモリは、主記憶とＣＰＵのレジスタの速度の差を埋めるために用いられるものです。キャッシュメモリを用いた場合の主記憶の実効アクセス時間は、キャッシュメモリのアクセス時間×ヒット率＋主記憶のアクセス速度×（１−ヒット率）となります。

よって、１０×０．９＋７０＋０．１＝９＋７＝１６ナノ秒となります。
問１９ メモリインタリーブを説明したものはどれか。
ア 主記憶と外部記憶を一元的にアドレス付けし、事実上無制限のメモリ空間を提供する方式である。
イ 主記憶と磁気ディスク装置のアクセス速度の差を補うために、補助的な記憶装置を双方の間に置く方式である。
ウ 主記憶と入出力装置との間でＣＰＵとは独立にデータ転送を行うことを可能とした方式である。
エ 主記憶を複数の領域に分け、連続したメモリ領域へのアクセスを高速化する方式である。
解答 エ
解説 メモリインタリーブとは、複数のバンクと呼ばれる単位に分けておくことで、高速にアクセスできます。アクセス幅が１の場合は３語分、アクセス幅が２の場合は６語分に同時にアクセスできます。

メモリインタリーブ

選択肢アは、仮想記憶の説明です。
選択肢イは、ディスクキャッシュの説明です。
選択肢ウは、ＤＭＡ（Direct Memory Access）の説明です。
問２０ データを分散して複数の磁気ディスクに書き込むことによって、データ入出力の高速化を図る方式はどれか。
ア ストライピング
イ スワッピング
ウ ディスクキャッシュ
エ ミラーリング
解答 ア
解説 それぞれの用語を以下にまとめます。

ストライピング：ＲＡＩＤ０に相当し、複数のＨＤＤに分散してデータを書き込むもの
スワッピング：仮想記憶において実主記憶と仮想記憶の間で行う入れ替えのこと
ディスクキャッシュ：主記憶とＨＤＤとの間におかれ、速度の差を埋めるために用いられるメモリ
ミラーリング：ＲＡＩＤ１に相当し、複数のＨＤＤに同じデータを書き込むもの