平成26年 春期 基本情報技術者 午前 問6

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

Proc(ノードn ) {
 n に左の子l があればProc(l )を呼び出す。
 n に右の子r があればProc(r )を呼び出す。
 n に書かれた記号を出力する
}

 ア  + a * - b c d
 イ  a + b - c * d
 ウ  a b c - d * +
 エ  b - c * d + a


答え ウ


解説
まず、問題の2分木の根であるノード『+』に対しプログラムProc( )を適用します。

@  ノード『+』は左の子『a』があるので、『a』に対しプログラムProc( )を適用します。
A  ノード『a』は子がないので、『a』を出力します。
B  ノード『+』の左の子の処理が終わったので、右の子の処理を行います。
ノード『+』は右の子『*』があるので、『*』に対しプログラムProc( )を適用します。
C  ノード『*』は左の子『-』があるので、『-』に対しプログラムProc( )を適用します。
D  ノード『-』は左の子『b』があるので、『b』に対しプログラムProc( )を適用します。
E  ノード『b』は子がないので、『b』を出力します。
F  ノード『-』の左の子の処理が終わったので、右の子の処理を行います。
ノード『-』は右の子『c』があるので、『c』に対しプログラムProc( )を適用します。
G  ノード『c』は子がないので、『c』を出力します。
H  ノード『-』の左右の子の処理が終わったので、『-』を出力します。
I  ノード『*』の左の子の処理が終わったので、右の子の処理を行います。
ノード『*』は右の子『d』があるので、『d』に対しプログラムProc( )を適用します。
J  ノード『d』は子がないので、『d』を出力します。
K  ノード『*』の左右の子の処理が終わったので、『*』を出力します。
L  ノード『+』の左右の子の処理が終わったので、『+』を出力します。
したがって、出力されるのはa b c - d * +(ウ)になります。


キーワード
・2分木

キーワードの解説

戻る 一覧へ 次へ