令和6年春期試験問題 午前Ⅰ 問3

各ノードがもつデータを出力する再帰処理 f(ノードn) を定義した。この処理を,図の2分木の根(最上位のノード)から始めたときの出力はどれか。

〔f(ノードn)の定義〕
  1. ノードnの右に子ノードrがあれば,f(ノードr)を実行
  2. ノードnの左に子ノードlがあれば,f(ノードl)を実行
  3. 再帰処理 f(ノードr),f(ノードl) を未実行の子ノード,又は子ノードがなければ,ノード自身がもつデータを出力
  4. 終了

  • +÷-ED×CBA
  • ABC×DE-÷+
  • E-D+C×B+A
  • ED-CB×÷A+
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
1.⇒2.⇒3.の流れより、f(ノードn)は、あるノードを右⇒左⇒中の順で走査していくものとわかります。子ノードがなくなった時点で自身のデータを出力するこのような探索方法は、後行順の深さ優先探索と呼ばれます。
  • 帰りがけ順(後行順) … 移動する子がなくなったタイミングで調べる。※下図は左⇒右⇒中なので設問とは逆向きです。
f(ノードn) を根ノードから始めた場合、再帰処理は次のように進んでいきます。
f(+) 右の子があるので f(÷) を実行
 f(÷) 右の子があるので f(-) を実行
  f(-) 右の子があるので f(E) を実行
   f(E) 子がないのでEを出力
  f(-)に戻る 左の子があるので f(D) を実行
   f(D) 子がないのでDを出力
   EDと続いたので、この時点で解答が確定します
  f(-)に戻る 左右の子は実行済みなので自身の値を出力
 f(÷)に戻る 左の子があるので f(×) を実行
  f(×) 右の子があるので f(C) を実行
   f(C) 子がないのでCを出力
  f(×)に戻る 左の子があるので f(B) を実行
   f(B) 子がないのでBを出力
  f(×)に戻る 左右の子は実行済みなので自身の値×を出力
 f(÷)に戻る 左右の子は実行済みなので自身の値÷を出力
f(+)に戻る 左の子があるので f(A) を実行
 f(A) 子がないのでAを出力
f(+)に戻る 左右の子は実行済みなので自身の値を出力
したがって出力は「ED-CB×÷A+」となります。

Pagetop