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

ソフ開

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

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

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

解答 ア

解説 散布図とは、以下のような図で、最小２乗法などによって直線を求めたものを回帰直線と呼びます。この傾きを相関係数といい、１に近ければ正の相関。−１に近ければ負の相関といいます。

問３ 任意のオペランドに対するブール演算Ａの結果とブール演算Ｂの結果が互いに否定の関係にあるとき、ＡはＢの（又は、ＢはＡの）相補演算であるという。排他的論理和の相補演算はどれか。

解答 ア

解説 排他的論理和（ＸＯＲ）とは、どちらかが１であるとき１になるような演算をいいます（不一致回路ともいいます）。以下に真理値表を示します。 A B A ＸＯＲ B 0 0 0 0 1 1 1 0 1 1 1 0 これを否定するということは、以下のような真理値表になります。 A B not(A ＸＯＲ B) 0 0 1 0 1 0 1 0 0 1 1 1 つまりこれは、Ａ＝Ｂのときに真になるので、等価演算であるといえます。

問５ 論理式Ｘ＝Ａ・Ｂ＋Ａ・Ｂ＋Ａ・Ｂ＋Ａ・Ｂ

解答 イ

解説 Ａ・Ｂ＋Ａ・Ｂは、Ａ（Ｂ＋Ｂ）＝Ａとすることができます。同様に、Ａ・Ｂ＋Ａ・Ｂは、（Ａ・Ａ）・Ｂとすることができます。 Ａ＋Ｂはド・モルガンの定理によりＡ・Ｂとなり、これは選択肢イのＮＡＮＤ回路の論理式となります。 式の変形が分からない場合は真理値表を作成し、代入しながら考えるのもよいと思います。

問７ 次の表は、入力信号の集合が｛０，１｝、状態集合が｛ａ，ｂ，ｃ，ｄ｝である有限オートマトンの状態遷移表である。長さ３以上の任意のビット列を左から（上位ビットから）順に読み込んで最後が１１０で終わっているものを受理するには、どの状態を受理状態とみればよいか。

ア ａ イ ｂ ウ ｃ エ ｄ

解答 ウ

解説 最後が１１０で終わっているものを受理するということは、１１０の前に何らかのデータがあり、いずれかの状態になっているが、１１０を入力することでかならず同じ状態に収束するという意味です。つまり、すべての状態で１１０を入力してどれに収束するかを考えます。 ａ：ａ→ｂ→ｄ→ｃ ｂ：ｂ→ｄ→ｄ→ｃ ｃ：ｃ→ｂ→ｄ→ｃ ｄ：ｄ→ｄ→ｄ→ｃ つまり、どんな状態からでも最後に１１０が付けば、状態ｃになることから、ｃを受理状態をすればよいことが分かります。

問９ 葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、深さとは根から葉に至るまでの辺の数を表す。

ア 木の深さがｎならば、葉の数は２n-1である。 イ 節点の数がｎならば、深さはｌｏｇ2ｎである。 ウ 葉の数がｎならば、葉以外の節点の数はｎ−１である。 エ 辺の数がｎならば、節点の数もｎである。

解答 ウ

解説 まず、木というデータ構造を以下に示します。 実際に代入して求めてもよいのですが、以下のような性質があります。 �@木の深さがｎならば、葉の数は２n �A節点の数がｎならば、深さはｌｏｇn+1−１ �B葉がｎならば、葉以外の節点の数はｎ−１

問１０ ヒープソートの説明として、適切なものはどれか。

ア ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が１になるまでこれを繰り返す。 イ 中間的な基準値を決めて、それよりも大きな値を集めた区分と、小さな値を集めた区分に要素を振り分ける。次に、それぞれの区分の中で同様な操作を繰り返す。 ウ 隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。 エ 未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

解答 エ

