平成16年度春季解答

問題11

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

解答：ア

＜解説＞

2分探索

予めソートされたデータ列を二つに分けて、そのどちらに検索対象が含まれているか判断するという手順を再帰的に繰り返していく検索方法。
実行時間のオーダ＝log_２n

線形探索

対象データを検索範囲のデータと先頭から順に1つずつ比較し、一致するものを検索する方法。
実行時間のオーダ＝n

ハッシュ探索

キーの値を基に格納先（記録媒体上）のアドレスを算出し、そのアドレス位置にあるデータを検索する方法。
実行時間のオーダ＝1/dd>

よって正解は、アである

問題へ

問題12

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

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

解答：ウ

＜解説＞

スタックとは、ある場所に格納したデータを、新しく格納した順に取り出すようにする方式。一番古く格納されたデータが一番最後に取り出される、LIFO型のバッファのこと。

問題へ

問題13

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

ア	54
イ	A1
ウ	B2
エ	B3

解答：ウ

＜解説＞

1A，35，3B，54，8E，A1，AF，B2，B3を16進数から10進数に基数変換し、ハッシュ値を求める。
最初に衝突が起こる(既に表にあるデータと等しいハッシュ値になる)のは、B2である。
よって正解はウである。

問題へ

問題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

解答：イ

＜解説＞

F(5)	=	5 × G(4)
	=	5 × (4 ＋ F(3))
	=	5 × (4 ＋ 3 × G(2))
	=	5 × (4 ＋ 3 × (2 ＋ F(1)))
	=	5 × (4 ＋ 3 × (2 ＋ 1))
	=	5 × (4 ＋ 3 × 3)
	=	5 × (4 ＋ 9)
	=	5 × 13
	=	65

問題へ

問題15

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

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

解答：ウ

＜解説＞

与えられたアルゴリズムは線形探索法である。

これは、配列の先頭から順に比較を行っていく探索法であり、k は現在着目している配列要素の添字で、1, 2, …と増えていく。 X と同じ値が配列中にない場合、配列の最後の要素A (N )がX と等しいかどうかを判断した後に、k の値は、一つ増やされてN + 1となる。したがって、アおよびイは誤りである。。
この線形探索では、X と等しい要素を見つけたときに終了する。したがって、X と同じ値が配列の1番目とN 番目にある場合は、先頭側の1を見つけたときに終了するので、k の値は1となる。

よって正解はウである。

問題へ