平成17年度秋季解答

問題11

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

解答：ア

＜解説＞

2分探索

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

線形探索

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

ハッシュ探索

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

よって正解は、アである

問題へ

問題12

すべての葉が同じ深さをもち，葉以外のすべての節点が二つの子をもつ2分木に関して，節点数と深さの関係を表す式はどれか。ここで， n は節点数， k は根から葉までの深さを表す。例に示す2分木の深さ k は2である。

ア	n ＝ k (k＋1)＋1
イ	n ＝ 2k＋3
ウ	n ＝ 2k+1－1
エ	n ＝ (k－1)(k＋1)＋4

解答：ウ

＜解説＞

k は根から葉までの深さ k と節点数 n は、次のようになる。

• n ＝０……………１
• n ＝１……………３（１＋２）
• n ＝２……………７（１＋２＋４）
• n ＝３……………１５（１＋２＋４＋８）

よって、 n ＝ 2^k+1－1　となる。

問題へ

問題13

データ構造に関する記述のうち、適切なものはどれか。

ア	2分木は、データ間の関係を階層的に表現する木構造の一種であり、すべての節が二つの子をもつデータ構造である。
イ	スタックは、最初に格納したデータを最初に取り出す先入れ先出しのデータ構造である。
ウ	線形リストは、データ部と次のデータの格納先を指すポインタ部から構成されるデータ構造である。
エ	配列は、ポインタの付替えだけでデータの挿入・削除ができるデータ構造である。

解答：ウ

＜解説＞

ア	×	2分木は、すべての節が必ずしも二つの子をもつとは限らない。
イ	×	キューは、最初に格納したデータを最初に取り出す先入れ先出し（FIFO：Fast In Fast Out）のデータ構造である。 スタック(stack)は，最後に格納したデータを最初に取り出す後入れ先出し（LIFO：Last In First Out）のデータ構造である。
ウ	○	線形リストは、データ部と次のデータの格納先を指すポインタ部から構成されるデータ構造である。
エ	×	リストは、ポインタの付替えだけでデータの挿入・削除ができるデータ構造である。配列(array)は，添字によってデータを任意の順序で読み出しや書き込みができるデータ構造である。

問題へ

問題14

2分探索に関する記述のうち、適切なものはどれか。

ア	2分探索するデータ列は整列されている必要がある。
イ	2分探索は線形探索より常に速く探索できる。
ウ	2分探索は探索をデータ列の先頭から開始する。
エ	n 個のデータﾌデータの探索に要する比較回数は、 n log2 n に比例する。

解答：ア

＜解説＞

ア	○	2分探索するデータ列は整列されている必要がある。
イ	×	データ数が少ない場合は線形探索の方が早い。
ウ	×	探索をデータ列の先頭から開始するのは，線形探索。2分探索はデータ列を2分した中央のデータと比較する。
エ	×	n 個のデータﾌデータの探索に要する比較回数は、log2nに比例する。

問題へ

問題15

次の関数 f (n, k) がある。 f (4, 2) の値は幾らか。

ア	3
イ	4
ウ	5
エ	6

解答：エ

＜解説＞

f(4，2)	＝	f(4-1，2-1)＋f(4-1，2)
	＝	f(3，1)＋f(3，2)
	＝	f(3-1，1-1)＋f(3-1，1)＋f(3-1，2-1)＋f(3-1，2)
	＝	f(2，0)＋f(2，1)＋f(2，1)＋f(2，2)
	＝	1＋f(2-1，1-1)＋f(2-1，1)＋f(2-1，1-1)＋f(2-1，1)＋1
	＝	2＋f(1，0)＋f(1，1)＋f(1，0)＋f(1，1)
	＝	2＋1＋1＋1＋1
	＝	6

よってエが正解である。

問題へ