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



このページは

ソフ開

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

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

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


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

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

しかし、１０進数の０．３のようなものは、２-1＝０．５と２-2＝０．２５の間にあるので、厳密な表現はできないということがわかります。
問２ 負の整数を表現する代表的な方法として、次の３種類がある。

ａ １の補数による表現
ｂ ２の補数による表現
ｃ 絶対値に符号を付けた表現（左端ビットが０の場合は正、１の場合は負）

４ビットのパターン１１０１をａ〜ｃの方法で表現したものと解釈したとき、値が小さい順になるように三つの方法を並べたものはどれか。
ア ａ、ｃ、ｂ
イ ｂ、ａ、ｃ
ウ ｂ、ｃ、ａ
エ ｃ、ｂ、ａ
解答 エ
解説 それぞれのを並べてみます。

補数とは、Ａ＋Ｂ＝０となるようなＡとＢの関係です。つまり、２回補数をとると元の値にもどります。

ａ：１１０１のビット反転００１０なので、−２
ｂ：１１０１のビット反転をして１を加えると００１１なので、−３
ｃ：１は負数で１０１は５なので、−５

よって、ｃ、ｂ、ａとなります。
問３ ＸとＹの否定論理積Ｘ ＮＡＮＤ Ｙは、ＮＯＴ（Ｘ ＡＮＤ Ｙ）として定義される。Ｘ ＯＲ ＹをＮＡＮＤだけを使って表した論理式はどれか。
ア （（Ｘ ＮＡＮＤ Ｙ）ＮＡＮＤ Ｘ）ＮＡＮＤ Ｙ
イ （Ｘ ＮＡＮＤ Ｘ）ＮＡＮＤ（Ｙ ＮＡＮＤ Ｙ）
ウ （Ｘ ＮＡＮＤ Ｙ）ＮＡＮＤ（Ｘ ＮＡＮＤ Ｙ）
エ Ｘ ＮＡＮＤ（Ｙ ＮＡＮＤ（Ｘ ＮＡＮＤ Ｙ））
解答 イ
解説 この問題はド・モルガンの定理と呼ばれる以下のような変換法則を利用します。

（Ａ＋Ｂ） ＝ Ａ・Ｂ
（Ａ・Ｂ） ＝ Ａ＋Ｂ

次に、Ａ ＮＡＮＤ Ａのように、同じ入力をＮＡＮＤに入れるとＡの否定を作ることができます。

１．Ｘ ＯＲ Ｙ ＝ （Ｘ ＯＲ Ｙ）の二重否定
２．（Ｘ ＯＲ Ｙ）の二重否定 ＝ Ｘ ＮＡＮＤ Ｙの否定 （ド・モルガンの定理）
よって、（Ｘ ＮＡＮＤ Ｘ）ＮＡＮＤ（Ｙ ＮＡＮＤ Ｙ）はＸ ＯＲ Ｙと等価であることがわかります。

最後に、ＸＯＲやＸＡＮＤはそれだけですべての演算子を作れるため、最小万能演算系と呼ばれます。
問４ 集合Ｓの部分集合ＡとＢがあるとき、Ａ∩Ｂに等しいものはどれか。ここで、Ａ、ＢはそれぞれのＡ，ＢのＳに対する補集合、Ｘ−Ｙは集合Ｘと集合Ｙの差集合を表す。
ア （Ａ∪Ｂ）−（Ａ∩Ｂ）
イ （Ｓ−Ａ）∪（Ｓ−Ｂ）
ウ Ａ−Ｂ
エ Ｓ−（Ａ∩Ｂ）
解答 ウ
解説 まず、差集合とはＡ−Ｂのとき、ＡであってＢでないものということを表します。よって、Ａ∩Ｂと変換できます。これを使って式を変形していきます。

次に、論理命題で重要なド・モルガンの定理をまとめます。
（Ａ＋Ｂ） ＝ Ａ・Ｂ
（Ａ・Ｂ） ＝ Ａ＋Ｂ

