令和6年春期試験問題 午前Ⅰ 問3
問3解説へ
各ノードがもつデータを出力する再帰処理 f(ノードn) を定義した。この処理を,図の2分木の根(最上位のノード)から始めたときの出力はどれか。
〔f(ノードn)の定義〕
〔f(ノードn)の定義〕
- ノードnの右に子ノードrがあれば,f(ノードr)を実行
- ノードnの左に子ノードlがあれば,f(ノードl)を実行
- 再帰処理 f(ノードr),f(ノードl) を未実行の子ノード,又は子ノードがなければ,ノード自身がもつデータを出力
- 終了
- +÷-ED×CBA
- ABC×DE-÷+
- E-D+C×B+A
- ED-CB×÷A+
正解 エ問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
広告
解説
1.⇒2.⇒3.の流れより、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+」となります。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(+)に戻る 左右の子は実行済みなので自身の値+を出力
広告