平成20年度春季解答

問題11

次の BNF で定義されるビット列 S であるものはどれか。

　　＜S＞ ::＝ 01 | 0 ＜S＞ 1

ア	000111
イ	010010
ウ	010101
エ	011111

解答：ア

＜解説＞

BNF(バッカス・ナウア記法)とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。
BNFでは、「＜S＞::＝」はS を定義するという意味で、「｜」は、「または」を意味する。

これより

1. 最後尾ビットは1になる
2. 0の個数と1の個数は同じになる
3. 01以外は0の右には0が続き，1の左には1が続く

事が分かる。

ア	○
イ	×	1及び3の条件に当てはまらない。
ウ	×	3の条件に当てはまらない。
エ	×	2の条件に当てはまらない。

問題へ

問題12

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

ア	3
イ	4
ウ	7
エ	15

解答：イ

＜解説＞

最下位のレベル以外の節点には必ず左右に子が存在する節点の総数が15個の2分探索木の比較回数は，次の図のようになる。

問題へ

問題13

データの整列方法に関する記述のうち，適切なものはどれか。

ア	クイックソートでは，ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が１になるまでこれを繰り返す。
イ	シェルソートでは，隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返して行う。
ウ	バブルソートでは，中間的な基準値を決めて，それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。
エ	ヒープソートでは，未整列の部分を順序木に構成し，そこから最大値又は最小値を取り出して既整列の部分に移す。これらの操作を繰り返して，未整列部分を縮めていく。

解答：エ

＜解説＞

ア	×	シェルソートでは，ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が１になるまでこれを繰り返す。
イ	×	バブルソートでは，隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返して行う。
ウ	×	クイックソートでは，中間的な基準値を決めて，それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。
エ	○	ヒープソートでは，未整列の部分を順序木に構成し，そこから最大値又は最小値を取り出して既整列の部分に移す。これらの操作を繰り返して，未整列部分を縮めていく。

問題へ

問題14

キーｘのハッシュ関数として h(x)＝mod（x，97）を用いるとき，キー 1094 とハッシュ値が一致するものは，キー １～1000 の中に幾つあるか。ここで，mod（x，97)はx を 97 で割った余りを表す。

ア	9
イ	10
ウ	11
エ	12

解答：ウ

＜解説＞

1. 1094のハッシュ値を求める
   h(1094)＝mod(1094，97)＝27になる。
2. 1から1000のうち、97で割った余りが27になるものを探す。
   商が0、余りが27，商が1、余りが27，商が2、余りが27・・・・，商が10、余りが27
3. 商が0から10まで全部で11個ある。

問題へ

問題15

次の流れ図は，2数 A，B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。 A が 876 ，B が 204 のとき，何回の比較で処理は終了するか。

ア	4
イ	9
ウ	10
エ	11

解答：エ

＜解説＞

トレースすると次のようになる。比較回数は11回なので、エが正解である。

問題へ