選択肢ア：（Ａ∪Ｂ）−（Ａ∩Ｂ）＝ （Ａ∩Ｂ）−（Ａ∩Ｂ）＝（Ａ∩Ｂ）
選択肢イ：（Ｓ−Ａ）∪（Ｓ−Ｂ）＝（Ａ∪Ｂ）＝ （Ａ∩Ｂ）
選択肢ウ：Ａ−Ｂ＝ （Ａ∪Ｂ）＝ （Ａ∪Ｂ）
選択肢エ：Ｓ−（Ａ∩Ｂ）＝（Ａ∩Ｂ）

よって、選択肢ウが正解となります。このような問題は真理値表やベン図を利用するもよいかと思います。
問５ 論理式Ｐ，Ｑがいずれも真のとき、論理式Ｒの真偽にかかわらず真になる式はどれか。ここで、“　”は否定、“∨”は論理和、“∧”は論理積、“→”は合意（真 → 偽となるときに限り結果が偽となる２項ブール演算）を表す。
画像（問5ans）を表示できません
解答 ウ
解説 まず、問題文にも定義されていますが、含意記号を真理値表で以下に示します。

ＰＱＰ→Ｑ
真真真
真偽偽
偽真真
偽偽真


Ｐ，Ｑに真を代入した式を選択肢に当てはめていきます。

選択肢ア：（（真→真）∩（真→真））→Ｒ＝真→Ｒ
Ｒが真ならば、真→真で真。Ｒが偽ならば、真→偽で偽となります。

選択肢イ：（（真→偽）∪（真→真））→（Ｒ→偽）＝（真∪真）→（Ｒ→偽）＝真→（Ｒ→偽）
Ｒが真ならば、真→（真→偽）で偽。Ｒが偽ならば、真→（偽→偽）で真となります。

選択肢ウ：（（真→偽）∪（真→偽））→（真→Ｒ）＝（偽∪偽）→（真→Ｒ）＝偽→（真→Ｒ）
Ｒが真ならば、偽→真で真。Ｒが偽ならば、偽→偽で真となります。

選択肢エ：（（真→真）∩（真→偽））→Ｒ＝（真∩偽）→Ｒ＝真→Ｒ
Ｒが真ならば、真→真で真。Ｒが偽ならば、真→偽で偽となります。

よって、選択肢ウの場合のみＲの真偽が影響しません。
なお、Ａ→Ａのように、常に真になるような論理式を恒真式（トートロジー）といいます。
問６ ７ビットのコードと１ビットのパリティビットからなる８ビットのデータで、データ誤りが発生したときの記述として、適切なものはどれか。
ア １ビットが誤っているときだけ、誤りを復元できる。
イ 誤りを復元することは、不可能である。
ウ 誤りを復元できるかどうかは、不明である。
エ 奇数個のビットが誤っているときだけ、誤りを復元できる。
解答 イ
解説 一般的に、１ビットのパリティを持たせている場合は、１の個数を奇数個や偶数個にあらかじめ決めておきます。

偶数個の例を考えると、１００００００とパリティが１で１００００００１で偶数個となります。しかし、１０１１０００１のように、偶数個誤っている場合には検出ができないという欠点があります。また、誤りがあるかどうかはわかっても訂正（誤りが起こったビットを特定できない）という欠点があります。
問７ 後置表記法（逆ポーランド表記法）では、例えば、式Ｙ＝（Ａ−Ｂ）×ＣをＹＡＢ−Ｃ×＝と表現する。次の式を後置表記法で表現したものはどれか。

Ｙ＝（Ａ＋Ｂ）×（Ｃ−（Ｄ÷Ｅ））
ア ＹＡＢ＋ＣＤＥ÷−×＝
イ ＹＡＢ＋Ｃ−ＤＥ÷×＝
ウ ＹＡＢ＋ＥＤＣ÷−×＝
エ ＹＡＢ＋ＣＤ−Ｅ÷×＝
解答 ア
解説 逆ポーランド記法とは、後置表記法とも呼ばれ、演算子を対象の後ろに記述する手法です。スタックを使うことで実現でき、括弧が不要なのでコンパイラなどで利用されています。

