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

ソフ開

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

問２ 数値を図に示す１６ビットの浮動小数点形式で表すとき、１０進数０．２５を正規化した表現はどれか。ここでの正規化は、仮数部の最上位けたが０にならないように指数部と仮数部を調節する操作とする。

解答 ウ

解説 まず、０．２５を２進数にすると（０．０１）2となります。仮数部の最上位が０にならないように正規化するので、０．１×２-1と表現することができます。あとは、これを問題の形式にあわせます。 符号：＋なので、０ 指数部：−１なので、４ビットの２の補数で表現します。（１）10＝（０００１）2から補数を求めます。 １の補数：ビット反転＝（１１１０）2 ２の補数：１の補数＋１＝（１１１１）2 仮数部：０．１の小数点以下の部分なので、１ よって、「０」、「１１１１」、「１００００００００００」をつなげた、選択肢ウが正解となります。

問４ 相関係数に関する記述のうち、適切なものはどれか。

ア すべての標本点が正の傾きをもつ直線上にあるときは、相関係数が＋１になる。 イ 変量間の関係が線形のときは、相関係数が０になる。 ウ 変量間の関係が非線形のときは、相関係数が負になる。 エ 無相関のときは、相関係数が−１になる。

解答 ア

解説 相関係数とは、相関図などにおいて、二つの関係の強さを表す係数です。係数は−１から＋１の間で表されます。以下に相関関係をまとめます。

問６ 論理式Ｘ＝Ａ・Ｂ＋Ａ・Ｂ＋Ａ・Ｂと同じ結果が得られる論理回路はどれか。

解答 イ

解説 論理式をみると、Ａ・Ｂ以外のとき出力が行われています。つまり、Ａ・Ｂ（論理積）の否定を出力としていることになるので、否定論理積の出力であるとわかります。

問８ 次の有限オートマトンが受理する文全体を正規表現で表したものはどれか。

ア （０１０）*１ イ （０１｜１０１）* ウ （０｜１０）*１ エ （１｜０１）*

解答 ウ

解説 オートマトンをみると、どんな状態であれ２回連続で１が入力されると、一番右の状態に遷移してしまい、戻れなくなってしまいます。つまり、選択肢イでは、０１→１０１の際に１が２回続いてしまいます。選択肢エでは、１→１の際に１が２回続いてしまうため不適切であることがわかります。 　つぎに、いくつかのパターンをあてはめてすべて記述できるかを考えます。受理できるパターンはたとえば以下のような場合です。 １、０１、００１、０００１、１０１、１０１０１、０１０１、０１００００１ 選択肢アでは、０１、００１などを作ることができないので不適切となります。 選択肢ウは、（０｜１０）の部分を実行すると初期状態へ戻ってくることができ、最後の１で受理状態へ移動するので正しいといえます。

問９ Ａ，Ｂ，Ｃの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを一回ずつ行うことができる場合、データの出力順序は何通りあるか。

ア ３ イ ４ ウ ５ エ ６

解答 ウ

解説 まず、Ａ，Ｂ，Ｃのすべての組み合わせは以下の６通りです。これについて順番に出力できるか考えます。 Ａ，Ｂ，Ｃ：Ａを出力、Ｂを出力、Ｃを出力 → 可能 Ａ，Ｃ，Ｂ：Ａを出力、Ｂをスタックに積む、Ｃを出力、Ｂを取り出す → 可能 Ｂ，Ａ，Ｃ：Ａをスタックに積む、Ｂを出力、Ａを取り出す、Ｃを出力 → 可能 Ｂ，Ｃ，Ａ：Ａをスタックに積む、Ｂを出力、Ｃを出力、Ａを取り出す → 可能 Ｃ，Ａ，Ｂ：Ａをスタックに積む、Ｂをスタックに積む、Ｃを出力、Ａを先に出力できない → 不可能 Ｃ，Ｂ，Ａ：Ａをスタックに積む、Ｂをスタックに積む、Ｃを出力、Ｂを取り出す、Ａを取り出す → 可能 よって、５通りが可能であるといえます。

問１１ 探索表の構成法を例とともにａ〜ｃに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

解答 ア

