修了試験 2016-12-11実施分 基本情報技術者試験 問5

解説

正解は3です。 再帰プログラムProc(n)が、2分木をどの順序でたどるかを問う問題です。 Proc(n)は「左の子を処理」「右の子を処理」「自分の記号を出力」の順なので、後行順（帰りがけ順、postorder）の走査です。 図の2分木は、根が＋、＋の左の子がa、右の子が＊です。 ＊の左の子が－、右の子がdで、－の左の子がb、右の子がcです。 【計算】 根の＋では、まず左の子aを処理し、aには子がないので「a」を出力します。 次に＋の右の子＊を処理します。 ＊では左の子－を処理し、－の左のbで「b」、右のcで「c」を出力します。 その後、－自身の「－」を出力します。 続いて＊の右の子dで「d」を出力し、＊自身の「＊」を出力します。 最後に根の「＋」を出力します。 出力は「abc－d＊＋」になります。 【選択肢別解説】 1：× 「＋a＊－bcd」は、自分を先に出力してから左右の子を処理する先行順（行きがけ順）の結果です。 2：× 「a＋b－c＊d」は、左の子・自分・右の子の順に出力する中間順（通りがけ順）の結果です。 3：○ 左の子、右の子、自分の順に出力する後行順の結果で、「abc－d＊＋」となります。 4：× 「b－c＊d＋a」は、右部分木を先に中間順で出力し、その後に根と左の子を出力した並びです。 Proc(n)の定義ではこの順序になりません。 【ポイント】 後行順で式の木をたどると、逆ポーランド記法（後置記法）が得られます。 先行順はポーランド記法（前置記法）、中間順は通常の中置記法に対応します。