平成２０年度春期 基本情報 問１−２０ 解答編

基本情報

問１ １６ビットの２進数ｎを１６進数の各けたに分けて、下位のけたから順にスタックに格納するために、次の手順を４回繰り返す。ａ、ｂに入る適切な語句の組合せはどれか。ここでｘｘｘｘ16は１６進数ｘｘｘｘを表す。 [手順] (1) [ ａ ]をｘに代入する。 (2) ｘをスタックにプッシュする。 (3) ｎを[ ｂ ]論理シフトする。

解答 イ

解説 １６進数１桁は２進数４桁に相当します。よって、[ ａ ]で下位４ビットを取り出すために、０００Ｆ16でマスク処理をします。値を入れ終わったあとは、次の４ビットが最下位４ビットになるようにシフトをするので、右に４ビットシフトします。

問８ 標本相関係数がー０．９、−０．７、０．７、０．９のいずれかとなる標本の分布と回帰直線を表したグラフのうち、標本相関係数が−０．９のものはどれか。

解答 ウ

解説 散布図における相関係数は−１〜１の間の値をとります。−１は完全な負の相関。０は無相関。１は完全な正の相関となっています。下に散布図の例を示します。

問９ ｘ、ｙ、ｚを論理変数、Ｔを真、Ｆを偽とするとき、次の真理値表で示される関数ｆ（ｘ、ｙ、ｚ）を表す論理式はどれか。ここで、∧は論理積、∨は論理和、ＡはＡの否定を表す。

ア （ｘ∧ｙ）∨（ｙ∧ｚ） イ （ｘ∧ｙ）∨（ｙ∧ｚ） ウ （ｘ∧ｙ）∨（ｙ∧ｚ） エ （ｘ∧ｙ）∨（ｙ∧ｚ）

解答 イ

解説 まず、真となる出力の入力を書き出します。 �@ｘ∧ｙ∧ｚ �Aｘ∧ｙ∧ｚ �Bｘ∧ｙ∧ｚ �Cｘ∧ｙ∧ｚ つぎに、各式をまとめていきます。 �@と�Aをまとめてｘ∧ｙ �Bと�Cをまとめてｙ∧ｚ よって、これらの∨なので、（ｘ∧ｙ）∨（ｙ∧ｚ）となります。

問１２ 最下位のレベル以外の節点には必ず左右に子が存在する２分探索木から、あるデータを探索する。節点の総数が１５のとき、比較する節点の数は最大で幾つか。ここで、探索するデータが存在するとは限らないものとする。

ア ３ イ ４ ウ ７ エ １５

解答 イ

解説 まず、左図で木についてまとめます。そして、完全２分木とは右図のような特殊な木で、２分探索などに用いることができます。 節点が１５個ということは、深さが４であることがわかります。なので、３回の比較が必要となります。しかし、最終的に値が存在するかどうかも比較する必要があるので、４回の比較が必要となります。

問１４ キーｘのハッシュ関数としてｈ（ｘ）＝ｍｏｄ（ｘ、９７）を用いるとき、キー１０９４とハッシュ値が一致するものは、キー１〜１０００の中に幾つあるか。ここで、ｍｏｄ（ｘ、９７）はｘを９７で割った余りを表す。

ア ９ イ １０ ウ １１ エ １２

解答 ウ

解説 ハッシュとは、以下のようなデータ構造で、同じキー値になると衝突が起こります。 まず、１０９４ ｍｏｄ ９７＝２７。 １０００／９７＝１０余り３０なので、まずどんな値でも１０個は存在し、３０以下なら１１個存在するということになります。

問１５ 次の流れ図は、２数Ａ、Ｂの最大公約数を求めるユークリッドの互助法を、引き算の繰返しによって計算するものである。Ａが８７６、Ｂが２０４のとき、何回の比較で処理は終了するか。

ア ４ イ ９ ウ １０ エ １１

解答 エ

解説 順番に追いかけて行きます。 �@８７６−２０４＝６７２ �A６７２−２０４＝４６８ �B４６８−２０４＝２６４ �C２６４−２０４＝６０ �D２０４−６０＝１４４ �E１４４−６０＝８４ �F８４−６０＝２４ �G６０−２４＝３６ �H３６−２４＝１２ �I２４−１２＝１２ �J１２−１２＝０ よって、１２回の比較となります。

問１９ クロック周波数が１ＧＨｚのＣＰＵがある。このＣＰＵの命令種別が、表に示す二つからなっているとき、処理能力は約何ＭＩＰＳか。

ア ３４ イ １００ ウ １２５ エ １３３

解答 ウ

解説 まず、１命令あたりの平均クロック数をもとめます。 １０×０．６＋５×０．４＝６＋２＝８クロック よって、１ＧＨｚ／８＝０．１２５Ｇ命令＝１２５ＭＩＰＳ