サンプル問題 科目B 問9
問題
次の記述中の [ ] に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
手続 order は，図の 2 分木の，引数で指定した節を根とする部分木をたどりながら，全ての節番号を出力する。大域の配列 tree が図の 2 分木を表している。配列tree の要素は，対応する節の子の節番号を，左の子，右の子の順に格納した配列である。例えば，配列 tree の要素番号 1 の要素は，節番号 1 の子の節番号から成る配列であり，左の子の節番号 2，右の子の節番号 3 を配列｛2，3｝として格納する。 手続 order を order(1)として呼び出すと， [ ] の順に出力される。
出典：情報処理技術者試験 サンプル問題
答えを予想する
これは二分木のトラバース（規則に従って木をなぞる）の問題です。プログラムで要素数が2のところを見ると、in-order traversal（指定されたノードの左のサブツリーのトラバースを行い、ノードの処理を行い、指定されたノードの右のサブツリーのトラバースを行う）であることがわかります。
ということは、答えはウになるはずです。
具体的に見ていく
関数の再帰呼び出しを順番に追いかけてみます。
- まず、order(1)として呼び出すと、tree[1]には要素が2つあるので、要素数が2のプログラムを実行します。
- すると、order関数を再帰的に呼び出します。order(tree[1][1])=order(2)の呼び出しです。
- 次にorder(2)を実行すると、tree[2]にも要素が2つあり、order(tree[2][1])=order(4)を呼び出します。
- order(4)を実行すると、これもtree[4]には要素が2つあり、order(tree[4][1])=order(8)を呼び出します。
- order(8)を実行すると、tree[8]は要素数が0なので、nを出力、を実行します。この場合、n=8なので8を出力します。このように、最初に出力する数は8です。これでorder(8)の実行は終わりです。
- order(8)の実行が終わればorder(4)に戻って実行を継続します。今度はnを出力で、n=4であり、4を出力します。2番目に出力する数は4です。
- order(4)は最後にorder(tree[4][2])=order(9)を呼び出します。
- order(9)を実行すると、これもtree[9]の要素数は0なので、nを出力を実行して、9を出力します。3番目に出力する数は9です。これでorder(9)の実行は終わりです。
- order(4)の実行が完了したので、次にorder(2)の続きに戻って実行を継続します。今度はnを出力で、n=2であり、2を出力します。4番目に出力する数は2です。
この後は省略しますが、ここまでの出力は、8, 4, 9, 2です。これは回答群のウと一致します。
答え
ウ
