修了試験 2022-06-12実施分 基本情報技術者試験 問7

解説

正解は3です。 Proc(n)は、左の子、右の子の順に処理してから自分の記号を出力します。 このように子を先に処理して最後に親を出力するたどり方を、後行順（帰りがけ順）の走査といいます。 図の2分木は、根が＋で、その左の子がa、右の子が＊です。 ＊の左の子は－で、－の左の子がb、右の子がcです。 ＊の右の子はdです。 【処理のたどり方】 根の＋から始め、まず左の子aを処理し、子がないのでaを出力します。 次に＋の右の子＊に進み、その左の子－に進みます。 －の左の子bを出力し、右の子cを出力したあと、－を出力します。 続いて＊の右の子dを出力し、その後に＊を出力します。 最後に根の＋を出力して終了します。 出力の並びは abc－d＊＋ です。 【選択肢別解説】 1：× ＋a＊－bcdは、親を先に出力する先行順（行きがけ順）の結果です。 Proc(n)は自分の記号を最後に出力するので当てはまりません。 2：× a＋b－c＊dは、左の子、親、右の子の順に出力する中間順の結果です。 これは通常の数式の書き方に当たります。 3：○ abc－d＊＋は、左の子と右の子を処理してから親を出力する後行順の結果です。 上でたどった順序と一致します。 4：× b－c＊d＋aは、どの標準的な走査順にも一致しない並びです。 根の左の子aが最初に出力されていない点からも誤りと分かります。 【ポイント】 数式の木を後行順にたどると逆ポーランド記法になり、先行順にたどるとポーランド記法になります。 「自分の記号をいつ出力するか」を見れば、どの走査順かを判断できます。