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




このページは

ソフ開

(ソフトウェア開発技術者試験)

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

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



問1 16ビットの2進数nを16進数の各けたに分けて、下位のけたから順にスタックに格納するために、次の手順を4回繰り返す。a、bに入る適切な語句の組合せはどれか。ここでxxxx16は16進数xxxxを表す。

[手順]
(1) [ a ]をxに代入する。
(2) xをスタックにプッシュする。
(3) nを[ b ]論理シフトする。
画像(問1ans)を表示できません
解答
解説 16進数1桁は2進数4桁に相当します。よって、[ a ]で下位4ビットを取り出すために、000F16でマスク処理をします。値を入れ終わったあとは、次の4ビットが最下位4ビットになるようにシフトをするので、右に4ビットシフトします。

問2 次の浮動小数点表示法がある。小数点は仮数の左にあり、指数は64の“下駄履き表現”であって、値は(−1)s×0.f×2e-64である。二つの16進数45BF0000と41300000を、この浮動小数点表示法で表現された値として加算した結果はどれか。

画像(問2)を表示できません
41EF0000
45C20000
45EF0000
86EF0000
解答
解説 まず、二つの数値を2進数に展開し、符号、指数、仮数を確認します。説明上2つの数値の前者をA、後者をBとします。

A=45BF0000 = 0100 0101 1011 1111 0000 0000 0000 0000(符号=0=正、指数=100 0101=69、仮数=1011 1111 0000 0000 0000 0000)
B=41300000 = 0100 0001 0011 0000 0000 0000 0000 0000(符号=0=正、指数=100 0001=65、仮数=0011 0000 0000 0000 0000 0000)

次に、指数部を69であわせるます。Bの指数を4増やして同じ値にするためには、仮数を4ビット右にシフトします。

つまり、B’=符号=0、指数=69、仮数=0000 0011 0000 0000 0000 0000

最後に、AとB’の仮数部を足します。

 1011 1111 0000 0000 0000 0000
+0000 0011 0000 0000 0000 0000
-------------------------------
 1100 0010 0000 0000 0000 0000

符号部と指数部はあわせたものを使うので、
0100 0101 1100 0010 0000 0000 0000 0000=45C20000となります。

問3 浮動小数点形式で表現されたx(x>>1)に対して、√(x+1)−√xをそのまま計算すると、けた落ちが生じることがある。それを防ぐために変形した式として、適切なものはどれか。
画像(問3ans)を表示できません
解答
解説 けた落ちとは値がほぼ等しい浮動小数点同士の減算において、有効けた数が大幅に減ってしまうことで起きる誤差です。選択肢イ、ウ、エには減算があるので、桁落ちが生じる可能性があります。

例えば、x=9999として有効桁数を4桁とします。
√(10000)=100.0。√(9999)=99.99。そのまま計算すると、誤差は0.01となりますが、1/(100.0+99.99)=0.005となり、有効桁数4桁を確保することがでいます。

問4 2けたの2進数x12が表す整数をxとする。2進数x21が表す整数を、xの式で表したものはどれか。ここで、int(r)は非負の実数rの小数点以下を切り捨てた整数を表す。
画像(問4ans)を表示できません
解答
解説 まず、xを各桁を表現するとx=2*x1+x2となります。

1=(x−x2)/2=int(x/2)
2=x−2*x1=x−2*int(x/2)

入れ替えた値は、x1+2*x2なので、int(x/2)+2*(X−2*int(x/2))=int(x/2)+2*x−4*int(x/2)=2*x - 3*int(X/2)となります。

問5 XとYの否定論理積X NAND Yは、NOT(X AND Y)として定義される。X OR YをNANDだけを使って表した論理式はどれか。
((X NAND Y) NAND X)N AND Y
(X NAND X) NAND (Y NAND Y)
(X NAND Y) NAND (X NAND Y)
X NAND (Y NAND (X NAND Y))
解答
解説 まず、A NAND Aのように、同じ入力をNANDに入れるとAの否定を作ることができます。

X OR Y = (X OR Y)の二重否定
(X OR Y)の二重否定 = Xの否定 NAND Yの否定 (ド・モルガンの定理)
よって、(X NAND X)NAND(Y NAND Y)はX OR Yと等価であることがわかります。

最後に、XORやXANDはそれだけですべての演算子を作れるため、最小万能演算系と呼ばれます。

