アルゴリズム(全79問中52問目)

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
2分木の各ノードがもつ記号を出力する再帰的なプログラムProc(ノードn)は,次のように定義される。このプログラムを,図の2分木の根(最上位のノード)に適用したときの出力はどれか。

Proc(ノードn){
 nに左の子lがあればProc(l)を呼び出す
 nに右の子rがあればProc(r)を呼び出す
 nに書かれた記号を出力する
}
12.gif

出典:平成19年秋期 問12

  • b-c*d+a
  • +a*-bcd
  • a+b-c*d
  • abc-d*+
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
与えられたプログラムを設問の2分木に適用すると次のようになります。
  1. 最初に2分木の根である"+"から始まります。
    [proc(+)]
    "+"の左には"a"があるので、Proc(a)が呼び出されます。
  2. [Proc(a)]
    "a"の左右にはノードがないので、aを出力し、Proc(+)の処理に戻ります。
  3. "+"の右には"*"があるので、Proc(*)が呼び出されます。
  4. [Proc(*)]
    "*"の左には"-"があるので、Proc(-)が呼び出されます。
  5. [Proc(-)]
    "-"の左には"b"があるので、Proc(b)が呼び出されます。
  6. [Proc(b)]
    "b"の左右にはノードがないので、bを出力し、Proc(-)の処理に戻ります。
  7. "-"の右には"c"があるので、Proc(c)が呼び出されます。
  8. [Proc(c)]
    "c"の左右にはノードがないので、cを出力し、Proc(-)の処理に戻ります。
  9. Proc(-)は、-を出力し、Proc(*)に戻ります。
  10. "*"の右には"d"があるので、Proc(d)が呼び出されます。
  11. [Proc(d)]
    "d"の左右にはノードがないので、dを出力し、Proc(*)の処理に戻ります。
  12. Proc(*)は、*を出力し、Proc(+)に戻ります。
  13. Proc(+)は、+を出力し、処理が終了します。
出力された記号を順番に並べると「abc-d*+」になります。
12a.gif

この問題の出題歴


Pagetop