優先度の高い部分から順に逆ポーランド記法に変換して行きます。

@Ａ＋ＢとＤ÷Ｅを変換する
Ｙ＝（ＡＢ＋）×（Ｃ−ＤＥ÷）
AＣ−ＤＥ÷を変換する
Ｙ＝（ＡＢ＋）×（ＣＤＥ÷−）
BＡＢ＋とＣＤＥ÷−を変換する
Ｙ＝ＡＢ＋ＣＤＥ÷−×
C『＝』を変換する
ＹＡＢ＋ＣＤＥ÷−×＝

なお他の選択肢は以下のようになります。
選択肢イ：Ｙ＝（（Ａ＋Ｂ）−Ｃ）×（Ｄ÷Ｅ）
選択肢ウ：Ｙ＝（Ａ＋Ｂ）×（Ｅ−（Ｄ÷Ｃ））
選択肢エ：Ｙ＝（Ａ＋Ｂ）×（Ｃ−Ｄ）÷Ｅ）
問８ 大きさｎの問題をＴ（ｎ）秒で解くプログラムがある。プログラムを用いて１０4以内で解ける最大の問題の大きさは、１０3秒以内で解ける最大の問題の大きさの約３．２倍になる。Ｔ（ｎ）を表す式はどれか。
ア １００ｎ
イ ５ｎ2
ウ ｎ3／２
エ ２n
解答 イ
解説 問題文から大きさが３．２倍になると時間が１０倍になることが分かります。Ｔ（ｎ）にｎと３．２ｎを代入して値が１０倍になるものを選びます。

選択肢ア：１００ｎと１００×３．２ｎ＝３２０ｎ
３２０ｎ／１００ｎ＝３．２倍

選択肢イ：５ｎ2と５×（３．２ｎ）2＝５×１０．２４ｎ2≒５０ｎ2
５０ｎ2／５ｎ2＝約１０倍

選択肢ウ：ｎ3／２と（３．２ｎ）3／２＝３２．７６８ｎ3／２≒３３3／２
３３ｎ3／ｎ3＝約３３倍
選択肢エ：２nと２3.2n
２3.2n／２n＝２2.2倍

よって、選択肢イが正解となります。
問９ 根付き木とは、根と呼ばれる特別な節点から木の枝が分かれるように、幾つかの辺が伸び、その先の節点から更に辺が伸びるということが繰り返されてできた構造である。根付き木の各節点ｖは、それぞれ３種類のポインタをもつ。

Parent[ｖ]：節点ｖの親を指すポインタ
FirstChild[ｖ]：節点ｖの第１子を指すポインタ
NextBrother[ｖ]：節点ｖの次の兄弟を示すポインタ

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


ポインタが指す相手がいないときには、ＮＩＬという記号で表される値がポインタに設定される。節点ｖも含めて、その兄弟をすべて出力するとき[　　]の部分に入れる手続きはどれか。ここで、節点ｖは根ではなく、report xは節点ｘを出力する手続きである。


[　　]
while x ≠ NIL do
　　report x
　　x ← NextBrother[x]
ア ｘ ← FirstChidl[v]
イ ｘ ← FirstChild[Parent[v]]
ウ ｘ ← NextBrother[v]
エ ｘ ← NextBrother[Parent[v]]
解答 イ
解説 問題文中にもありますが、木構造について図示をして確認をしておきます。

木構造を表示できません

問題文中のループは、自分を表示して次の兄弟を表示するという内容になっています。そのため、[　　]部分には、一番最初の兄弟をセットする必要があります。

例を挙げると、今自分が３番目の兄弟だったとすると、一度親に戻って、１番目の兄弟をセットする必要があります。これを定式化すると選択肢イとなります。
問１０ キューとスタックの二つのデータ構造がある。次の手続きを順に実行した場合、変数ｘに代入されるデータはどれか。ここで、

