応用情報技術者試験 応用情報技術者試験 令和6年度春期 午前 問6: 各ノードがもつデータを出力する再帰処理 f(ノード n) を定義した。この処理を，図の 2 分木の根（最上位のノード）から始めたときの出力はどれか。 〔f(ノー

問題本文

各ノードがもつデータを出力する再帰処理 f(ノード n) を定義した。この処理を，図の 2 分木の根（最上位のノード）から始めたときの出力はどれか。 〔f(ノード n)の定義〕 1．ノード n の右に子ノード r があれば，f(ノード r) を実行 2．ノード n の左に子ノード l があれば，f(ノード l) を実行 3．再帰処理 f(ノード r)，f(ノード l) を未実行の子ノード，又は子ノードがなければ，ノード自身がもつデータを出力 4．終了

選択肢

• ア.＋÷−ED×CBA
• イ.ABC×DE−÷＋
• ウ.E−D÷C×B＋A
• エ.ED−CB×÷A＋

正解

エ. ED−CB×÷A＋

解説

この再帰処理は「右の子→左の子→自分自身」の順に処理するため、左右を入れ替えた後行順(帰りがけ順)の走査となり、出力は逆ポーランド記法を右優先で並べた形になる。木は根＋の左にA・右に÷、÷の左に×(子B,C)・右に−(子D,E)である。根から右優先でたどると、÷の右の−を先に処理して E,D,− を出力、次に÷の左の×で C,B,× を出力、続いて÷を出力、最後に根の左のA、根の＋を出力する。結果として ED−CB×÷A＋ となり、エが正解である。