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

このページは

ソフ開

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

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

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

問１	ａを正の整数とし、ｂ＝ａ²とする。ａを２進数で表現するとｎビットであるとき、ｂを２進数で表現すると高々何ビットになるか。

ア	ｎ＋１
イ	２ｎ
ウ	ｎ²
エ	２ⁿ

解答	イ

解説	まず、２桁と３桁で計算してみます。　　１１　×１１　－－ー　　１１　１１　－－－－１００１　　　１１１　　×１１１　　－－－－　　　１１１　　１１１　　１１１　－－－－－１１０００１２進数におけるｎ桁の最大値は、すべてが１の状態なので、２ⁿ－１となります。つまり、積の最大は（２ⁿ－１）²なので、２²ⁿ－２・２ⁿ＋１となり＜２²ⁿなので、高々２ｎ桁になることがわかります。

問２	袋の中に重心の偏った二つのサイコロＡ、Ｂが入っている。Ａは１の目が３／１０の確率で、Ｂは１の目が３／５の確率で出る。袋の中からサイコロを一つ取り出し、振ってみたら１の目が出たという条件の下で、取り出したサイコロがＡである条件付き確率は幾らか。

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

解答	イ

解説	Ａのサイコロで１が出る確率は３／１０。Ｂのサイコロで１がでる確率は３／５＝６／１０。現在１が出たので、Ａ：Ｂ＝３／１０：６／１０の確率つまり、１／３でＡ、２／３でＢであるといえます。

問３	回帰直線に関する記述のうち、適切なものはどれか。

ア	回帰直線のグラフが原点を通ることはない。
イ	相関係数の値が大きいほど、回帰直線の傾きは大きくなる。
ウ	相関係数の値が異なっていても、同一の回帰直線が求められることがある。
エ	相関係数の値が負のときは、回帰直線が求められない。

解答	ウ

解説	回帰直線とは、散布図において、分布するデータとの誤差が最小になるように求める直線で、最小二乗法などによって、求められます。以下に回帰直線の例を示します。また、回帰直線の傾きを相関係数といい、１に近ければ正の相関。－１に近ければ負の相関といいます。以下に散布図の３つの相関を示します。選択肢ア：原点を通る場合もあります。選択肢イ：傾きと相関の強弱は関係ありません。選択肢エ：右下がりの直線が得られます。

問４	平均が６０、標準偏差が１０の正規分布を表すグラフはどれか。

解答	ア

解説	まず、正規分布（あるいはガウス分布）とは、山型で左右対称となるような分布をいいます。選択肢ウ、エは正規分布ではありません。平均とは山の頂点が来る値のことで、標準偏差とは、平均から左右へのばらつきの範囲のことをいいます。

問５	論理式Ｐ、Ｑがいずれも真であるとき、論理式Ｒの真偽にかかわらず真になる式はどれか。ここで、“　”は否定、“∨”は論理和、“∧”は論理積、“→”は含意（“真”→“偽”となるときに限り偽となる演算）を表す。

解答	エ

解説	まず、Ｐ＝真、Ｑ＝真を代入して、各選択肢を簡略化します。選択肢ア：（（真→真）∧（真→真））→（Ｒ→偽）＝真→（Ｒ→偽）選択肢イ：（（真→真）∧（真→偽））→（真→Ｒ）＝（真∧偽）→（真→Ｒ）＝真→（真→Ｒ）選択肢ウ：（（真→偽）∨（真→真））→（Ｒ→偽）＝真→（Ｒ→偽）選択肢エ：（（真→偽）∨（真→偽））→（真→Ｒ）＝偽→（真→Ｒ）偽→○の場合は、どんな状態でも真になるので、選択肢エはＲの値に係らず（真→Ｒの値に係らず）真になるといえます。

問６	信頼性設計技術の中で、誤りを検出した上である程度の訂正まで行いたいと場合に使用する符号として、適切なものはどれか。

ア	巡回冗長符号（ＣＲＣ）
イ	垂直パリティ符号
ウ	水平パリティ符号
エ	ハミング符号

解答	エ

解説

代表的な誤り制御方式を下にまとめます。

奇数パリティ：１（あるいは０）の個数が奇数個になるように、１ビットを付加するもの。
奇数パリティ：１（あるいは０）の個数が偶数個になるように、１ビットを付加するもの。
水平パリティ：転送を２次元の配列とみなしたときに、水平方向へのパリティを付加するもの。垂直パリティと合わせて利用されることが多い。
チェックサム：送信データを数値に対応させ、その合計を計算し付加するもの。
ハミング符号：複数の冗長ビットを付加し２ビットの誤り検出と、１ビットの誤り訂正機能を持つ。
巡回冗長検査（ＣＲＣ）：送信列から生成多項式とよばれる式をつくり、受信側で計算式の余りが０かどうかを調べる。バースト誤り（連続した・固まったあやまり）に強い。

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

