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



このページは

ソフ開

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

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

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


問１ 基数変換に関する記述のうち、適切なものはどれか。
ア ２進数の有限小数は、１０進数にしても必ず有限小数になる。
イ ８進数の有限小数は、２進数にすると有限小数にならないこともある。
ウ ８進数の有限小数は、１０進数にすると有限小数にならないこともある。
エ １０進数の有限小数は、８進数にしても必ず有限小数になる。
解答 ア
解説 まず、２進数３桁を１桁にまとめたものが８進数で、２進数４桁を１桁にまとめたものが１６進数です。よって、２進数で表現できるものは、必ず８進数、１６進数でも表現できます。逆に８進数、１６進数で表現で表現できるものは、必ず２進数で表現できます。

次に、１０進数との関係を考えます。
２進数を１０進数に変換することを考えると、２-1、２-2・・・２-nのようになっているので、これらの和で表現できます。よって、２進数で表現できることは１０進数で表現できます。

しかし、１０進数の０．３のようなものは、２-1＝０．５と２-2＝０．２５の間にあるので、厳密な表現はできないということがわかります。
問２ けた落ちによる誤差の説明として、適切なものはどれか。
ア 値がほぼ等しい二つの数値の差を求めたとき、有効けた数が減ることによって発生する誤差
イ 指定された有効けた数で演算結果を表すために、切捨て、切上げ、四捨五入などで下位のけたを削除することによって発生する誤差
ウ 絶対値の非常に大きな数値と小さな数値の足し算や引き算を行ったとき、小さい数値が計算結果に反映されないことによって発生する誤差
エ 無限級数で表される数値の計算処理を有限項で打ち切ったことによって発生する誤差
解答 ア
解説 誤差について下にまとめます。

アンダーフロー：演算結果が、扱える数値の最小値を超えることによって生じる誤差
オーバーフロー：演算結果が、扱える数値の最大値を超えることによって生じる誤差
打切り誤差：数表現のけた数に限度があるときに、計算を途中でやめることで起きる誤差
丸め誤差：数表現のけた数に限度があるとき、最小のけたより小さい部分について四捨五入、切上げ又は切捨てを行うことによって生じる誤差
けた落ち：値がほぼ等しい浮動小数点同士の減算において、有効けた数が大幅に減ってしまうことで起きる誤差
情報落ち：浮動小数点の加算において、一方の数値の下位のけたが欠落することで起きる誤差

情報落ちは絶対値の小さいものから計算することで回避できます。
けた落ちは式を変形するなどで回避することができます。
そのほかは、誤差が許容できるほどに大きな計算桁数を準備することで軽減できます。
問３ 関数ｙ＝ｆ（ｘ）上の点（ｘ0，ｆ（ｘ0）における接線とｘ軸との交点のｘ座標をｘ1とする。ｘ0とｘ1の関係式はどれか。ここで、ｆ'（ｘ）はｆ（ｘ）の導関数である。

画像（問3）を表示できません
画像（問3ans）を表示できません
解答 エ
解説 まず、関数ｙ＝ｆ（ｘ0）の地点において、接線の傾きは、導関数であるｆ’（ｘ0）になります。
つまり、直線の方程式ｙ＝ａｘ＋ｂに代入すると、ｙ＝ｆ’（ｘ0）ｘ＋ｂとなります。

この式に（ｆ（ｘ0），ｘ0）を代入すると、ｆ（ｘ0）＝ｆ’（ｘ0）ｘ0＋ｂとなります。
この式に（ｆ（ｘ1），ｘ1）を代入すると、ｆ（ｘ1）＝ｆ’（ｘ0）ｘ1＋ｂとなります。

下の式から上の式を引くとｆ（ｘ1）−ｆ（ｘ0）＝ｆ’（ｘ0））（ｘ1−ｘ0）となります。

このとき、ｆ（ｘ1）はｘ軸との接点なので、ｙ＝０です。つまり、−ｆ（ｘ0）＝ｆ’（ｘ0））（ｘ1−ｘ0）となります。

最後に、ｘ1ついて解くと、ｘ1＝ｘ0−ｆ（ｘ0）／ｆ’（ｘ0）となります。
問４ Ｒａｎｄｏｍ（ｎ）は０以上ｎ未満の整数を一様な確率で返す関数である。整数型の変数Ａ，Ｂ及びＣに対して次の一連の手続を実行したとき、Ｃの値が０になる確率はどれか。

