うごく基本情報

平成26年度 春期 問6

アルゴリズムとプログラミング › 木構造・ヒープ ○ 優先

出典:平成26年度 春期 基本情報技術者試験 午前 問6 の問題

出典:平成26年度 春期 基本情報技術者試験 午前 問6

正解と解説を見る

正解:ウ

覚えること:左の子 → 右の子 → 自分 の順に出力するのは後行順(帰りがけ順)。数式の木なら逆ポーランド記法になる。

Proc は左の子、右の子を処理してから自分の記号を出力するので、後行順の走査です。根の + では、まず左の a、次に右の * の部分木を処理します。* では左の − の部分木で b、c、− を出し、右の d を出してから * を出します。最後に + で、出力は abc−d*+ です(ウ)。アの +a*−bcd は自分を先に出す先行順、イの a+b−c*d は左・自分・右の順の中間順で出したものです。エは右の部分木を先に処理していて、どの順にも当たりません。

解説はこのサイトが作成したものです。