問6 100人の学生を調べたところ、スペイン語を学んでいるものは18人、ドイツ語は40人、フランス語は42人であった。これらの学生の中で、2言語を学んでいる者を調べると、スペイン語とドイツ語6人、ドイツ語とフランス語は15人、フランス語とスペイン語は5人であり、その中には、3言語すべてを学んでいるものは2人いた。いずれの言語も学んでいないの学生は何人か。
22
24
26
28
解答
解説 まず、問題文をベン図で表記すると以下のようになります。

画像(問6kai)を表示できません

まず、少なくとも1つ以上の言語を学んでいるのべ人数は、18+40+42=100人となります。
そして、重複している分を引いていきます。
上の式では、2言語学んでいる人数は2回。3言語学んでいる人数は3回カウントされています。
2言語学んでいる人数は、6+5+15となりますが、3言語学んでいる人が3回多くカウントされているので、2×3を引きます。つまり、6+5+15−2×3=20となります。
3言語学んでいる人物は、2人です。

100−20×1−2×2=76人となります。
これを100人から引いて24人がどの言語も学んでいない人数といえます。

問7 ハミング符号とは、データに冗長ビットを付加して、1ビットの誤りを訂正できるようにしたものである。ここで、X1、X2、X3、X4の4ビットからなるデータに、3ビットの冗長ビットP3、P2、P1を付加したハミング符号X1233421を考える。

画像(問7)を表示できません

このハミング符号1110011には1ビットの誤りが存在する。誤りビットを訂正した正しいハミング符号はどれか。

0110011
1010011
1100011
1110111
解答
解説 それぞれのパリティの式に代入しながら確認します。なお、排他的論理和はEORと表記します。

1 EOR 1 EOR 0 EOR 1 = 1
1 EOR 1 EOR 0 EOR 1 = 1
1 EOR 1 EOR 1 EOR 0 = 1

誤りは1ビットしかなく、かつ1ビット確実にあることが保障されているので、すべての式に影響があるX1が誤りであることがわかります。

問8 方程式a+b×cの逆ポーランド表記法による表現として、正しいものはどれか。
+×cba
×+abc
abc×+
cba+×
解答
解説 逆ポーランド記法とは、後置表記法とも呼ばれ、演算子を対象の後ろに記述する手法です。スタックを使うことで実現でき、括弧が不要なのでコンパイラなどで利用されています。

優先度の高い部分から順に逆ポーランド記法に変換して行きます。
b×cの部分を変換:a+bc×
a+b×cの部分を変換:abc×+

問9 葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、深さとは根から葉に至るまでの枝の個数を表す。
枝の個数がnならば、葉を含む節点の個数もnである。
木の深さがnならば、葉の個数は2n-1である。
節点の個数がnならば、深さはlog2nである。
葉の個数がnならば、葉以外の節点の個数はn−1である。
解答
解説 まず、木構造を以下にまとめます。今回は完全二分木の問題です。

木構造を表示できません

深さをnとした時の枝、葉、節点の個数を確認していきます。
n=1 → 枝:2、葉:2、節点:1+2=3
n=2 → 枝:2+4=6、葉4、節点:1+2+4=7
n=3 → 枝:2+4+8=14、葉:8、節点:1+2+4+8=15

これを元に各選択肢を調べていきます。
選択肢ア:枝がnならば、節点はn+1となります。
選択肢イ:木の深さがnならば、葉の個数は2nとなります。
選択肢ウ:節点の個数がnならば、深さは、(log2(n+1))−1となります。
選択肢エ:葉の個数がnならば、排外の節点の数はn−1となります。

よって、選択肢エが正解となります。

問10 ビット列x123456789=010111111とy123111に対して、次のアルゴリズムで表示されるkの変化はどれか。

画像(問10)を表示できません
1,2,3,4
1,2,4
1,3,4
1,4
解答
解説 順番に追いかけていきます。

k=1
d=1
d≠0なのでループに入ります。  k=1を出力します。
 x1≠y1なので、d=1となります。
 k=k+d=1+1=2となります。
d≠0なのでループを続けます。
 k=2を出力します。
 x2≠y1ではないので、else ifに移ります。
 x3≠y2なので、d=2となります。
 k=k+d=2+2=4となります。
d≠0なのでループを続けます。
 k=4を出力します。
 x4≠y1ではないので、else ifに移ります。
 x5≠y2ではないので、次のelse ifに移ります。
 x6≠y3ではないので、elseに移ります。
 d=0となります。
 k=k+d=4+0=4となります。
d=0なのでループを抜けます。

よって、出力結果は1,2,4となります。
なおこのアルゴリズムは、文字列のマッチングと探索時の添え字を表示しているものと考えられます。

