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

ソフ開

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

問２ 規格ＩＥＥＥ７５４（ＩＥＣ ６０５５９）による単精度の浮動小数点表示法は、次のとおりである。１０進数１４．７５をこの規格に従って表示したときの指数部Ｅのビット列はどれか。 たとえば、２進数（０．０１１）2は、（−１）0×２125-127×（１＋０．１）2なので、Ｓ＝０、Ｅ＝１２５、Ｆ＝（０．１）2となる。ここで、（ ）2内の数は２進数を表す。

ア ００００００１０ イ ００００００１１ ウ １０００００１０ エ １０００００１１

解答 ウ

解説 例があるので、これと照らし合わせながら１４．７５を変換していきます。まずは、１４．７５を２進数に変換します。整数部と小数点以下を分けて計算します。すると（１４．７５）10＝（１１１０．１１）2となります。 次に、これを（１＋○）2×２△の形にします。まず、シフトして（１．１１０１１）2×２3。 よって、正数なのでＳ＝１、Ｆ＝は１１０１１、Ｅ＝３＝１３０−１２７なので、１０００００１０となります。

問５ Ａ，Ｂ，Ｃ，Ｄを論理変数とするとき、次のカルノー図と等価な論理式はどれか。

ア Ａ・Ｂ・Ｄ＋Ｂ・Ｄ イ Ａ・Ｂ・Ｃ＋Ｂ・Ｄ ウ Ａ・Ｂ・Ｄ＋Ｂ・Ｄ エ Ａ・Ｂ・Ｃ・Ｄ＋Ｂ・Ｄ

解答 ウ

解説 カルノー図とは、多変数の論理式を簡単化するのに用いられる図で、変数が多くなるとベン図では表現しにくくなり、カルノー図が用いられることが多いです。 例として、ＡＢＣ＋ＡＢＣ＋ＡＢＣ＋ＡＢＣが与えられたとします。真を１、偽を０に対応させると以下のようになります。 そこで、隣り合うもの同士をまとめると、緑の部分がＡＣ、青の部分がＢＣ、赤の部分がＡＢとなります。 よって、ＡＣ＋ＢＣ＋ＡＢとなり、元の式の簡約化ができました。 それでは、問題のカルノー図を考えます。以下のように色分けをします。端同士がつながっていることや、グループ化は２の倍数個で行われることに注意してください。 赤い線の部分が、Ｂ・Ｄ。青い部分がＡ・Ｂ・Ｄとなり、これを＋でつないだものが等しい論理式となります。

問６ ８ビットのレジスタがある。このレジスタの各ビットの値をｄ0、ｄ1、・・・ｄ7とし、パリティビットの値をｐとする。奇数パリティの場合、常に成立する関係式はどれか。

解答 エ

解説 いくつかの例をためしてみるのも手ですが、確実ではなく、偶然成立してしまう可能性も捨てきれないので論理的に考えてます。 まず、排他的論理和の性質ですが、１と０、０と１のとき１。１と１、０と０のとき０になります。つまり、１が奇数個の場合に限り１を出力するといえます。つまり、最後に１の個数が奇数個になるようにパリティを調整すると出力は１になることがわかります。

問９ 次の２分探索木からルートノード７を削除し、そのあと再び７を追加した２分探索木はどれか。

解答 イ

解説 まず、木の基本的な事項について以下に図示します。 次に、２分探索木（２分木）とは、すべてのノードについて、左の子の値≦親の値≦右の子の値（あるいは大小が逆）の値となっているものを指します。そして、木からルート（根）のノードを取り除く場合は、末端の葉と入れ替えて削除します。つまり、新しいルートは６になります。 そして、あたらしいルートになった時点で再構築が行われますが、左の子の値≦親の値≦右の子が守られているので、そのままになります。最後に７を再度追加するわけですが、６＜７により右、７＜９により左、７＜８により左なので、ルートから右、左、左に進んだ選択肢イの木となります。

問１０ 配列Ａ[１]、Ａ［２］、･･･、Ａ［７］で、Ａ［１］を根とし、Ａ［ｉ］の左側の子をＡ［２ｉ］、右側の子をＡ[２ｉ＋１]とみなすことによって、２分木を表現する。このとき、配列の線形探索は２分木の探索のどれに当たるか。

ア 行きがけ（先行順）深さ優先探索 イ 帰りがけ（後行順）深さ優先探索 ウ 通りがけ（中間順）深さ優先探索 エ 幅優先探索

解答 エ

解説 木と配列の関係をまとめると以下のようになります。 つまり、これは、１段目をさがし、２段目をさがし、３段目をさがし・・・となるので、幅優先探索となります。

問１１ キューの実装のうち、キューへの追加と取出しの手間が最少のものはどれか。ここで、キューの要素数は可変とし、図中の矢印は、ポインタの指示を表す。

解答 ウ

解説 実装するのはキュー、つまり先入先出のデータ構造になります。よって、データの先頭と末尾に高速にアクセスすることができれば、手間が最少になるといえます。ここでは、先頭と末尾へのポインタをもっている選択肢ウのような構造が望ましいといえます。