ア	ａ
イ	ｂ
ウ	ｃ
エ	ｄ

解答	ウ

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

問８	逆ポーランド表記法で表された式を評価する場合、途中の結果を格納するためのスタックを用意し、式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき、入力が演算子となった。このときに行われる演算はどれか。ここで、演算は中置表記で記述するものとする。

ア	Ａ演算子Ｂ
イ	Ｂ演算子Ａ
ウ	Ｃ演算子Ｄ
エ	Ｄ演算子Ｃ

解答	ウ

解説	スタックは、後入先出法によるデータ構造です。また、逆ポーランド記法とは、スタックを使うことで表現でき、括弧を使わないで計算の順序を指定できるため、コンパイラなどで用いられています。たとえば、（（Ｅ－Ｆ）÷Ｇ）＋（（Ｃ－Ｄ）÷（Ａ＋Ｂ））は、ＥＦ－Ｇ÷ＣＤ－ＡＢ＋÷＋のように表記されます。問題のスタックは、Ｃ、Ｄの順に入力が行われ、演算子が来ているので、『ＣＤ演算子』という状態なので、これを中置記法にすると『Ｃ演算子Ｄ』となります。

問９	配列内に構成されたヒープとして適切なものはどれか。

解答	イ

解説	ヒープとは、木構造において『親の値』≦『子の値』（あるいは逆）になっているものを言います。また、配列との対応は幅優先順位で格納するので、親をｉとすると、左の子は２ｉ、右の子は２ｉ＋１となります。まず、このデータ構造を以下に図示します。そして、各選択肢の配列を木構造に再構築したものを以下に示します。選択肢アは、親５に対して、子４なので誤りです。選択肢ウは、親８に対して、子６なので誤りです。選択肢エは、親６に対して、子５なので誤りです。

問１０	データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで、図中のデータ列中の縦の区切り線は、その左右でデータ列が分割されていることを示す。

ア	クイックソート
イ	シェルソート
ウ	ヒープソート
エ	マージソート

解答	エ

解説

代表尾的なソート法を以下にまとめます。

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

問１１	相異なるｎ個のデータが昇順に整列された表がある。この表をｍ個ごとのブロックに分割し、各ブロックの最後尾のデータだけを線形検索することによって、目的のデータが存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を求める式はどれか。ここで、ｍは十分大きく、ｎはｍの倍数とし、目的のデータは必ず表中に存在するものとする。

ア	ｎ／ｍ
イ	ｎ／２ｍ
ウ	ｍ＋ｎ／ｍ
エ	ｍ／２＋ｎ／２ｍ

解答	エ

解説	まず、内容を整理すると以下のようになります。・全体でｎ個のデータがある。・データはｍ個ごとにブロック化されている。・各ブロックのデータ数はｎ／ｍである。検索はデータは、まずｍ個ごとに大まかに探し、その後見つかったデータのあるブロックを１個ずつ調べる。このことにより、まずｍ個を調べますが、平均なのでｍの半分（ｍ／２）で見つかると予想できます。次に、このブロックを調べますが、平均なのでｎ／ｍの半分（ｎ／２ｍ）で見つかると予想できます。よって、ｍ／２＋ｎ／２ｍとなります。

問１２	ｆａｃｔ（ｎ）は、非負の整数ｎに対してｎの階乗を返す。ｆａｃｔ（ｎ）の再帰的な定義はどれか。

ア	ｉｆｎ＝０ｔｈｅｎｒｅｔｕｒｎ０ｅｌｓｅｒｅｔｕｒｎｎ＊ｆａｃｔ（ｎ－１）
イ	ｉｆｎ＝０ｔｈｅｎｒｅｔｕｒｎ０ｅｌｓｅｒｅｔｕｒｎｎ＊ｆａｃｔ（ｎ＋１）
ウ	ｉｆｎ＝０ｔｈｅｎｒｅｔｕｒｎ１ｅｌｓｅｒｅｔｕｒｎｎ＊ｆａｃｔ（ｎ－１）
エ	ｉｆｎ＝０ｔｈｅｎｒｅｔｕｒｎ１ｅｌｓｅｒｅｔｕｒｎｎ＊ｆａｃｔ（ｎ＋１）

解答	ウ