問11 データの整列方法に関する記述のうち、適切なものはどれか。
クイックソートでは、ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。
シェルソートでは、隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。
バブルソートでは、中間的な基準値を決めて、それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に、それぞれの区分の中で同様な処理を繰り返す。
ヒープソートでは、未整列の部分を順序木に構成し、そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して、未整列部分を縮めていく。
解答
解説 代表的な整列法を下にまとめます。

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

問12 16進数で表される9個のデータ1A、35、3B、54、8E、A1、AF、B2、B3を順にハッシュ表に入れる。ハッシュ値とハッシュ関数f(データ)=mod(データ,8)で求めたとき、最初に衝突が起こるのはどのデータか。ここで、mod(a,b)はaをbで割った余りを表す。
54
A1
B2
B3
解答
解説 f(データ)=mod(データ、8)というのは、データA×(α8)=データBのとき衝突が起きます。ハッシュの概要を以下に図示します。

ハッシュを表示できません

一般的には10進数に変換して8で割った余りを順次もとめていけばいいのですが、今回は8で割ったあまりということなので、ビットの性質を利用したいと思います。
1→00001
9=1×8+1→01001
17=2×8+1→10001
25=3×8+1→11001

以上のように、8を加えても、下位3ビットは変化しません。よって、データの下位3ビットを調べて同じものがあった場合に衝突と判断することができます。

1A→010
35→101
3B→011
54→100
8E→110
A1→001
AF→111
B2→011

B2と3Bはともに011で値が3でハッシュ値が衝突することがわかります。

また、直感的に分かると思いますが、9個のデータを8個の表に入れると必ず衝突がおきます。(鳩の巣論法により証明)

問13 次の流れ図において、S4でYesと判断したときまでの、ステップS1〜S4の実行回数をそれぞれn1〜n4とする。n1〜n4の間に成立する式はどれか。

画像(問13)を表示できません
4=n1+n2+n3
4=n1+n2−n3
4=n1−n2+n3
4=−n1+n2+n3
解答
解説 幾つかのテストケースで試してみます。

まず、S1 → S2 → S3 → S4で実行されたとするとn1〜n4は全て1となります。

これに該当するものは選択肢イ、ウだけとなります。
つぎに、S1 → S2 → S3 → S4 → S3 → S4で実行されたとするとn1,n2=1。n3,n4=2となります。

これに該当するのは、選択肢ウだけとなります。

問14 流れ図に示す処理の動作の記述として、適切なものはどれか。ここで、二重線は並列処理の同期を表す。

画像(問14)を表示できません
Aの後にBC又はCB、BC又はCB、・・・と繰り返して実行する。
Aの後にBの無限ループ又はCの無限ループになる。
ABC又はACBを実行してデッドロックになる。
AB又はACを実行してデッドロックになる。
解答
解説 まず、処理が開始されるとAが実行されます。その後、BかCのどちらかが実行されます。そして、同期線をで他方の処理が終わるのをまちます。よって、BC又はCBが実行されます。これを繰り返して実行してきます。

問15 DDR−SDRAMの特徴として、適切なものはどれか。
クロック信号の立ち上がりと立ち下がりの両方に同期して、データを読み出す。
高速ページモードDRAMのページアクセスのサイクル時間を短くして、より高速にデータ転送する。
メモリセルからデータを読み出すとき、一度だけ行アドレスを指定した後、列アドレスを変えながら複数のデータを行バッファから高速に読み出す。
メモリバスクロックに同期して、1クロックにつき一つのデータを読み出す。
解答
解説 DDR−SDRAM(Double-Data-Rate Synchronous Dynamic Random Access Memory)とはDRAMの一種でクロック信号の立ち上がり(0から1への変化)と立ち下り(1から0への変化)の両方でデータのアクセスが可能なメモリです。一般的なメモリは立ち上がりのみで同期します。

問16 SRAMと比較した場合のDRAMの特徴はどれか。
SRAMよりも高速なアクセスが実現できる。
データを保持するためのリフレッシュ動作が不要である。
内部構成が複雑になるので、ビット当たりの単価が高くなる。
ビット当たりの面積が小さくなるので、高集積化に適している。
解答
解説 DRAMとSRAMを下にまとめます。

SRAM:フリップフロップで構成される。容量は小さいが高速。リフレッシュがいらず消費電力も小さい。比較的高価。主にキャッシュメモリに利用される。
DRAM:コンデンサで構成される。容量は大きいが低速。リフレッシュが必要で消費電力が大きい。比較的安価。主に主記憶に利用される。

リフレッシュとは、値を保持するために、電気的に再充電する操作をいいます。DRAMはトランジスタとコンデンサによって構成されているので、このような操作が必要となります。

