応用情報技術者試験令和6年春午前問6 解説付き過去問

問題

各ノードがもつデータを出力する再帰処理 f(ノードn) を定義した。この処理を、図の2分木の根(最上位のノード)から始めたときの出力はどれか。

〔f(ノードn)の定義〕

＋÷－ED×CBA

ABC×DE－÷＋

E－D÷C×B＋A

ED－CB×÷A＋

与えられた2分木に対して、再帰処理 f(ノードn) を実行したときの出力順序を求める。

再帰処理 f(ノードn) は、以下の手順で実行される。

再帰処理の手順
f(ノードn) は以下の流れで処理を行う。
- 右に子ノード r があれば、f(ノード r) を実行する。
- 左に子ノード l があれば、f(ノード l) を実行する。
- すべての子ノードの処理が完了したら、自身のデータを出力する。
問題の2分木の構造
問題の2分木は以下の構造である。
再帰処理の実行手順（詳細）
f(＋)から再帰処理を始めると、以下のような順序で進む。
- f(＋)の右の子「÷」を処理する。
  - f(÷)の右の子「－」を処理する。
    - f(－)の右の子「E」を処理 → Eを出力
    - f(－)の左の子「D」を処理 → Dを出力
    - 子ノード処理済のため、「－」を出力
  - f(÷)の左の子「×」を処理する。
    - f(×)の右の子「C」を処理 → Cを出力
    - f(×)の左の子「B」を処理 → Bを出力
    - 子ノード処理済のため、「×」を出力
  - 子ノード処理済のため、「÷」を出力
- f(＋)の左の子「A」を処理 → Aを出力
- 子ノード処理済のため、「＋」を出力
出力結果
以上の再帰処理から得られた出力順序は以下の通りである。
「E → D → － → C → B → × → ÷ → A → ＋」

したがって、正解は「ED－CB×÷A＋」である。

このように、本問題のアルゴリズムは通常の後行順とは逆の「右→左→根」の順序で処理が行われることが特徴である。