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



このページは

ソフ開

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

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

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


問１ 次の浮動小数点表示法がある。小数点は仮数の左にあり、指数は６４の“下駄履き表現”であって、値は（−１）s×０.ｆ×２e-64である。二つの１６進数４５ＢＦ００００と４１３０００００を、この浮動小数点表示法で表現された値として加算した結果はどれか。

画像（問1）を表示できません
ア ４１ＥＦ００００
イ ４５Ｃ２００００
ウ ４５ＥＦ００００
エ ８６ＥＦ００００
解答 イ
解説 まず、二つの数値を２進数に展開し、符号、指数、仮数を確認します。説明上２つの数値の前者をＡ、後者をＢとします。

Ａ＝45BF0000 ＝ 0100 0101 1011 1111 0000 0000 0000 0000（符号＝0＝正、指数＝100 0101＝69、仮数＝1011 1111 0000 0000 0000 0000）
Ｂ＝41300000 ＝ 0100 0001 0011 0000 0000 0000 0000 0000（符号＝0＝正、指数＝100 0001＝65、仮数＝0011 0000 0000 0000 0000 0000）

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

つまり、Ｂ’＝符号＝０、指数＝６９、仮数＝0000 0011 0000 0000 0000 0000

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

　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＝４５Ｃ２００００となります。
問２ 負の整数を表現する代表的な方法として、次の３種類がある。

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

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

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

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

よって、ｃ、ｂ、ａとなります。
問３ ０以上２５５以下の整数ｎに対して、

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


と定義する。ｎｅｘｔ（ｎ）と恒等的に等しい式はどれか。ここでｘ ＡＮＤ ｙ及びｘ ＯＲ ｙは、それぞれｘとｙを２進数表現にして各けたごとの論理積及び論理和をとったものとする。
ア （ｎ＋１）ＡＮＤ２５５
イ （ｎ＋１）ＡＮＤ２５６
ウ （ｎ＋１）ＯＲ２５５
エ （ｎ＋１）ＯＲ２５６
解答 ア
解説 定義式をみると、０なら１、１なら２と１ずつ足していって２５５だったら０にもどるという。いわゆる２５６進カウンタであることがわかります。これを２進数で考えます。２５５とは１１１１１１１１です。ここで１を加えると０になるので１００００００００が０になる処理を考えると選択肢アが正解だとわかります。
問４ 全体集合Ｓ内に部分集合ＡとＢがあるとき、Ａ∩Ｂに等しいものはどれか。ここで、Ａ∪ＢはＡとＢの和集合、Ａ∩ＢはＡとＢの積集合、ＡはＳにおけるＡの捕集合、Ａ−ＢはＡからＢを除いた差集合を表す。
ア （Ａ∪Ｂ）−（Ａ∩Ｂ）
イ （Ｓ−Ａ）∪（Ｓ−Ｂ）
ウ Ａ−Ｂ
エ Ｓ−（Ａ∩Ｂ）
解答 ウ
解説 ベン図や真理値表を用いても良いのですが、ここでは変数の簡約をつかって解を求めます。

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

よって、選択肢ウが問題の式と同じとなります。
問５ ｘ、ｙ、ｚを論理変数、Ｔを真、Ｆを偽とするとき、次の真理値表で示される関数ｆ（ｘ、ｙ、ｚ）を表す論理式はどれか。ここで、∧は論理積、∨は論理和、ＡはＡの否定を表す。

画像（問5）を表示できません
ア （ｘ∧ｙ）∨（ｙ∧ｚ）
イ （ｘ∧ｙ）∨（ｙ∧ｚ）
ウ （ｘ∧ｙ）∨（ｙ∧ｚ）
エ （ｘ∧ｙ）∨（ｙ∧ｚ）
解答 イ
解説 まず、真となる出力の入力を書き出します。

@ｘ∧ｙ∧ｚ
Aｘ∧ｙ∧ｚ
Bｘ∧ｙ∧ｚ
Cｘ∧ｙ∧ｚ