問17 パイプラインの深さをD、パイプラインピッチをP秒とすると、I個の命令をパイプラインで実行するのに要する時間を表す式はどれか。ここで、パイプラインの各ステージは1ピッチで処理されるものとし、パイプラインハザードについては、考慮しなくてよい。
(I+D)×P
(I+D−1)×P
(I×D)+P
(I×D−1)+P
解答
解説 まず、パイプラインの例を下に示します。

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

パイプラインの深さは、分かれた段階の個数で、上の例では4です。
パイプラインピッチとは、1つの段階にかかる時間です。

実際に値を入れて後から一般化します。

1個目の命令は、D×Pで終了します。
2個目の命令は、(D+1)×Pで終了します。
3個目の命令は、(D+2)×Pで終了します。

I個目の命令は、(D+I−1)×Pで終了します。

よって、選択肢イが正解となります。(Iが十分に大きければ選択肢アに収束します)

なお、パイプラインハザードとは、依存関係や分岐命令などによってパイプラインの順番どおりに処理されないような状況をいいます。

問18 プロセッサにデータを読み込むときにキャッシュメモリがヒットしなかった場合、キャッシュメモリ制御装置が行う動作はどれか。
キャッシュメモリから所要のデータをブロック転送し、磁気ディスクに書き込む
磁気ディスクから所要のデータをブロック転送し、キャッシュメモリに読み込む。
主記憶から所要のデータをブロック転送し、キャッシュメモリに読み込む。
ディスクキャッシュから所要のデータをブロック転送し、主記憶に読み込む。
解答
解説 キャッシュメモリは、主記憶装置(=メインメモリ)とCPUとの処理能力の速度の差を埋めるために用いられるメモリです。メインメモリは、まずキャッシュメモリにデータを探しに行き、そのデータがある場合はキャッシュメモリから、ない場合はメインメモリからデータを読み出します。よって、存在しない確率 ×メインメモリの読み込み速度+存在する確率×キャッシュメモリの読み込み速度となります。

データがキャッシュにない場合には、主記憶装置から該当のデータがあるブロックをキャッシュメモリに読み出してからロードを行います。これは、一度呼ばれたデータは再び呼び込まれる可能性が高いという局所性に基づくものです。

問19 RAIDの分類においては、ミラーリングを用いることで信頼性を高め、障害発生時には冗長ディスクをデータを復元を行う方式はどれか。
RAID1
RAID2
RAID3
RAID4
解答
解説 RAID(Redundant Arrays of Inexpensive Disks あるいはRedundant Arrays of Independent Disks)とは、複数のHDDを1台の高信頼性のHDDとして利用する技術のことです。RAID1〜6は冗長ビットをどこに配置するかで決まります。代表的なRAIDの例を下に示します。

RAID0(ストライピング):複数のHDDに分散してデータを書き込む(冗長性はない)
RAID1(ミラーリング):複数のHDDに同じデータを書き込む
RAID2:ビット単位での専用誤り訂正符号ドライブをもつ
RAID3:ビット/バイト単位での専用パリティドライブをもつ
RAID4:ブロック単位での専用パリティドライブをもつ
RAID5:ブロック単位で冗長データをもつが、特定のドライブに冗長データを書き込むということはしない。
RAID6:ブロック単位・複数パリティを分散して書き込む

また、複数の技術を組み合わせた、RAID1+0、RAID0+1、RAID5+0、RAID0+5、RAID5+1、RAID1+5などもあります。

問20 シリアルATAによる内臓周辺機器の接続方法を説明したものはどれか。
ホストコントローラからのケーブルには、マスタとスレーブの2台の周辺機器が接続できる。
ホストコントローラと周辺機器は、デイジチェーンやツリー構造で接続できる。
ホストコントローラと周辺機器は、ハブを介して接続する。
ホストコントローラとポイントツーポイントで周辺機器を接続する。
解答
解説 シリアルATA(SATA)とは、従来のATA(IDE)やUltraATAなどのパラレル転送と異なり、シリアル化をし、高速化したもので、外部記憶用のドライブを接続するインタフェースです。

マスタとスレーブは、1つのIDEケーブルに2つの機器をつなぐ際に、認識をわけるために行う設定です。シリアルATAでは1対1で接続を行うので設定は必要ありません。ポートマルチプレイヤという技術を使うことで、1チャンネルあたりのデバイス数を増やすことができます。

選択肢アは、ATAなどの説明です。
選択肢イは、IEEE1393などの説明です。
選択肢ウは、USBなどの説明です。