解説 まず、３つの探索法についてまとめます。データ量をｎとしたときのオーダ（検索時間）もあわせてまとめます。 ２分探索：ソートされているデータに対して、中間値と目的とを比較することで、大きいグループと小さいグループに分け、１回の検索で探索範囲を半分にしていく。オーダはｌｏｇ2ｎ 線形探索：上から一つずつ比較していく方法。オーダはｎ ハッシュ検索：ハッシュ関数を使って、格納場所を決める方法。ハッシュ値が同じになる衝突（シノニム）などがなければ、１度で検索場所が決まります。オーダは１ それでは、それぞれの表に適した検索法を考えます。 表ａ：コードが順番にならんでいる（ソートされている）ので、線形探索よりも２分探索のほうが高速に検索ができるので、２分探索を利用します。 表ｂ：コードに規則性がないが、使用頻度順にならんでいるということは、上にあるものほど発見しやすいので、線形探索を利用します。 表ｃ：ハッシュにより場所を決めているので、同じ関数を利用して求めるのが一番よいので、ハッシュ表探索を利用します。

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

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

解答 イ

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

問１３ 図の２分木を深さ優先の先行順で探索を行ったときの探索順はどれか。ここで、図中の数字はノードの番号を表す。

ア １，２，３，４，５，６ イ １，２，４，５，３，６ ウ ４，２，５，１，３，６ エ ４，５，２，６，３，１

解答 イ

解説 木構造を走査する代表的な方法を主にまとめます。 １．行きがけ順（深さ優先）：根を調べる → 左の部分木を走査する → 右の部分木を調べる ２．通りがけ順：左の部分木を走査する → 根を調べる → 右の部分木を調べる ３．帰りがけ順：左の部分木を走査する → 右の部分木を調べる → 根を調べる ４．幅優先：根を調べる → 根の子を調べる → その子を調べる・・・ 今回は、深さ優先方式なので、以下のようになります。 １．まず根である「１」を調べる ２．左の部分木に移り、根である「２」を調べる ３．更に、左へ移り、「４」を調べる ４．根（２）にもどり右の子である（５）を調べる ５．根（２）にもどり、さらに親（１）にもどる。そして、右の部分木である「３」を調べる ６．最後に「６」を調べる 図にすると以下のようになります。

問１４ 再帰的に定義された手続きｐｒｏｃでｐｒｏｃ（５）を実行したとき、印字される数字を順番に並べたものはどれか。

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

解答 イ

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

問１５ 次の流れ図は、シフト演算と加算の繰返しによって２進数の乗算を行う手順を表したものである。この流れ図中のａ，ｂの処理の組合せとして、正しいものはどれか。ここで、乗数と被乗数は符号なしの１６ビットで表される。Ｘ，Ｙ，Ｚは３２ビットのレジスタであり、けた送りには論理シフトを用いる。最下位ビットを第０ビットと記す。

解答 ア

解説 シフトされたＹの最下位ビットが１だった場合は、乗算をする必要があり、０だった場合は、何もする必要がありません。また、被乗数Ｘを左に１ビットシフトし、乗数を右に１ビットシフトすることで桁をあわせていきます。 ２３５×３２１を計算するときに、 ５×３２１ ３×３２１０ ２×３２１００のようにしていると考えるとわかりやすいかもしれません。

問１８ 同じ命令セットをもつコンピュータＡとＢがある。それぞれのＣＰＵクロック周期と、あるプログラムを実行したときのＣＰＩ（Cycles Per Instruction）は、表のとおりである。コンピュータＡがこのプログラムを実行したときの処理時間は、コンピュータＢの何倍になるか。

ア １／３２ イ １／２ ウ ２ エ ８

解答 ウ

解説 ＣＰＩとは、その名の通り、１命令あたりに必要なクロック数を表します。 コンピュータＡでは、１命令当たり４クロック必要で、１クロックが１ナノ秒なので、１命令は平均４ナノ秒かかります。 コンピュータＢでは、１命令当たり０．５クロック必要で、１クロックが４ナノ秒なので、１命令は平均２ナノ秒かかります。 よって、よって同じ命令数のプログラムを実行した場合、プログラムＡはプログラムＢの２倍の時間がかかるといえます。

問１９ 図のアーキテクチャのシステムにおいて、ＣＰＵからみた、主記憶とキャッシュメモリを合わせた平均読込み時間を表す式はどれか。ここで、読み込みたいデータがキャッシュメモリに存在しない確率をｒとし、キャッシュメモリ管理に関するオーバヘッドは無視できるものとする。

解答 イ

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