解説	５の階乗を例に考えます。５の階乗は、５×４の階乗。４の階乗は４×３の階乗のように考えます。（ｎの階乗をｎ！と表記します。）５！＝５×４！４！＝４×３！３！＝３×２！２！＝２×１！１！＝１×０！０！＝１つまり、１ステップは、ｎ×（ｎ－１）！となります。そして、０！は１となります。（０！＝０ではどんな階乗でも０になってしまいます。）これを、プログラムの式になおすと、選択肢ウのようになります。

問１３	次に示すユークリッドの互除法（方法１、方法２）で正の整数ａ，ｂの最大公約数はそれぞれｍとｎのどちらの変数に求まるか。ここで、ｍｍｏｄｎは、ｍをｎで割った余りを表す。

解答	ウ

解説

実際に２４と１６を用いて計算をしていきます。

[方法１]
ａ＝１４，ｂ＝８
ｍ＝１４，ｎ＝８
ｒ＝１４ｍｏｄ８＝６
ｒ＝０でないので、ループに入る
ｍ＝８
ｎ＝６
８ｍｏｄ６＝２
ｒ＝０でないので、ループに入る
ｍ＝６
ｎ＝２
ｒ＝６ｍｏｄ２＝０
ｒ＝０なので、ループにから出る

最大公約数２はｎに求まる

[方法２] ａ＝１４，ｂ＝８
ｍ＝１４，ｎ＝８
ｒ＝１４ｍｏｄ８＝６
ｍ＝８
ｎ＝６
ｒ＝０でないので、ループを続ける
ｒ＝８ｍｏｄ６＝２
ｍ＝６
ｎ＝２
ｒ＝０でないので、ループを続ける
６ｍｏｄ２＝０
ｍ＝２
ｎ＝０
ｒ＝０なので、ループを出る。

最大公約数２はｍに求まる

よって、方法１ではｎ、方法２ではｍに求まります。

問１４	次の流れ図による処理を複数回実行した場合、途中に出現し得る実行順序はどれか。ここで、二重線は、並列処理の同期を表す。

ア	Ｂ → Ａ → Ｂ → Ａ
イ	Ｂ → Ｘ → Ａ → Ｙ
ウ	Ｘ → Ｂ → Ａ → Ｙ
エ	Ｙ → Ｘ → Ｂ → Ａ

解答	イ

解説	一つずつ検証していきます。（便宜上Ａ，側Ｂを左側、Ｘ、Ｙ側を右側といいます。）選択肢ア：初期条件として左側がＢの直前・右側が同期線の直前とすると、Ｂ→同期→Ａ→ＢでＡを処理できません。選択肢イ：初期条件として左側がＢの直前・右側が同期線の直前とすると、Ｂ→同期→Ｘ→Ａ→Ｙで処理ができます。選択肢ウ：初期条件として左側がＢの直前・右側がＹの直前とすると、Ｙ→Ｂ→同期→ＡでＹが処理できません。選択肢エ：初期条件として左側が同期線の直前・右側がＹの直前とすると、Ｙ→Ｘで処理ができません。

問１５	ゲーム理論を使って検討するのに適している業務はどれか。

ア	イベント会場の入場ゲート数の決定
イ	売れ筋商品の要因の分析
ウ	競争者がいる地域での販売戦略の策定
エ	新規開発商品の需要見通しと利益計画の策定

解答	ウ

解説	ゲーム理論とは、数学の分野で定式化された個人や集団が相互に影響を与えていくなかで、目的にどうやってたどり着くかの振る舞いを研究する分野です。選択肢ア：待ち行列モデルを使うのが適しています。選択肢イ：特性要因図を使うのが適しています。選択肢エ：需要の予測は様々な要因があるため、さまざまな手法があります。

問１６	図の論理回路において、Ｓ＝１、Ｒ＝１、Ｘ＝０、Ｙ＝１のとき、Ｓをいったん０にした後、再び１に戻した。この操作を行った後のＸ、Ｙの値はどれか。

ア	Ｘ＝０、Ｙ＝０
イ	Ｘ＝０、Ｙ＝１
ウ	Ｘ＝１、Ｙ＝０
エ	Ｘ＝１、Ｙ＝１

解答	ウ

解説	このように、出力を入力にフィードバックし、一時的に値を保持する論理回路をフリップフロップといい、様々な種類があります。順番に追いかけていきます。初期条件（フィードバック部分を赤で補完します）Ｓを１から０にします。Ｓを０から１に戻します。このようなフィリップフロップをＲＳ型（リセット・セット型）といいます。Ｓ＝Ｒ＝０の場合は前の状態を保持するというのが特徴です。

問１７	パイプラインの性能を向上させるための技術の一つで、分岐条件の結果が決定する前に、分岐先を予測して命令を実行させるものはどれか。