解説 まず、選択肢のソート法をまとめます。 選択肢ア：シェルソート 選択肢イ：クイックソート 選択肢ウ：バブルソート 選択肢エ：ヒープソート 次に、ヒープとは親より子の方が値が大きい（または小さい）ように作られた木のことで、これを用いてソートを行うのがヒープソートです。ヒープは通常以下のように、配列と対応付けられて利用されます。

問１１ 昇順に整列されたｎ個のデータが格納されている配列Ａがある。流れ図は、配列Ａからｘを２分探索法を用いて探し出す処理を表している。ａ、ｂに入る操作の正しい組合せはどれか。ここで、除算の結果は小数点以下が切り捨てられる。

解答 ウ

解説 問題のアルゴリズムは、２分探索です。 ２分探索とは、ソートされたデータに対して検索をする手法で、中央値と検索値を比較することで、範囲を徐々に半分にしていく手法です。よって 中央値＞検索値だった場合は、下半分にあるので、上限＝中央値の下のインデックス 中央値＜検索値だった場合は、上半分にあるので、上限＝中央値の上のインデックス として、再度中央値を再計算するということを繰り返します。 これにより、探索範囲を半分ずつにしていくことができlog2Nで探索ができます。 前提条件のソート済みという利点を活用しています。

問１２ ２整数Ｘ、Ｙをキーとするデータを、ハッシュ関数ｈ（Ｘ、Ｙ）を使って要素数２５６の１次元配列に格納する。Ｘは１〜２５６、Ｙは１〜１６の値を一様にとる。ハッシュ関数として最も不適切なものはどれか。ここで、Ｎ＝２５６であり、Ａ ｍｏｄ ＢはＡ÷Ｂの余りを表す。

ア Ｘ ｍｏｄ Ｎ イ Ｙ ｍｏｄ Ｎ ウ （Ｘ＋Ｙ） ｍｏｄ Ｎ エ （Ｘ×Ｙ） ｍｏｄ Ｎ

解答 イ

解説 ハッシュ関数とは、特定の値(キー)から別の代表値(ハッシュ値)を変換する関数をいいます。ハッシュ関数の概念図をいかにまとめます。 一般的にハッシュ関数が備えるべき性質はたくさんありますが、ここでは、一様性とハッシュ値の取りえる範囲について問われています。 一様性とは、できるかぎりハッシュ値が重ならない（シノニムが発生しない）ようになる性質です。理想的には、Ｎ個の要素があれば、それぞれが１／Ｎになることが望ましいといえます。 これを基準に選択肢の発生確率を考えます。 選択肢ア：１−２５６ ｍｏｄ ２５６ ＝＞０から２５５が一様 選択肢イ：１−１６ ｍｏｄ ２５６ ＝＞０から１５が一様 選択肢ウ：２−２７２ ｍｏｄ ２５６ ＝＞０から２５５だが偏りがある。 選択肢エ：１−４０９６ ｍｏｄ ２５６ ＝＞０から２５５で一様 ここでは、範囲が極端に狭い選択肢イが不適切であるといえます。

問１４ 次の流れ図を実行したとき、手続が終了するまでに何回の比較を行うか。

ア ９９ イ １００ ウ １０１ エ １０２

解答 エ

解説 まず、値をトレースしながらどのようなことをしているアルゴリズムか調べてみます。 １回目：ｘ＝０（ｙ＝０） ２回目：ｘ＝０（ｙ＝１） ３回目：ｘ＝１（ｙ＝２） ４回目：ｘ＝３（ｙ＝３） ５回目：ｘ＝６（ｙ＝４） つまり、１＋２＋３＋・・・＋ｎ ＞ ５０００となるｎを探していることが予想できます。もちろん１〜１００までの合計が５０５０であることを知っていれば比較的容易ですが、今回は１〜ｎまでの合計の求め方から考えてみましょう。 ４までの和を例に考えます。まず、Ｓを二つ準備して、以下のように２Ｓを計算します。 Ｓ＝１＋２＋３＋４ Ｓ＝４＋３＋２＋１ −−−−−−−−− ２Ｓ＝５＋５＋５＋５ ５とは（１＋４）＝ａ1＋ａnとみることができます。 ５の個数４はｎと一致します。 つまり、２Ｓ＝ｎ（ａ1＋ａn）と表現できるので、Ｓ＝ｎ（ａ1＋ａn）／２となります。 ｎ＝１００とすると、Ｓ＝１００（１＋１００）／２＝５０５０が計算できます。 ２回目が０なので、１０２回目が５０５０となります。

