BohYoh.com《基本情報技術者試験》2007年度＝平成19年度・秋期午前問12

基本情報技術者試験

2007年度＝平成19年度・秋期

午前

問12

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

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

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

解答

エ

解説

　プログラムProc(ノードn )は、“左部分木→右部分木→ノードn ”という後順走査を行います。
　根に対してプログラムProc(ノードn )を適用すると、どのように表示が行われるのかを検討してみます。

　　　　＋　　　／　＼　　ａ　　　＊

したがって、表示の順は

　　ａ　　＊を根とする部分木　　＋

です。
　最初にａが表示され、最後に＋が表示される、という条件を満たす選択肢はエのみです。この段階で正解が導かれますので、これ以上の検討は不要です。