つぎに、各式をまとめていきます。

@とAをまとめてｘ∧ｙ
BとCをまとめてｙ∧ｚ

これらの∨なので、（ｘ∧ｙ）∨（ｙ∧ｚ）となります。
問６ ハミング符号とは、データに冗長ビットを付加して、１ビットの誤りを訂正できるようにしたものである。ここで、Ｘ1Ｘ2Ｘ3Ｘ4の４ビットからなるデータに、３ビットの冗長ビットＰ3Ｐ2Ｐ1を付加したハミング符号Ｘ1Ｘ2Ｘ3Ｐ3Ｘ4Ｐ2Ｐ1を考える。

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

このハミング符号１１１００１１には１ビットの誤りが存在する。誤りビットを訂正した正しいハミング符号はどれか。
ア ０１１００１１
イ １０１００１１
ウ １１０００１１
エ １１１０１１１
解答 ア
解説 それぞれのパリティの式に代入しながら確認します。なお、排他的論理和はＥＯＲと表記します。

１ ＥＯＲ １ ＥＯＲ ０ ＥＯＲ １ ＝ １
１ ＥＯＲ １ ＥＯＲ ０ ＥＯＲ １ ＝ １
１ ＥＯＲ １ ＥＯＲ １ ＥＯＲ ０ ＝ １

誤りは１ビットしかなく、かつ１ビット確実にあることが保障されているので、すべての式に影響があるＸ1が誤りであることがわかります。
問７ ａ，ｂ，ｃ，ｄの４文字からなるメッセージを符号化してビット列にする方法として表のア〜エの４通りを考えた。この表はａ，ｂ，ｃ，ｄの各１文字を符号化するときのビット列を表している。メッセージ中のａ，ｂ，ｃ，ｄの出現頻度は、それぞれ５０％、３０％、１０％、１０％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の平均長が最も短くなるものはどれか。
画像（問7ans）を表示できません
解答 ウ
解説 それぞれの選択肢を評価していきます。

選択肢ア：００が現れた時に、ａａなのかｃなのか判別できません。一意に復号不能なので不適切です。
選択肢イ：０１１０が現れた時に、ａｄａなのかｂｃなのか判別できません。一意に復号不能なので不適切です。
選択肢ウ：一意に復号可能なので、平均ビット長を計算します。０．５×１＋０．３×２＋０．１×３＋０．１×３＝０．５＋０．６＋０．３＋０．３＝１．７
選択肢エ：一意に復号可能なので、平均ビット長を計算します。すべて２ビットなので、平均ビット長は２

よって、選択肢ウが最も平均ビット長を短くできる符号化といえます。
なお、このように使用頻度の高いものに短いビット列を割り当てる符号化をハフマン符号といいます。
問８ 次に示す記述は、ＢＮＦで表現されたあるプログラム言語の構文の一部である。＜パラメタ指定＞として、正しいものはどれか。

＜パラメタ指定＞：：＝＜パラメタ＞｜（＜パラメタ指定＞，＜パラメタ＞）
＜パラメタ＞：：＝＜英字＞｜＜パラメタ＞＜英字＞
＜英字＞：：＝ａ｜ｂ｜ｃ｜ｄ｜ｅ｜ｆ｜ｇ｜ｈ｜ｉ
ア （（ａｂｃ，ｄｅｆ））
イ （（ａｂｃ，ｄｅｆ），ｇｈｉ）
ウ （ａｂｃ）
エ （ａｂｃ，（ｄｅｆ））
解答 イ
解説 それぞれの選択肢を順次評価していってもいいのですが、ここでは論理的な方法で解を求めます。

括弧を作ることができるのは、（＜パラメタ指定＞，＜パラメタ＞）の部分だけです。この部分に注目すると、『（ 』と『，』と『 ）』がセットで現れることがわかります。このことから選択肢アと選択肢ウが生成できないことがわかります。