Ａ＝Ｒａｎｄｏｍ（１０）
Ｂ＝Ｒａｎｄｏｍ（１０）
Ｃ＝Ａ−Ｂ
ア １／１００
イ １／２０
ウ １／１０
エ １／５
解答 ウ
解説 Ａ、Ｂがそれぞれ持ちうる値は０〜９です。つまり、１０種類×１０種類＝１００種類が生成可能です。Ｃが０ということは、Ａ＝Ｂなので、０と０、１と１・・・９と９のように１０種類あります。つまり、１０／１００＝１／１０となります。
問５ 図の線上を、点Ｐから点Ｒを通って、点Ｑに至る最短経路は何通りあるか。

画像（問5）を表示できません
ア １６
イ ２４
ウ ３２
エ ６０
解答 エ
解説 Ｐ〜ＲとＲ〜Ｑに分けて考えます。とりうる値は右と上の二つです。

Ｐ〜Ｒの場合は、上に２つ右に２つあるので、この組み合わせを考えると4Ｃ2＝４！／（２！（４−２）！）＝６
Ｒ〜Ｑの場合は、上に２つ右に３つあるので、この組み合わせを考えると5Ｃ2＝５！／（２！（５−２）！）＝１０

よって、６×１０で６０通りとなります。
問６ ７ビットのコードと１ビットのパリティからなる８ビットのデータで発生した誤りに関する記述として、適切なものはどれか。
ア １ビットが誤っているときだけ、誤りが復元できる。
イ 誤りが復元できるかどうかは、不明である。
ウ 誤りを復元することは、不可能である。
エ 奇数個のビットが誤っているときだけ、誤りが復元できる。
解答 ウ
解説 １ビットのパリティでは、誤りの場所を特定することができないので、誤りを復元することはできません。１の個数を偶数や奇数になるように、パリティを調節することで誤りの発見をすることはできます。（ただし同時に複数誤りが発生した場合はできない場合があります）
問７ 次のＢＮＦにおいて非終端記号＜Ａ＞から生成される文字列はどれか。

＜Ｒ0＞：：＝０｜３｜６｜９
＜Ｒ1＞：：＝１｜４｜７
＜Ｒ2＞：：＝２｜５｜８
＜Ａ＞：：＝＜Ｒ0＞｜＜Ａ＞＜Ｒ0＞｜＜Ｂ＞＜Ｒ2＞｜＜Ｃ＞＜Ｒ1＞
＜Ｂ＞：：＝＜Ｒ1＞｜＜Ａ＞＜Ｒ1＞｜＜Ｂ＞＜Ｒ0＞｜＜Ｃ＞＜Ｒ2＞
＜Ｃ＞：：＝＜Ｒ2＞｜＜Ａ＞＜Ｒ2＞｜＜Ｂ＞＜Ｒ1＞｜＜Ｃ＞＜Ｒ0＞
ア １２３
イ １２４
ウ １２７
エ １２８
解答 ア
解説 ＢＮＦ（Backus Naur Form）とは文脈自由言語を定義する言語で、正規表現などを記述するのに用いられています。

実際にそれぞれの値を生成できるかを調べていきます。生成規則を見ると後ろの値から確定させているので、これにあわせて考えます。
選択肢ア：３を作るために＜Ａ＞＜Ｒ0＞にします。２を作るために＜Ｂ＞＜Ｒ2＞＜Ｒ0＞にします。１を作るために＜Ｒ1＞＜Ｒ2＞＜Ｒ2＞とすることで１２３を作れます。
選択肢イ：４を作るために＜Ｃ＞＜Ｒ1＞にします。２を作るために＜Ａ＞＜Ｒ2＞＜Ｒ1＞にします。＜Ａ＞から１をつくることができないので、１２４を作れません。
選択肢ウ：７を作るために＜Ｃ＞＜Ｒ1＞にします。２を作るために＜Ａ＞＜Ｒ2＞＜Ｒ1＞にします。＜Ａ＞から１をつくることができないので、１２７を作れません。
選択肢エ：８を作るために＜Ｂ＞＜Ｒ2＞にします。２を作るために＜Ｃ＞＜Ｒ2＞＜Ｒ2＞にします。＜Ｃ＞から１をつくることができないので、１２８を作れません。

