アルゴリズム(全100問中2問目)

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

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

出典：令和6年春期　問 6

  • ＋÷－ED×CBA
  • ABC×DE－÷＋
  • E－D＋C×B＋A
  • ED－CB×÷A＋
正解　エ問題へ
分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム
広告
解説
1.⇒2.⇒3.の流れより、f(ノードn)は、あるノードを右⇒左⇒中の順で走査していくものとわかります。子ノードがなくなった時点で自身のデータを出力するこのような探索方法は、後行順の深さ優先探索と呼ばれます。
  • 帰りがけ順(後行順) … 移動する子がなくなったタイミングで調べる。※下図は左⇒右⇒中なので設問とは逆向きです。
    06_1.gif
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