つぎに、『，』の後ろが＜パラメタ指定＞ではなく、＜パラメタ＞なので、英字の繰返ししか生成できません。つまり、『，』の後ろに『（ 』がくることはありません。よって、選択肢エが間違いであることがわかります。
問９ データ構造に関する記述の内、Ｂ木の説明として適切なものはどれか。
ア ある特定のアルゴリズムに従って、レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。
イ 索引部の各ノードのキー値を中心にして、小さい側のレコード数と大きい側のレコード数の比率が、ある範囲内に収まるように動的に再配置しながら格納する。
ウ レコードの物理的配置とは独立に、論理的にレコードをつなぐポインタによって、レコードを関係付けて格納する。
エ レコードをキー値の昇順にしてトラックなどのアクセス単位（ページ）ごとに格納し、各ページ内の最大キー値とそのページの番地をもつ索引を作る。
解答 イ
解説 それぞれの選択肢のデータ構造を以下にまとめます。

選択肢ア：ハッシュ
選択肢イ：Ｂ木
選択肢ウ：リスト
選択肢エ：索引順編成ファイル
問１０ 次の条件ａ〜ｄを満たすデータを処理するために、内部データ構造の要素@〜Bを考えた。これらを用いて実装できるデータ構造は、どの抽象データ型に分類されるか

[条件]
ａ データはすべて同じ型をもつ。
ｂ データは時系列的に発生する。
ｃ 処理の済んだデータを記憶しておく必要はない。
ｄ 未処理のデータ数は常にｎ未満になることが分かっている。

[内部データ構造の要素]
@ データと同じ型の要素をもつ大きさｎの配列Ａ（A[0],A[1]…A[n-1]）
A ０以上ｎ未満の整数が記憶できる変数ＸとＹ
B ０以上ｎ未満の値をとる仮引数ｉに対して、ｉ＋１をｎで割った余りを返す関数succ(i)
ア キュー（ＦＩＦＯ）
イ スタック（ＬＩＦＯ）
ウ 根付き木
エ 優先度キュー
解答 ア
解説 [条件]を満たすためのものが、[内部データ構造の要素]なのでこちらだけを考えます。

要素@から、ｎ未満のデータをそれぞれ配列に格納することが予想されます。
要素Aから、使用される変数が２つであることがわかります。
要素Bから、０、１、２、・・・ｎ−１、０、１のように、値を循環させることがわかります。

以上のことからキューをあらわしていることがわかります。（ＸとＹは入り口と出口を表している変数と予想されます）

最後に、スタックとキューのデータ構造を以下にまとめます。

スタックとキューを表示できません
問１１ 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ未使用領域のうちで最小のものを割り当てる最良適合（best-fit）アルゴリズムを用いる場合、未使用領域を管理するためのデータ構造として、メモリ割当て時の処理時間が最も短いものはどれか。
ア 空き領域のアドレスをキーとする２分木探索木
イ 空き領域の大きさが小さい順の片方向連結リスト
ウ 空き領域の大きさをキーとする２分探索木
エ アドレスに対応したビットマップ
解答 ウ
解説 使用するメモリ量よりぎりぎり大きいメモリ空間を探すわけなので、大きさを基準に検索を行います。よって、選択肢イと選択肢ウのどちらかになります。リストよりもハッシュのほうが高速に検索ができるので、選択肢ウのほうが処理時間が短くなるといえます。
問１２ 分割統治法を適用した整列（ソート）アルゴリズムはどれか。
ア クイックソート
イ 選択ソート
ウ 挿入ソート
エ ヒープソート
解答 ア
解説 分割統治法とは、大きな問題を複数の小さい問題に分割し、その小さな問題を解決することによって、全体の問題を解決するという手法です。ソートアルゴリズムでは、ソート範囲を区切って再帰的にソートをするクイックソートやマージソートなどが該当します。
問１３ キー値が１〜1,000,000の範囲で一様にランダムであるレコード３件を、大きさ１０のハッシュ表に登録する場合、衝突が起こらない確率は幾らか。ここで、ハッシュ値にはキー値をハッシュ表の大きさ１０で割った余りを用いる。
ア ０．２８
イ ０．７
ウ ０．７２
エ ０．８
解答 ウ
解説 まず、ハッシュの概念を以下にしめします。

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