意味から考えることもできます。＜Ｒ0＞、＜Ｒ1＞、＜Ｒ2＞はそれぞれ３で割った余りが０になる集合といえます。再帰的に考えると＜Ａ＞は、３で割った余りが０になるように調節され、＜Ｂ＞は、３で割った余りが１になるように調節され、＜Ｃ＞は、３で割った余りが２になるように調節されています。

つまり、＜Ａ＞から生成できるのは、それぞれの桁を足し合わせて３で割り切れる文字列といえます。（例：１＋２＋３＝６ ６％３＝０なので作れる。１＋２＋４＝７ ７％３＝１なので作れない）
問８ 逆ポーランド表記法で表された式を評価する場合、途中の結果を格納するためのスタックを用意し、式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき、入力が演算子となった。このときに行われる演算はどれか。ここで、演算は中置表記法で記述するものとする。

画像（問8）を表示できません
ア Ａ 演算子 Ｂ
イ Ｂ 演算子 Ａ
ウ Ｃ 演算子 Ｄ
エ Ｄ 演算子 Ｃ
解答 ウ
解説 スタックは、後入先出法によるデータ構造です。また、逆ポーランド記法とは、スタックを使うことで表現でき、括弧を使わないで計算の順序を指定できるため、コンパイラなどで用いられています。たとえば、（（Ｅ−Ｆ）÷Ｇ）＋（（Ｃ−Ｄ）÷（Ａ＋Ｂ））は、ＥＦ−Ｇ÷ＣＤ−ＡＢ＋÷＋のように表記されます。

問題のスタックは、Ｃ、Ｄの順に入力が行われ、演算子が来ているので、『Ｃ Ｄ 演算子』という状態なので、これを中置記法にすると『Ｃ 演算子 Ｄ』となります。
問９ Ｂ木に関する記述として、適切なものはどれか。
ア 階層の深さが同じになるように、ノードの分割と併合を行う。
イ キー値からある関数によって、データの格納位置を決める。
ウ 先頭データから順次アクセスだけが可能である。
エ 登録簿とメンバに分かれ、メンバは順編成ファイルである。
解答 ア
解説 Ｂ木とは、索引部の各ノードのキー値を中心にして、小さい側のレコード数と大きい側のレコード数の比率が、ある範囲内に収まるように動的に再配置しながら格納するものです。

選択肢イは、ハッシュテーブルの説明です。
選択肢ウは、順編成ファイルの説明です。
選択肢エは、区分編成ファイルの説明です。
問１０ 節点の集合｛１，２，・・・，ｎ｝である木を表現するために、大きさｎの整数型配列Ａ[１]，Ａ[２]，・・・，Ａ[ｎ]，を用意して、節点ｉの根の節点をＡ[ｉ]に格納する。節点ｋが根の場合はＡ[ｋ]＝０とする。表に示す配列が表す木の葉の数は、幾つか。

画像（問10）を表示できません
ア １
イ ３
ウ ５
エ ７
解答 ウ
解説 まず、木というデータ構造について下図にまとめます。

木を表示できません

つぎに、配列と木構造の対応を図示すると以下のようになります。

木を表示できません

最後に、問題文のＡ［ｉ］が親を指し、ｉが自分の番号であることを順番に繰り返していくと以下のような図になります。

6aを表示できません

葉は、一番末端にあるデータなので、今回は｛２、４、６、７、８｝の５つとなります。
問１１ 整列済みの列の末尾から比較して、次の要素の挿入位置を決める単純挿入整列法について考える。昇順に整列済みの大きさｎのデータ列を、改めて昇順に整列する処理を行う場合の比較回数のオーダは、どれか。
ア ｎ
イ ｎ2
ウ ｌｏｇ ｎ
エ ｎ ｌｏｇ ｎ
解答 ア
解説 ［１，２，３，４，５］のようなデータで比較回数を考えて見ます。

１はそのまま配列に入れます。[１]
２を末尾のデータと比較して、１＜２のため末尾に入れます。[１，２]
３を末尾のデータと比較して、２＜３のため末尾に入れます。[１，２，３]
４を末尾のデータと比較して、３＜４のため末尾に入れます。[１，２，３，４]
５を末尾のデータと比較して、４＜５のため末尾に入れます。[１，２，３，４，５]

