問題プレビューID: 7b045bd9基本情報技術者試験 午前免除試験 2022年6月12日

問 7
基本情報技術者試験 午前免除試験 2022年6月12日

2 分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は,次のとおりである。このプログラムを,図の 2 分木の根(最上位のノード)に適用したときの出力はどれか。

Proc(n) {
  n に左の子 l があれば Proc(l) を呼び出す。
  n に右の子 r があれば Proc(r) を呼び出す。
  n の記号を出力して終了する。
}

図の 2 分木は,根が + であり,その左の子は a,右の子は * である。* の左の子は -,右の子は d であり,- の左の子は b,右の子は c である。

解説

正解は「ウ」です。

Proc(n) は,左部分木,右部分木の順にたどってから自分の記号を出力する後置記法(帰りがけ順)の処理です。根 + に適用すると次の順になります。

  1. 左の子 a を処理 → a を出力
  2. 右の子 * を処理
    • その左の子 - を処理 → b,c を出力してから - を出力(bc-)
    • その右の子 d を処理 → d を出力
    • 最後に * を出力(bc-d*)
  3. 最後に + を出力

したがって出力は abc-d*+ となり,「ウ」が正解です。

  • ア: 前置記法(行きがけ順)の出力です。
  • イ・エ: 中置記法など,たどる順序が異なる出力です。

関連問題

本文が同じ・似ている問題を表示しています