重要度：A 論点：アルゴリズムとプログラミング
問61：処理時間がn×log2nに比例するアルゴリズムがある。n＝1,024のときと比べて、n＝2,048のときの処理時間はおよそ何倍になるか。
- A：1.1
- B：2.2
- C：4
- D：11
【第61問：正解と解説】
正解：B
・A
1.1倍は、対数部分の比11÷10だけを用い、データ件数が2倍になることを考慮していない。
・B
正解。1,024＝2の10乗、2,048＝2の11乗である。比は（2,048×11）÷（1,024×10）＝2×11÷10＝2.2倍となる。
・C
4倍は、処理時間がnの2乗に比例する場合の倍率である。
・D
11倍は、log2 2,048の値をそのまま倍率とした誤りである。
重要度：A 論点：アルゴリズムとプログラミング
問62：値50を根とし、左部分木に30、その子に20と40、右部分木に70、その子に60と80をもつ2分探索木がある。この木を中間順（左部分木、根、右部分木の順）で巡回したときの値の並びはどれか。
- A：20，30，40，50，60，70，80
- B：50，30，20，40，70，60，80
- C：20，40，30，60，80，70，50
- D：50，70，80，60，30，40，20
【第62問：正解と解説】
正解：A
・A
正解。2分探索木を中間順で巡回すると、左部分木、根、右部分木の順に訪れるため、値は昇順の20，30，40，50，60，70，80となる。
・B
50から始まる並びは、根を先に訪れる先行順に近い。
・C
各部分木の子を訪れる順序と根を訪れる位置が中間順になっていない。
・D
右部分木を先に訪れており、中間順ではない。
重要度：B 論点：アルゴリズムとプログラミング
問63：整列されていない1,000件のデータから線形探索で目的のデータを1件探すとき、平均の比較回数はおよそ何回か。ここで、目的のデータは必ず存在するものとする。
- A：10
- B：100
- C：500
- D：1000
【第63問：正解と解説】
正解：C
・A
10回は、2分探索を行った場合の最大比較回数に近い値である。
・B
100回は、データ件数の10分の1に当たる値であり、平均比較回数ではない。
・C
正解。目的データが1,000個の各位置に同じ確率で存在すると仮定すると、平均比較回数は（1＋1,000）÷2＝500.5回であり、およそ500回である。
・D
1000回は、最後の1件で見つかる最悪の場合の比較回数である。
重要度：B 論点：アルゴリズムとプログラミング
問64：バブルソートで、n件のデータを整列するときの比較回数はn×（n−1）÷2回である。10件のデータを整列するときの比較回数は何回か。
- A：20
- B：45
- C：50
- D：90
【第64問：正解と解説】
正解：B
・A
20回は、件数の2倍を求めた誤りである。
・B
正解。10×（10−1）÷2＝10×9÷2＝45回である。
・C
50回は、10の2乗を2で割った概算値であり、式に正しく当てはめていない。
・D
90回は、2で割る操作を行わずに10×9で求めた値である。
重要度：B 論点：アルゴリズムとプログラミング
問65：次のように定義された関数Gがある。G(7)の値は幾らか。G(n)：nが0以下のときは0を返し、それ以外のときはn＋G(n－2)を返す。
- A：12
- B：16
- C：21
- D：28
【第65問：正解と解説】
正解：B
・A
12は、7＋5だけを計算し、その後の再帰呼出しを省略した値である。
・B
正解。G(7)＝7＋G(5)＝7＋5＋G(3)＝7＋5＋3＋G(1)＝7＋5＋3＋1＋G(－1)＝16である。
・C
21は1から6までの和であり、この再帰式の結果ではない。
・D
28は1から7までの全ての整数の和であり、2ずつ減る再帰式を反映していない。
コメント