基本情報技術者試験 基本情報技術者試験 平成26年度 春期 午前 午前 問6: 2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は，次のとおりである。このプログラムを，図の2分木の根(最上位のノード)に適用した

問題本文

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

選択肢

• ア.+a-bcd
• イ.a+b-cd
• ウ.abc-d+
• エ.b-cd+a

正解

ウ. abc-d+

解説

Proc は「左子→右子→自分」の順に処理する後行順(postorder)走査です。図の木(根+、左a、右、の左-、の右d、-の左b、-の右c)を後行順でたどると、a、b、c、-、d、、+ の順に出力されます。

選択肢ごとの解説

• ア.'+a-bcd' は先行順(preorder: 自分→左→右)の結果に近く、後行順とは異なります。
• イ.'a+b-cd' は中間順(inorder: 左→自分→右)に近い並びで、後行順とは異なります。
• ウ.後行順の正しい出力 abc-d+ で、これは逆ポーランド記法(a + ((b-c) d) に相当)になっています。
• エ.'b-cd+a' は走査順序として該当する標準的な木走査がなく、誤りです。