基本情報技術者試験 基本情報技術者試験 平成26年度 春期 午前 午前 問6: 2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は，次のとおりである。このプログラムを，図の2分木の根(最上位のノード)に適用した
←
基本情報技術者試験 平成26年度 春期 午前
Q 66 / 80
2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は，次のとおりである。このプログラムを，図の2分木の根(最上位のノード)に適用したときの出力はどれか。
Proc(n) {
n に左の子 l があれば Proc(l) を呼び出す。
n に右の子 r があれば Proc(r) を呼び出す。
n の記号を出力して終了する。
}
この問の正解率:42.48%(1,728件)
解説
基本情報技術者試験 平成26年度 春期 午前 問6「2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は…」の正解と解説です。基本情報技術者試験の「データ構造」分野の過去問で、これまでの受験者の正答率は約42%です。
正解
ウ. abc-d+
正答率 42.5%（1,728人中 734人が正解）
問題の解説
Proc は「左子→右子→自分」の順に処理する後行順(postorder)走査です。図の木(根+、左a、右、の左-、の右d、-の左b、-の右c)を後行順でたどると、a、b、c、-、d、、+ の順に出力されます。
選択肢ごとの解説
- ア'+a-bcd' は先行順(preorder: 自分→左→右)の結果に近く、後行順とは異なります。
- イ'a+b-cd' は中間順(inorder: 左→自分→右)に近い並びで、後行順とは異なります。
- ウ後行順の正しい出力 abc-d+ で、これは逆ポーランド記法(a + ((b-c) d) に相当)になっています。
- エ'b-cd+a' は走査順序として該当する標準的な木走査がなく、誤りです。
基本情報技術者試験 の iOS アプリ版
アプリ版なら、よりスムーズに動作し、
スワイプで問題遷移ができます。
