基本情報技術者試験 過去問解説
再帰とは？基本情報技術者試験 平成26年度 春期 午前 問6を解説
基本情報技術者試験 平成26年度 春期 午前 問6は、再帰に関する理解を問う問題です。検索から入っても、問題文、選択肢、正解、解説、各選択肢がなぜ違うかをこのページだけで確認できます。
問題文
2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は，次のとおりである。このプログラムを，図の2分木の根(最上位のノード)に適用したときの出力はどれか。 Proc(n) { n に左の子 l があれば Proc(l) を呼び出す。 n に右の子 r があれば Proc(r) を呼び出す。 n の記号を出力して終了する。 }
この問題の出題ポイント
- 再帰の定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
- データ構造分野では、用語の目的・主体・責任範囲の違いが選択肢で問われやすい。
- 関連タグ: 再帰。
選択肢
- ア+a*-bcd
- イa+b-c*d
- ウabc-d*+正解
- エb-c*d+a
正解
ウ: abc-d*+
解説
Proc は「左子→右子→自分」の順に処理する後行順(postorder)走査です。図の木(根+、左a、右*、*の左-、*の右d、-の左b、-の右c)を後行順でたどると、a、b、c、-、d、*、+ の順に出力されます。
なぜ他の選択肢が違うのか
ア
'+a*-bcd' は先行順(preorder: 自分→左→右)の結果に近く、後行順とは異なります。
イ
'a+b-c*d' は中間順(inorder: 左→自分→右)に近い並びで、後行順とは異なります。
ウ（正解）
後行順の正しい出力 abc-d*+ で、これは逆ポーランド記法(a + ((b-c) * d) に相当)になっています。
エ
'b-c*d+a' は走査順序として該当する標準的な木走査がなく、誤りです。
解き方の整理
再帰の問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。
関連問題
前後の問題
平成26年度 春期 午前 の関連する問題
復習を続ける
間違えた問題、苦手タグ、模試履歴を保存して復習する導線を用意しています。広告なしPro、弱点分析、復習リマインダーは段階的に提供予定です。