平成17年度春季解答

問題11

図は1の数が偶数個のビット列を受理するオートマトンの状態遷移図であり，“偶”と書かれた二重丸が受理状態を表す。a，b の正しい組合せはどれか。

解答：ウ

＜解説＞

空欄aの遷移は、1の個数が奇数個から偶数個への遷移なので1である。

空欄bの遷移は、1の個数が奇数個から奇数個への遷移なので0である

問題へ

問題12

2分探索木として適切なものはどれか。ここで，1～9の数字は，各ノード（節）の値を表す。

解答：イ

＜解説＞

2分探索木では、すべての節点において、節点の値の関係が「左の子の値<親の子の値<右の子の値」となる。

以下の図において、赤丸の部分の値の関係が「左の子の値<親の子の値<右の子の値」となっていない。よってイが正解である。

問題へ

問題13

PUSH 命令でスタックにデータを入れ，POP 命令でスタックからデータを取り出す。動作中のプログラムにおいて，ある状態から次の順で 10 個の命令を実行したとき，スタックの中のデータは図のようになった。１番目のPUSS命令でスタックに入れたデータはどれか。

ア	7
イ	29
ウ	55
エ	326

解答：ア

＜解説＞

実行した処理を「PUSH a → PUSH b → POP → PUSH c → PUSH d → PUSH e → PUSH f → POP → POP → PUSH g」として、スタックの状態を考える。
(※開始時、スタックは空とする。)

1. PUSH aでスタックは[a]
2. PUSH bでスタックは[b, a]
3. POPでスタックからデータbを取り出し[a]
4. PUSH cでスタックは[c, a]
5. PUSH dでスタックは[d, c, a]
6. PUSH eでスタックは[e, d, c, a]
7. PUSH fでスタックは[f, e, d, c, a]
8. POPでスタックからデータfを取り出し[e, d, c, a]
9. POPでスタックからデータeを取り出し[d, c, a]
10. PUSH gでスタックは[g, d, c, a]

したがって、最初にPUSHしたデータはスタックの上から4番目のaなのでイが正解である。

問題へ

問題14

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

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

解答：エ

＜解説＞

ア	→×	シェルソートに関する説明である。
イ	→×	バブルソートに関する説明である。
ウ	→×	クイックソートに関する説明である。
エ	→○	ヒープソートに関する説明である。

問題へ

問題15

2分探索において、データの個数が4倍になると、最大探索回数はどうなるか。

ア	1回増える。
イ	2回増える。
ウ	約2倍になる。
エ	約4倍になる。

解答：イ

＜解説＞

データの個数がN個から4倍の4N個になった場合、2分探索の最大探索回数はlog₂Nからlog₂4Nになるので2回増えることになる。

問題へ