データｙをスタックに挿入することをpush(y),
スタックからデータを取り出すことをpop(),
データｙをキューに挿入することをenq(y),
キューからデータを取り出すことをdeq(),
とそれぞれ表す。

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x←pop()
ア ａ
イ ｂ
ウ ｃ
エ ｄ
解答 イ
解説 まず、二つのデータ構造を図示すると以下のようになります。

スタックとキューを表示できません

@ｐｕｓｈ（ａ）　　　　スタック：ａ　　　　　キュー：
Aｐｕｓｈ（ｂ）　　　　スタック：ａ，ｂ　　　キュー：
Bｅｎｑ（ｐｏｐ（））　スタック：ａ　　　　　キュー：ｂ
Cｅｎｑ（ｃ）　　　　　スタック：ａ　　　　　キュー：ｂ，ｃ
Dｐｕｓｈ（ｄ）　　　　スタック：ａ，ｄ　　　キュー：ｂ，ｃ
Eｐｕｓｈ（ｄｅｑ（））スタック：ａ，ｄ，ｂ　キュー：ｃ
Fｘ＝ｐｏｐ（）　　　　スタック：ａ，ｄ　　　キュー：ｃ

ということで、ｐｏｐ（）でとりだされるのは、ｂとなります。
問１１ 次の手順はシェルソートによる整列を示している。データ列“７, ３, ８, ３, １, ９, ４, ５, ６”を手順（１）〜（４）に従って整列するとき、手順（３）を何回繰り返して完了するか。ここで、[ ]は小数点以下を切り捨てた結果を表す。


〔手順〕
（１）[データ数÷３] → Ｈ
（２）データ列を互いにＨ要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を、挿入法を用いて整列する。
（３）[Ｈ÷３] → Ｈとする。
（４）Ｈが０であればデータ列の整列は完了し、０でなければ（２）に戻る。
ア ２
イ ３
ウ ４
エ ５
解答 ア
解説 シェルソートとは、ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が１になるまでこれを繰り返すことで、値を整列させる手法です。

順番に追いかけていきます。
１回目
（１）９÷３＝３→Ｈ
（２）（７，３，４）（２，１，５）（８，９，６）→（３，４，７）（１，２，５）（６，８，９）
（３）３÷３＝１→Ｈ
（４）Ｈ＝０でないので、（２）へ戻る

２回目
（２）（３，４，７，１，２，５，６，８，９）→（１，２，３，４，５，６，７，８，９）
（３）１÷３＝０→Ｈ
（４）Ｈ＝０なので、完了

よって、（３）は２回実行されています。
問１２ 与えられた１〜８の整数の列をヒープソートによって降順に並び替えるため、列の全体をヒープに構成したところ

１，４，２，５，８，３，６，７


となった。ここで先頭の要素と最後の要素を交換して

７，４，２，５，８，３，６，１


とし、次に下線の部分をヒープに構成する手続きを実行する。このとき、実行直後の列はどうなるか。ここで、ヒープは列の１番目（左端）の要素が根、列のｉ番目の要素の子が２ｉ番目と２ｉ＋１番目の要素とみなした完全２分木上に構成されるものとする。
ア ２，４，３，５，８，７，６，１
イ ４，２，５，８，３，６，７，１
ウ ７，４，５，８，３，６，２，１
エ ８，７，６，５，４，３，２，１
解答 ア
解説 ヒープソートとは未整列の部分を順序木に構成し、そこから最大値又は最小値を取り除いて既整列の部分に移す。これらの操作を繰り返して、未整列部分を縮めていくものです。まずは、ヒープソートと配列の関係を以下に図示します。

ヒープと配列を表示できません