通常の単純挿入整列法はＯ（ｎ2）ですが、すでに整列済みであることと、後ろから比較することが決まっていれば、上のようにｎ回の比較と代入で終わります。
問１２ 従業員番号と氏名の対がｎ件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率をａとする。
ア （ｎ＋１）／２＋ｎａ／２
イ （ｎ＋１）（１−ａ）／２
ウ （ｎ＋１）（１−ａ）／２＋ｎ／２
エ （ｎ＋１）（１−ａ）／２＋ｎａ
解答 エ
解説 まず、表の中にある場合の平均探索回数は（ｎ＋１）／２です。次に表の中にない場合はすべてを調べる必要があるので、ｎ回探索します。今存在しない確率がａなので、存在する確率は１−ａとなります。

つまり、全体としては、（ｎ＋１）／２×（１−ａ）＋ｎ×ａ＝（ｎ＋１）（１−ａ）／２＋ｎａとなります。
問１３ 次の関数ｇ（ｘ）の定義に従ってｇ（４）を再帰的に求めるとき、必要な加算の回数は幾らか。

ｇ（ｘ）＝ｉｆ ｘ＜２ ｔｈｅｎ １ ｅｌｓｅ ｇ（ｘ−１） ＋ ｇ（ｘ−２）
ア ３
イ ４
ウ ５
エ ７
解答 イ
解説 再帰は本来性質を考え、回数を見積もりますが、値が小さいので順番に追いかけていきます。

ｘ＝０から考えていきます
ｇ（０）＝０→加算は０回
ｇ（１）＝１→加算は０回
ｇ（２）＝ｇ（１）＋ｇ（０）→加算は１回
ｇ（３）＝ｇ（２）＋ｇ（１）→加算はｇ（２）が１回とこの関数で１回＝２回
ｇ（４）＝ｇ（３）＋ｇ（２）→加算はｇ（３）が２回とｇ（２）が１回、この関数で１回＝４回、
問１４ 次に示すユークリッドの互除法（方法１、方法２）で、正の整数ａ，ｂの最大公約数は、それぞれｍとｎのどちらの変数に求まるか。ここで、ｍ ｍｏｄ ｎはｍをｎで割った余りを表す。

画像（問14）を表示できません
画像（問14ans）を表示できません
解答 ウ
解説 ｍ ｍｏｄ ｎ＝ｒが０になったときのｎが最大公約数となります。方法１では、ループの最後でｒを計算し、終了条件でｒ＝０を調べているので、ｎに最大公約数が求まります。一方方法２では、ｒを計算した後に、ｎ→ｍ、ｒ→ｎの代入を行い、ｒ＝０を調べています。つまり、最大公約数ｎはｍに移されているため、ｍに最大公約数が求まります。
問１５ 変数ｘの初期値がある正の整数であるとき、次の流れ図で表される手続きを実行したところ、ｘの値はｘの初期値と等しくなり終了した。ｘの初期値として考えられるものは全部で幾つあるか。

画像（問15）を表示できません
ア １
イ ２
ウ ３
エ ４
解答 ウ
解説 まず、このアルゴリズムをみると、入力値ｘを９０より大きくなるまで２倍し続けています。９０より大きくなったら９０を引いて終了するという流れです。
つまり、ｘ＝２n−９０が成立する整数が求めるべき初期値といえます。

ｎ＝０：ｘ＝ｘ−９０となるｘは存在しない。
ｎ＝１：ｘ＝２ｘ−９０となるｘは４５（正しい）
ｎ＝２：ｘ＝４ｘ−９０となるｘは３０（正しい）
ｎ＝３：ｘ＝８ｘ−９０となるｘは約１２．８６
ｎ＝４：ｘ＝１６ｘ−９０となるｘは６（正しい）
ｎ＝５：ｘ＝３２ｘ−９０となるｘは約２．９０
ｎ＝６：ｘ＝６４ｘ−９０となるｘは約１．４３
ｎ＝７：ｘ＝１２８ｘ−９０となるｘは約０．７１
これ以上は、ｎを大きくしてもｘは１より小さいので整数にはならない。

よって、４５、３０、６の３つが初期値と同じになるといえます。
問１６ ＮＡＮＤ素子を用いた次の組合せ回路の出力Ｚを表す式はどれか。ここで、・は論理積、＋は論理和、ＸはＸの否定を表す。