キー値は十分にランダムであるので、１０個に入れたときにどうなるかを考えます。

１件目：ハッシュ表は空なので、衝突は起こりません。
２件目：１つデータが入っているので、９／１０の確率で衝突が起こりません。
３件目：２つデータが入っているので、８／１０の確率で衝突が起こりません。

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

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

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

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

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

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

選択肢ア：４＞３で確かにＹＥＳとなり、ループをぬけることができます。
選択肢イ：４＞３＋１ではＮＯでまだループは続きます。
選択肢ウ：４＞３−１では、その前にループを抜けてしまいます。
選択肢エ：ｎ＜３では、一番最初のループで抜けてしまいます。
問１５ 条件１〜４の検査する順序を変えても、動作が変化しない決定表はどれか。ここで、“−”は条件を判定しないことを表す。
画像（問15ans）を表示できません
解答 ア
解説 決定表は、１つの縦の列を見て、条件がＹとなっているものを見たいしている場合には、その下の動作がＸとなっているものを実行するという意味です。表は左から順に評価し、一番最初に条件を満たしたものを実行します。たとえば、選択肢アの一番左の列であれば、条件１、２、３、４を満たすのであれば、動作１を実行するという意味です。

左から順に評価していくので、表の順番によっては挙動が変化することがあります。つまり、複数行に該当するような場合には考慮が必要です。

選択肢ア：条件１と条件２で複数行に該当することはありえないので、動作は変化しません。
選択肢イ：例えば、条件１＝Ｎ、条件２＝Ｙ、条件３＝Ｎの場合は、３列目と４列目に該当するため、順序を変えると動作が変化します。
選択肢ウ：例えば、条件１＝Ｎ、条件２＝Ｙ、条件３＝Ｎ、条件＝Ｎの場合に、３列目と４列目に該当するため、順序を変えると動作が変化します。
選択肢エ：例えば、条件１＝Ｎ、条件２＝Ｙ、条件３＝Ｙの場合は、３列目と４列目に該当するため、順序を変えると動作が変化します。
問１６ ＳＲＡＭと比較した場合のＤＲＡＭの特徴はどれか。
ア ＳＲＡＭよりも高速なアクセスが実現できる。
イ データを保持するためのリフレッシュ動作が不要である。
ウ 内部構成が複雑になるので、ビット当たりの単価が高くなる。
エ ビット当たりの面積を小さくできるので、高集積化に適している。
解答 エ
解説 二つのメモリを以下にまとめます。

ＳＲＡＭ：容量は小さいが高速。リフレッシュがいらず消費電力も小さい。比較的高価。主にキャッシュメモリに利用される。
ＤＲＡＭ：容量は大きいが低速。リフレッシュが必要で消費電力が大きい。比較的安価。主に主記憶に利用される。

（リフレッシュとは、値を保持するために、電気的に再充電する操作をいいます。ＤＲＡＭはトランジスタとコンデンサによって構成されているので、このような操作が必要となります。）
問１７ スーパスカラの説明はどれか。
ア 処理すべきベクトルの長さがベクトルレジスタより長い場合、ベクトルレジスタ長の組に分割して処理を繰り返す方式である。
イ パイプラインを更に細分化することによって高速化を図る方式である。
ウ 複数のパイプラインを用いて、同時に複数の命令を実行可能にすることによって高速化を図る方式である。
エ 命令語を長く取り、一つの命令で複数の機能ユニットを同時に制御することによって高速化を図る方式である。
解答 ウ
解説 スーパースカラ（スーパースケーラ）方式は、パイプライン技術の応用的な技術です。パイプラインとは、下の図のように命令の段階を少しずつずらして多重化する方式です。

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

