アルゴリズム (全80問中30問目)
No.30
2分木の各ノードがもつ記号を出力する再帰的なプログラムProc(n)の定義は，次のとおりである。このプログラムを，図の2分木の根(最上位のノード)に適用したときの出力はどれか。
Proc(ノードn){
nに左の子lがあればProc(l)を呼び出す
nに右の子rがあればProc(r)を呼び出す
nに書かれた記号を出力する
}
Proc(ノードn){
nに左の子lがあればProc(l)を呼び出す
nに右の子rがあればProc(r)を呼び出す
nに書かれた記号を出力する
}
出典：平成26年春期 問6
- ＋a*－bcd
- a＋b－c*d
- abc－d*＋
- b－c*d＋a
- [出題歴]
- 基本情報技術者 H19秋期 問12
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ウ
解説
与えられたプログラムを設問の2分木に適用すると次のようになります。
- 最初に2分木の根である"+"から始まります。
[proc(+)]
"+"の左には"a"があるので、Proc(a)が呼び出されます。 - [Proc(a)]
"a"の左右にはノードがないので、aを出力し、Proc(+)の処理に戻ります。 - "+"の右には"*"があるので、Proc(*)が呼び出されます。
- [Proc(*)]
"*"の左には"-"があるので、Proc(-)が呼び出されます。 - [Proc(-)]
"-"の左には"b"があるので、Proc(b)が呼び出されます。 - [Proc(b)]
"b"の左右にはノードがないので、bを出力し、Proc(-)の処理に戻ります。 - "-"の右には"c"があるので、Proc(c)が呼び出されます。
- [Proc(c)]
"c"の左右にはノードがないので、cを出力し、Proc(-)の処理に戻ります。 - Proc(-)は、-を出力し、Proc(*)に戻ります。
- "*"の右には"d"があるので、Proc(d)が呼び出されます。
- [Proc(d)]
"d"の左右にはノードがないので、dを出力し、Proc(*)の処理に戻ります。 - Proc(*)は、*を出力し、Proc(+)に戻ります。
- Proc(+)は、+を出力し、処理が終了します。