画像（問16）を表示できません
ア Ｘ・Ｙ
イ Ｘ＋Ｙ
ウ Ｘ・Ｙ
エ Ｘ＋Ｙ
解答 イ
解説 ＮＡＮＤに同じ値を入力すると、下にようになり、入力の否定が出力されます。

０，０ → １
１，１ → ０

つまり全体は、ＸとＹのＮＡＮＤであるといえます。
これをド・モルガンの定理をつかって変換すると、Ｘ＋Ｙとなります。
問１７ ＶＬＩＷに関する記述として、適切なものはどれか。
ア 同時に複数の命令が独立して実行され、どの命令が同時に実行されるのかは、ハードウェア制御で動的に決定される。
イ パイプラインの段数を増やすことで、高い周波数での動作を可能とし、処理を高速化する。
ウ 一つの命令語で複数の命令を同時に実行する。
エ 命令を処理するためのフェッチ、デコード、実行などの段階を、それぞれ並列に処理する。
解答 ウ
解説 ＶＬＩＷ（Very Long Instruction Word）は、命令語を長く取り、一つの命令で複数の機能ユニットを同時に制御することによって高速化を図る方式です。

選択肢アは、アウト・オブ・オーダー実行の説明です。
選択肢イは、スーパーパイプラインの説明です。
選択肢エは、スーパースカラ方式の説明です。
問１８ 表のクロック周波数と平均ＣＰＩ（Cycles Per Instruction）の組合せのうち、同一命令数のプログラムを処理するのが最も短いものはどれか。
画像（問18ans）を表示できません
解答 イ
解説 クロック周波数は１秒間に発生できるクロック数を表した値です。平均ＣＲＩは１命令を実行するのに必要な平均クロック数を表した値です。

つまり、１命令の処理に掛かる平均時間は、平均ＣＲＩ／クロック周波数で求めることができます。
選択肢ア：７／２．０ＧＨｚ＝３．５（ナノ秒）
選択肢ア：８／２．５ＧＨｚ＝３．２（ナノ秒）
選択肢ア：１０／３．０ＧＨｚ≒３．３（ナノ秒）
選択肢ア：１２／３．５ＧＨｚ≒３．４（ナノ秒）

よって、選択肢イのケースが最も処理時間が短いといえます。
問１９ キャッシュメモリの書込み制御方式の一つであるライトバック方式の特徴はどれか。
ア キャッシュメモリからデータを追い出すとき、主記憶を更新する必要がない。
イ キャッシュメモリのデータとそれに対応する主記憶のデータとの間で不一致が生じない
ウ データを書き込むとき、キャッシュメモリにあるかどうかにかかわらず、主記憶に書き込む
エ 同一番地に繰り返して書き込む場合は、主記憶へのアクセス回数が少なくて済む。
解答 エ
解説 キャッシュメモリと主記憶のデータの整合性の取り方には、以下の２つの種類があります。

ライトスルー方式：キャッシュメモリと主記憶の両方の書き込む方法です。
ライトバック方式：データがキャッシュメモリから追い出されるときに主記憶に書き込みます。
問２０ 回転速度が５，０００回転／分、平均シーク時間が２０ミリ秒の磁気ディスクがある。この磁気ディスクの１トラック当たりの記憶容量は、１５，０００バイトである。このとき、１ブロックが４，０００バイトのデータを、１ブロック転送するのに必要な平均アクセス時間は何ミリ秒か。
ア ２７．６
イ ２９．２
ウ ３３．６
エ ３５．２
解答 イ
解説 アクセス時間はサーチ時間（平均回転待ち時間）＋シーク時間（平均位置決め時間）＋データ転送時間で求められます。

サーチ時間は、半回転するのにかかる時間です。これは、回転速度５０００回転／分から６０／５０００（秒）＝０．０１２。これは、１回転にかかる時間なので、この半分０．０１２／２＝６ミリ秒となります。
シーク時間は、問題文より２０ミリ秒

データ転送時間は、１トラック（＝１周）あたり１５０００バイトなので、４０００バイトは、４／１５トラックとなります。これに１回転する時間をかけると、４／１５×１２ミリ秒＝３．２ミリ秒

よって、アクセス時間は、６＋２０＋３．２＝２９．２秒となります。