問１２ キー値が等しい要素同士について、整列前の要素の順序（前後関係）を保つアルゴリズムを、安定な整列アルゴリズムという。次の二つの整列アルゴリズムに対して、安定にできるかどうかを考える。正しい組合せはどれか。 [アルゴリズムとその特徴] 選択ソート 未整列の並びに対して、最小のキー値をもつ要素と先頭の要素とを入れ替える。 同様の操作を未整列の並びの長さを一つずつ減らしながら繰り返す。 挿入ソート 未整列要素の並びの先頭の要素を取り出し、その要素を整列済みの要素の正しい位置に挿入する。

解答 ウ

解説 つまり、安定な整列アルゴリズムとは、５，３'，２，３''，４があったときに、確実に２，３'，３''，４，５になるアルゴリズムのことです。 選択ソート： ３',５,３'',２があったとすると １つ目まで確定：２，５，３''，３' ２つ目まで確定：２，３''，５，３' ソート完了：２，３''，３'，５ 以上のように、値を入れ替える際に前にある値が後ろに移動する可能性があるので安定な整列アルゴリズムにはなりません。 挿入ソート： ３',５,３'',２があったとすると １つめまで確定：２，３'，５，３'' ２つめまで確定：２，３'，５，３'' ソート完了：２，３'，３''，５ 以上のように、同じ値が合った場合には後ろに追加するというルールを決めておけば安定な整列アルゴリズムにすることができます。

問１３ 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーｘのハッシュ関数ｈ（ｘ）を ｈ（ｘ）＝ｘ ｍｏｄ ｎ とする。ここで、ｎはハッシュ表の大きさであり、ｘ ｍｏｄ ｎはｘをｎで割った余りを表す。キーａであるデータと、キーがｂであるデータの間で、衝突が起きる条件はどれか。

ア ａ＋ｂがｎの倍数 イ ａ−ｂがｎの倍数 ウ ｎがａ＋ｂの倍数 エ ｎがａ−ｂの倍数

解答 イ

解説 まず、実際に値を入れて計算してみたハッシュの例を下に示します。 上の図からもわかるように、二つの値の差がｎの倍数であれば衝突が起こることがわかります。 なお、整数論においては、『ｍｏｄ ｎ』のことを『ｎを法とする』などといいます。

問１４ 探索表の３種類の構成法を例とともにａ〜ｃに示す。これらの構成法にふさわしい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

解答 ア

解説 まず、３つの探索法についてまとめます。データ量をｎとしたときのオーダ（検索時間）もあわせてまとめます。 ２分探索：ソートされているデータに対して、中間値と目的とを比較することで、大きいグループと小さいグループに分け、１回の検索で探索範囲を半分にしていく。オーダはｌｏｇ2ｎ 線形探索：上から一つずつ比較していく方法。オーダはｎ ハッシュ検索：ハッシュ関数を使って、格納場所を決める方法。ハッシュ値が同じになる衝突（シノニム）などがなければ、１度で検索場所が決まります。オーダは１ それでは、それぞれの表に適した検索法を考えます。 表ａ：コードが順番にならんでいる（ソートされている）ので、線形探索よりも２分探索のほうが高速に検索ができるので、２分探索を利用します。 表ｂ：コードに規則性がないが、使用頻度順にならんでいるということは、上にあるものほど発見しやすいので、線形探索を利用します。 表ｃ：ハッシュにより場所を決めているので、同じ関数を利用して求めるのが一番よいので、ハッシュ表探索を利用します。

問１６ ＣＰＵのパイプライン処理を有効に機能させるプログラミング方法はどれか。

ア ＣＡＳＥ文を多くする。 イ 関数の個数をできるだけ多くする。 ウ 分岐命令を少なくする。 エ メモリアクセス命令を少なくする。

解答 ウ

解説 まず、パイプラインの例を下に示します。 なお、分かれた段階の個数をパイプラインの深さといい、１つの段階にかかる時間をパイプラインピッチといいます。 見てわかるとおり、パイプラインは、きれいに各段階が１つずつずれているのが理想的ですが、実際はこのようにきれいにはなりません。それは、依存関係や分岐命令によって、順番どおりに処理できない場合が生じるからです。逆に言えば、依存関係や分岐命令を極力減らすことでパイプラインを効果的に利用することができるといえます。 依存関係や分岐命令などによってパイプラインの順番どおりに処理されないような状況をパイプラインハザードといいます。

問１８ キャッシュメモリのアクセス時間及びヒット率と、主記憶のアクセス時間の組合せのうち、主記憶の実効アクセス時間が最も短くなるのはどれか。

解答 エ

解説 すべてを計算してもよいのですが、今回はアクセス時間が同じでヒット率が低いという理由で、選択肢イとくらべて選択肢アを除外。選択肢エとくらべて選択肢ウを除外できます。よって、選択肢イと選択肢エだけを計算すれば十分です。 選択肢イ：１０×０．７＋７０×０．３＝７＋２１＝２８ 選択肢エ：２０×０．８＋５０×０．２＝１６＋１０＝２６ よって、２６ナノ秒で選択肢エが最も高速だといえます。