問１５ 次の流れ図のうちで、処理１と処理２が交互に繰り返し実行されるものはどれか。ここで、二重線は並列処理の同期を表す。

解答 イ

解説 ひとつずつ検証していきます。 選択肢ア：左側の処理が一番上の同期線まで戻らないので、処理が止まってしまいます。 選択肢イ：処理１と処理２がそれぞれ同期線に囲まれているので、確実に交互に処理が行われます。 選択肢ウ：処理１を行った後に、同期線を超え、右側が処理２を行う前に処理１が実行できてしまうので間違いです。 選択肢エ：同時に処理１と処理２の上にもどるので、「処理１→処理２」と「処理２→処理１」が繰り返されます。

問１６ 同一メモリ上で転送するとき、転送元の開始アドレス、転送先の開始アドレス、方向フラグ及び転送語数をパラメタとして指定することでブロック転送が行えるＣＰＵがある。図のようにアドレス１００１から１００４の内容をアドレス１００３から１００６に転送する場合、パラメタとして適切なものはどれか。ここで、転送は開始アドレスから１語ずつ行われ、方向フラグに０を指定するとアドレスの昇順に、１を指定するとアドレスの降順に転送を行うものとする。

解答 エ

解説 まず、昇順にコピーするか降順にコピーするかの２種類に矛盾する選択肢を除きます。 選択肢ア：１００１から１００４に向かってフラグ０（昇順）でコピーするので矛盾はありません。 選択肢イ：１００１から１００４に向かってフラグ１（降順）でコピーするので１００１から９９８をコピーしてしまいます。 選択肢ウ：１００４から１００１に向かってフラグ０（昇順）でコピーするので１００４から１００７をコピーしてまいます。 選択肢エ：１００４から１００１に向かってフラグ１（降順）でコピーするので矛盾はありません。 つぎに、転送元と転送先のアドレスを考えます。 今回転送先のアドレスが、一部転送元とかぶっています。つまり、正しくコピーをしないと内容を壊してしまいます。 選択肢ア：１００１のデータが１００３に上書きされるので、１００３のデータをコピーするのに正しいデータがコピーできません。 選択肢エ：１００４のデータを１００６にコピーするので、ほかのデータを壊すことなく正しくコピーできます。

問１９ 主記憶装置の高速化の技法として、主記憶を幾つかのアクセス単位に分割し、各アクセス単位をできるだけ並行動作させることによって、実効アクセス時間を短縮する方法を何というか。

ア 仮想記憶 イ キャッシュメモリ方式 ウ ダイレクトメモリアクセス エ メモリインタリーブ

解答 エ

解説 メモリインタリーブとは、複数のバンクと呼ばれる単位に分けておくことで、高速にアクセスできます。アクセス幅が１の場合は３語分、アクセス幅が２の場合は６語分に同時にアクセスできます。以下にイメージ図を示します。 選択肢アの仮想記憶は、ハードディスクの一部を主記憶のように使うことで、主記憶の見かけ上の容量を増やす技術です。 選択肢イのキャッシュメモリ方式は、キャッシュメモリを主記憶とレジスタの間に搭載し、速度の差を埋める技術やそのアクセス方式をいいます。 選択肢ウのダイレクトメモリアクセス方式（ＤＭＡ）は、ＣＰＵを介さずに機器同士が直接データをやり取りする方式のことです。