ヒープは、親より子の値が小さいという制限があるので、根(添え字の先頭）が最小値になることになります。よって、選択肢アが正解となります。
問１３ 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーｘのハッシュ関数ｈ（ｘ）を

ｈ（ｘ）＝ｘ ｍｏｄ ｎ


とする。ここで、ｎはハッシュ表の大きさであり、ｘ ｍｏｄ ｎはｘをｎで割った余りを表す。キーａであるデータと、キーがｂであるデータの間で、衝突が起きる条件はどれか。
ア ａ＋ｂがｎの倍数
イ ａ−ｂがｎの倍数
ウ ｎがａ＋ｂの倍数
エ ｎがａ−ｂの倍数
解答 イ
解説 まず、実際に値を入れて計算してみたハッシュの例を下に示します。

ハッシュ

ハッシュのイメージがつかめたところで計算に移ります。

上の図からもわかるように、二つの値の差がｎの倍数であれば衝突が起こることがわかります。

なお、整数論においては、『ｍｏｄ ｎ』のことを『ｎを法とする』などといいます。
問１４ 整数ｘ、ｙ（ｘ＞ｙ≧０）に対して、次のように定義された関数Ｆ（ｘ、ｙ）がある。Ｆ（２３１、１５）の値は幾らか。ここで、ｘｍｏｄｙはｘをｙで割った余りである。

画像（問14）を表示できません
ア ２
イ ３
ウ ５
エ ７
解答 イ
解説 値を順番にトレースしていきます。

Ｆ（２３１，１５）＝Ｆ（１５，２３１ ｍｏｄ １５）＝Ｆ（１５，６）
Ｆ（１５，６＝Ｆ（６，１５ ｍｏｄ ６）＝Ｆ（６，３）
Ｆ（６，３）＝Ｆ（３，６ ｍｏｄ ３）＝Ｆ（３，０）
Ｆ（３，０）＝３

よって、Ｆ（２３１，１５）＝３となります。
問１５ 正の整数Ｍに対して次の二つの流れ図に示されるアルゴリズムを実行したとき、結果のｘの値が等しくなるようにしたい。ａに入れる条件として、正しいものはどれか。

画像（問15）を表示できません
ア ｎ＞Ｍ
イ ｎ＞Ｍ＋１
ウ ｎ＞Ｍ−１
エ ｎ＜Ｍ
解答 ア
解説 まず、左の流れ図をみると、ｘに１を入れた後、ｎをＭから１まで動かし、Ｍの階乗を計算しています。これと同じものを右の流れ図で行うためには、ｘ×Ｍとなるまでｎを増やす必要があります。右の流れ図は階乗を計算した後に、終了の判定が行われるのでｎ＝ｎ＋１が行われてからＭとの比較が行われます。つまり、Ｍ＋１のときにループを抜けるようにする必要があります。よって、正解はアとなります。

分かりにくい方は、実際に値を入れて計算してみるといいと思います。
今『Ｍ＝３』として計算してみましょう。

１回目
１→ｘ
１→ｎ
１×１→ｘ
ｎ＝ｎ＋１＝２
続ける（ｎ＝２）

２回目
１×２→ｘ
ｎ＝ｎ＋１＝３
続ける（ｎ＝３）

３回目
２×３→ｘ
ｎ＝ｎ＋１＝４
終わる（ｎ＝４）

選択肢ア：４＞３で確かにＹＥＳとなり、ループをぬけることができます。
選択肢イ：４＞３＋１ではＮＯでまだループは続きます。
選択肢ウ：４＞３−１では、その前にループを抜けてしまいます。
選択肢エ：ｎ＜３では、一番最初のループで抜けてしまいます。
問１６ コンピュータの命令実行順序として、適切なものはどれか。
ア オペランド読出し → 命令の解読 → 命令フェッチ → 命令の実行
イ オペランド読出し → 命令フェッチ → 命令の解読 → 命令の実行
ウ 命令の解読 → 命令フェッチ → オペランド読出し → 命令の実行
エ 命令フェッチ → 命令の解読 → オペランド読出し → 命令の実行
解答 エ
解説 プログラム内蔵方式での命令の実行は、まず大きく分けて、フェッチ（取り出し）とエグゼキューション（実行）に分けられます。大まかに流れをまとめると、命令読み出し、命令解読、実行アドレス計算、オペランド読み出し、演算、結果の格納というようになります。

オペランドとは、演算対象となる値や変数をいいます。

つまり、命令をメモリ上からもってきて、どんな命令かを解読し、必要な値を読み込み、実行するということです。
問１７ 内部割込みに分類されるものはどれか。
ア 商用電源の瞬時停電などの電源異常による割込み
イ ゼロによる除算を実行したことによる割込み
ウ 入出力が完了したことによる割込み
エ メモリパリティエラーが発生したことによる割込み
解答 イ
解説 まず、割り込には大きく分けて内部割りこみと外部割り込みがあります。内部割り込はゼロによる除算に代表されるソフトウェア的な原因。外部割り込みは、入出力の完了や電圧異常などに代表されるハードウェア的な原因です。

また、割り込みを受け付けるとＣＰＵはレジスタのデータを主記憶等に退避させ、割り込みの処理を実行します。さらに、複数の割り込みに優先順位をつけ、順位の低いものが、順位の高いものに割り込みを行わないようにマスク処理をする場合もあります。
問１８ メモリアクセスの信頼性を高めるための方式で、自動訂正が可能なものはどれか。
ア ＣＲＣ
イ ＥＣＣ
ウ チェックサム
エ パリティ
解答 イ
解説 ＥＣＣ（error check and correct：エラー訂正機能）メモリとは、その名の通り、ビット誤りを自動訂正する機能をもったメモリのことで、主にハミング符号を利用しています。

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

奇数パリティ：１（あるいは０）の個数が奇数個になるように、１ビットを付加するもの
奇数パリティ：１（あるいは０）の個数が偶数個になるように、１ビットを付加するもの
水平パリティ：転送を２次元の配列とみなしたときに、水平方向へのパリティを付加するもの。垂直パリティと合わせて利用されることが多い。
チェックサム：送信データを数値に対応させ、その合計を計算し付加するもの。
ハミング符号：データに冗長ビットを付加して、２ビットの誤り検出と１ビットの誤り訂正機能を持たせたもの。
巡回冗長検査（ＣＲＣ）：送信列から生成多項式とよばれる式をつくり、受信側で計算式の余りが０かどうかを調べる。
問１９ すべての命令が５命令で完了するように設計されたコンピュータがある。パイプライン制御の下で、２０命令を実行するには何サイクル必要となるか。ここで、すべての命令は途中で停止することなく実行できるものとする。
ア ２０
イ ２１
ウ ２４
エ ２５
解答 ウ
解説 パイプラインとは、下の図のように命令の段階を少しずつずらして行う方式です。なお各段を多重化したスーパースケーラ（スーパスカラ）方式というのもあります。

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

１つ目の命令は５サイクルで終了します。
２つ目の命令は６サイクルで終了します。
３つ目の命令は７サイクルで終了します。
・ ・ ・ １８つ目の命令２２サイクルで終了します。
１９つ目の命令２３サイクルで終了します。
２０つ目の命令２４サイクルで終了します。

よって、２４サイクルで終了することが分かります。

なお、問題文中にあるような依存関係や分岐命令などによってパイプラインの順番どおりに処理されないような状況をパイプラインハザードといいます。
問２０ 大量の画像データの高速転送を可能にする専用インタフェースはどれか。
ア ＡＧＰ
イ ＡＴＡ
ウ ＩＳＡ
エ ＰＣＩ
解答 ア
解説 AGP（Accelerated Graphics Port）はマザーボード上に設備され、グラフィックボードを接続するインタフェースです。また、ＡＴＡはＨＤＤを接続するインタフェースで、ＰＣＩは一般の拡張ボードを接続するインタフェースです。ＩＳＡはＰＣＩの前身でいまはほとんど使われていません。