平成20年度春季問題

問題11

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

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

ア	000111
イ	010010
ウ	010101
エ	011111

解答・解説へ

問題12

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

ア	3
イ	4
ウ	7
エ	15

解答・解説へ

問題13

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

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

解答・解説へ

問題14

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

ア	9
イ	10
ウ	11
エ	12

解答・解説へ

問題15

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

ア	4
イ	9
ウ	10
エ	11

解答・解説へ