令和6年度春期 応用情報技術者試験 午前 問6
各ノードがもつデータを出力する再帰処理 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＋
解答・解説を見る
正解：エ
AI解説
定義された再帰処理f(ノードn)は、右の子→左の子の順に再帰呼出しを行い、両方(または存在する分)の子の処理が終わってから最後に自分自身のデータを出力する。つまり「右部分木→左部分木→自分自身」の順(右優先の後行順走査)で出力される点が、通常の左優先の後行順走査(後行順=左→右→根)と対称的な特徴になる。 ア: これは根を先に出力してから右部分木、左部分木の順にたどる走査(先行順走査に近い、根が最初に来る並び)の結果であり、設問の定義(自分自身の出力は子の処理が終わった後)と矛盾する。 イ: これは通常の後行順走査(左の子→右の子→自分自身の順)の結果であり、設問で定義された「右の子を先に処理する」という順序とは逆になっている。 ウ: これは中間順走査(行きがけ・通りがけの混在)に近い並びであり、設問で定義された「両方の子の処理を終えてから自分自身を出力する」規則とは異なる。 エ: 正しい。設問の定義どおり、各ノードで右の子→左の子の順に再帰処理を行い、子の処理が全て終わった後に自分自身のデータを出力すると、この選択肢の順列が得られる。 💡 この再帰定義は「右→左→自分」の順であり、通常の後行順走査(左→右→根)の左右を入れ替えたものに当たる。出力の最後に来る記号が根(演算子)である点は共通するので、まず根の記号が末尾にあるかを確認し、次に右部分木の結果が左部分木より先に来ているかを確認すると絞り込みやすい。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。