これを応用して、命令パイプライン上で複数の命令を同時に実行する方式をスーパースカラ方式といいます。例を図示します。

スーパースカラを表示できません

選択肢アは、ベクトルプロセッサの説明です。
選択肢イは、スーパーパイプラインの説明です。
選択肢エは、ＶＬＩＷ（Very Long Instruction Word）の説明です。
問１８ １件のトランザクションについて８０万ステップの命令実行を必要とするシステムがある。プロセッサの性能が２０ＭＩＰＳで、プロセッサの使用率が８０％のときのトランザクションの処理能力（件／秒）は幾らか。
ア ２
イ ２０
ウ ２５
エ ３１
解答 イ
解説 まず、プロセッサの性能が２０ＭＩＰＳで、使用率が８０％なので、１秒間に２０×１０6×０．８＝１６×１０6命令処理ができます。

そして、トランザクションは８０万命令必要なので、１秒間に処理できる件数は１６×１０6／８０×１０4＝１６００／８０＝２０件／秒となります。
問１９ 図のアーキテクチャのシステムにおいて、ＣＰＵからみた、主記憶とキャッシュメモリを合わせた平均読込み時間を表す式はどれか。ここで、読み込みたいデータがキャッシュメモリに存在しない確率をｒとし、キャッシュメモリ管理に関するオーバヘッドは無視できるものとする。

画像（問19）を表示できません
画像（問19ans）を表示できません
解答 イ
解説 キャッシュメモリは、主記憶装置（＝メインメモリ）とＣＰＵとの処理能力の速度の差を埋めるために用いられるメモリです。メインメモリはまず、キャッシュメモリにデータを探しに行き、そのデータがある場合は、キャッシュメモリから、ない場合はメインメモリからデータを読み出します。よって、存在しない確率 ×メインメモリの読み込み速度＋存在する確率×キャッシュメモリの読み込み速度となります。両者の容量はアクセス速度には関係がありません。
問２０ ＣＰＵと主記憶の間に置かれるキャッシュメモリにおいて、主記憶のあるブロックを、キャッシュメモリの複数の特定ブロックと対応づける方式はどれか。
ア セットアソシアティブ方式
イ ダイレクトマッピング方式
ウ フルアソシアティブ方式
エ ライトスルー方式
解答 ア
解説 キャッシュメモリはデータをライン(あるいはブロック)と呼ぶある程度まとまった単位で管理します。
例えば４ビットを１つのラインとしてまとめて管理する場合は、その上位ビットを保存しておきます。この上位のアドレスをフレームアドレス、下位のアドレスをエントリアドレスといいます。これによりフレームアドレスをまず検索し、その後エントリアドレスを検索することで、高速化できます。
（例：１０１０００００〜１０１０１１１１は、１０１０を上位ビットとして保存しておきます。）

このフレームアドレスバッファが複数ある場合は、複数のデータを格納できます。このときのバッファの個数をセット数（ウェイ）と呼びます。このような構造により、局所的に連続したデータにアクセスする場合に高速に処理できます。

これを踏まえて、キャッシュメモリの方式を下にまとめます。

ダイレクトマッピング方式：メモリ空間と１対１で割り当てる方式。すべてのメモリ領域を１対１でカバーするのでヒット率が低い
フルアソシアティブ方式：任意のメモリ空間と対応付ける方法。使用率が高いところを自由に持ってこれるので、ヒット率が高い反面オーバヘッドが大きい
セットアソシアティブ方式：上の二つの間のような方法。ある程度区切った空間を自由に対応付けることができる。通常セット数ｎに対して、ｎウェイセットアソシアティブという

ライトスルー方式は、キャッシュメモリのアクセス方式の一種です。