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

問題本文

各ノードがもつデータを出力する再帰処理 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＋

解説

この再帰処理は、右の子→左の子を先に処理し、子をすべて処理し終えてから自ノードを出力する。すなわち左右を逆順に巡る後行順（帰りがけ順）で、結果は逆ポーランド記法に近い形になる。図の木に適用すると、×の部分木からED−、CB×、それを÷でまとめ、最後にAと＋で結合し、ED−CB×÷A＋となりエが正解。木の走査順序の理解が問われる。

選択肢ごとの解説

• ア.演算子が先頭に来る前置記法に近い並びで、自ノードを最後に出力する定義と一致せず誤り。
• イ.左の子を先に処理した場合の並びで、右の子を先に処理する定義に反し誤り。
• ウ.中置記法に近い順で、子をすべて処理してから出力する後行順と一致せず誤り。
• エ.右→左→自ノードの順で巡った後行順の出力で、定義どおりであり正解。