問題プレビューID: 1b210eb8基本情報技術者試験 午前免除試験 2016年12月11日

問 5
基本情報技術者試験 午前免除試験 2016年12月11日

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

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

正解は「ウ」です。

このプログラムは,左の子,右の子の順に再帰呼出しを行った後で自分自身の記号を出力するため,木を「左部分木 → 右部分木 → 根」の順にたどる後行順(帰りがけ順)の走査になります。

  • 根 + の左の子 a を処理して a を出力します。
  • 根 + の右の子 * の左の子 − をたどり,その左 b,右 c を出力してから − を出力します(b c −)。
  • * の右の子 d を出力してから * を出力します(b c − d *)。
  • 最後に根 + を出力します(a b c − d * +)。

以上より,出力は「abc−d*+」です。

関連問題

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