ア	アウトオブオーダ実行
イ	遅延分岐
ウ	投機実行
エ	レジスタリネーミング

解答	ウ

解説	それぞれのアーキテクチャの用語を以下にまとめます。アウトオブオーダ実行：実行可能になったものから実行することによって、後から投入されたものでも先に実行できる。遅延分岐：命令の直後の命令を先に実行し、後から分岐命令を行うこと。投機実行：ループなどは真になるほうが多いため、分岐先を予想して実行を行う。予想が外れた場合は割込みにより修正する。レジスタリネーミング：レジスタの名前を動的に変更することで、並列性や依存性を考慮し、高速化をする技術です。

問１８	複数のデータに対して一つの命令で同じ処理を並列に行うのはどれか。

ア	ＭＩＭＤ
イ	ＭＩＳＤ
ウ	ＳＩＭＤ
エ	ＳＩＳＤ

解答	ウ

解説	これは、フリンの分類と呼ばれる命令とデータの並列性を基にした分類法ですＳＩＳＤ：（単一命令、単一データ）命令にもデータにも並列性のない逐次的なコンピュータＳＩＭＤ：（単一命令、複数データ）ベクトル演算機やＧＰＵ等ＭＩＳＤ：（複数命令、単一データ）命令列が複数あり、それを1 つのデータストリームに適用する形態のコンピュータ。あまり一般的ではないＭＩＭＤ：（複数命令、複数データ）複数のプロセッサが同時並行的にそれぞれ異なるデータを異なる命令で処理するコンピュータ

問１９	キャッシュメモリに関する記述のうち、適切なものはどれか。

ア	キャッシュメモリのアクセス時間が主記憶と同等でも、主記憶の実効アクセス時間は短縮される。
イ	キャッシュメモリの容量と主記憶の実効アクセス時間は、反比例の関係にある。
ウ	キャッシュメモリは、プロセッサ内部のレジスタの代替として使用可能である。
エ	主記憶全体をランダムにアクセスするプログラムでは、キャッシュメモリの効果は小さくなる

解答	エ

解説	キャッシュメモリは、ＣＰＵのレジスタと主記憶の間に存在し、アクセス速度の差を埋めるために用いられます。選択肢ア：アクセス速度の差を埋めるものなので、主記憶と同じくらい遅いのであればアクセス時間の短縮にはなりません。選択肢イ：容量とアクセス速度にはあまり関係はありません。選択肢ウ：キャッシュメモリとレジスタは別物なので、代替利用は不可能です。選択肢エ：キャッシュメモリは、ある程度まとめてロードするので、局所性が強いほど効果が高くなります。

問２０	ＵＳＢ２．０に関する記述として、適切なものはどれか。

ア	ＰＣと周辺機器を接続するＡＴＡ仕様をシリアル転送方式に変更したもので、磁気ディスクやＣＤ－ＲＯＭなどの接続に採用されているシリアルインタフェースである。
イ	音声や映像などに適したアイソクロナス転送を採用しているほか、ブロードキャスト転送などがあるシリアルインタフェースであり、ＦｉｒｅＷｉｒｅとも呼ばれている。
ウ	周辺機器とＰＣとの間の接続に用いられ、クロスやストレートのケーブルを使ってつなぐシリアルインタフェースである。
エ	データ転送にアイソクロナス、バルク、インタラプトなどの転送プロトコルがあり、拡張機能として周辺機器同士が直接接続できるＯｎ－Ｔｈｅ－ＧＯをサポートしたシリアルインタフェースである。

解答	エ

解説

ＵＳＢ(Universal Serial Bus)は現在最も主流な周辺機器をパソコンに接続するインタフェースの一種です。中でもＵＳＢ２．０というのが最も主流で、従来のＵＳＢ１．１で利用できたロースピードモード、フルスピードモードに、ハイスピードモードを追加したものです。また、転送モードも４つあります。下にまとめます。なお、ＵＳＢ１．１とＵＳＢ２．０は互換性があります。

ロースピードモード（１．５Ｍｂｐｓ）：キーボードやマウスなど
フルスピードモード（１２Ｍｂｐｓ）：スキャナやプリンタなど
ハイスピードモード（４８０Ｍｂｐｓ）：大容量のＨＤＤなど

コントロール転送：デバイスの設定・制御するためのもの
インタラプト転送：一定間隔でデータを転送するためのもの。キーボードやマウスな等に使われる
バルク転送：まとまったデータを一度に転送するためのもの。スキャナ等に使われる
アイソクロナス転送：連続的、周期的なデータ転送するためのもの。ビデオやオーディオ等に使われる。

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

ソフ開

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

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