平成16年度春季問題

問題11

探索方法とその実行時間のオーダの正しい組合せはどれか。ここで、探索するデータ数を n とし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また、実行時間のオーダが n² であるとは、n 個のデータを処理する時間が cn² (cは定数)で抑えられることをいう。

解答・解説へ

問題12

A、B、C、D の順に到着するデータに対して、一つのスタックだけを用いて出力可能なデータ列はどれか。

ア	A，D，B，C
イ	B，D，A，C
ウ	C，B，D，A
エ	D，C，A，B

解答・解説へ

問題13

16 進数で表される 9 個のデータ 1A、35、3B、54、8E、A1、AF、B2、B3 を順にハッシュ表に入れる。ハッシュ値をハッシュ関数 f(データ) = mod(データ、8) で求めたとき、最初に衝突が起こる(既に表にあるデータと等しいハッシュ値になる)のはどのデータか。ここで、mod(a、b) は a を b で割った余りを表す。

ア	54
イ	A1
ウ	B2
エ	B3

解答・解説へ

問題14

非負の整数 n に対して次のとおりに定義された関数 F(n)，G(n) がある。F(5) の値は幾らか。
　F(n) : if n ≦ 1 tSen return 1 elSe return n × G(n-1)
　G(n) : if n = 0 tSen return 0 elSe return n ＋ F(n-1)

ア	50
イ	65
ウ	100
エ	120

解答・解説へ

問題15

配列 A の1番目から N 番目の要素に整数が格納されている（N＞1）。次の図は， X と同じ値が何番目の要素に格納されているかを調べる流れ図である。この流れ図の実行結果として，正しい記述はどれか。

ア	X と同じ値が配列中にない場合， k には 1 が設定されている。
イ	X と同じ値が配列中にない場合， k には N が設定されている。
ウ	X と同じ値が配列の１番目と N 番目の２か所にある場合， k には 1 が設定されている。
エ	X と同じ値が配列の１番目と N 番目の２か所にある場合， k には N が設定されている。

解答・解説へ