基本情報技術者講座

★　猫本　4-09　プログラムの属性(その3)　★

基本情報技術者　令和4年度6月免除　問7

2分木の各ノードがもつ記号を出力する再帰的なプログラムProc(n)の定義は，次のとおりである。このプログラムを，図の2分木の根(最上位のノード)に適用したときの出力はどれか。

Proc(n){

　nに左の子lがあればProc(l)を呼び出す。

　nに右の子rがあればProc(r)を呼び出す。

　nの記号を出力して終了する。

}

ア	＋a*－bcd
イ	a＋b－c*d
ウ	abc－d*＋
エ	b－c*d＋a

解説

(頭の準備体操)

再帰的：「手続の内部から自分自身を呼び出すことができる。」(FE27.1.07)

(イメージで解く)

①Proc(+)

+に，左の子aがあるので，Proc(a)を呼び出す。

②Proc(a)

aに，左の子，右の子がないので，aを出力して，Proc(+)に戻る。

③Proc(+)，左の子の処理は終了済み

+に，右の子*があるので，Proc(*)を呼び出す。

④Proc(*)

*に，左の子-があるので，Proc(-)を呼び出す。

⑤Proc(-)

-に，左の子bがあるので，Proc(b)を呼び出す。

⑥Proc(b)

bに，左の子，右の子がないので，bを出力して。Proc(-)に戻る。

⑦Proc(-)，左の子の処理は終了済み

-に，右の子cがあるので，Proc(c)を呼び出す。

⑧Proc(c)

cに，左の子，右の子がないので，cを出力して，Proc(-)に戻る。

⑨Proc(-)，左の子，右の子の処理が終了済み

-を出力して，Proc(*)に戻る。

⑩Proc(*)，左の子の処理は終了済み

*に，右の子dがあるので，Proc(d)を呼び出す。

⑪Proc(d)

dに，左の子，右の子がないので，dを出力して，Proc(*)に戻る。

⑫Proc(*)，左の子，右の子の処理が終了済み

*を出力して，Proc(+)に戻る。

⑬Proc(+)，左の子，右の子の処理が終了済み

+を出力して終了する。

よって，ウである。

解答
ウ