令和6年度 春期 ITストラテジスト試験 システムアーキテクト試験 ネットワークスペシャリスト試験 ITサービスマネージャ試験 情報処理安全確保支援士試験 午前I 問題【共通】 問3

テクノロジアルゴリズムデータ構造

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

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

  1. ノード n の右に子ノード r があれば，f(ノード r)を実行
  2. ノード n の左に子ノード l があれば，f(ノード l)を実行
  3. 再帰処理 f(ノード r)，f(ノード l)を未実行の子ノード，又は子ノードがなければ，ノード自身がもつデータを出力
  4. 終了
図 2分木の構造
図の説明テキスト

2分木の構造図。
根ノードは「＋」
「＋」の左の子ノードは「A」、右の子ノードは「÷」
「÷」の左の子ノードは「×」、右の子ノードは「－」
「×」の左の子ノードは「B」、右の子ノードは「C」
「－」の左の子ノードは「D」、右の子ノードは「E」

解答・解説

正解: エ. ED－CB×÷A＋

二分木の再帰的な探索とは

二分木の各ノードを巡回（探索）する方法には、親ノードと子ノードをどの順番で処理するかによっていくつかの種類があります。本問のように再帰的な関数を用いて、子ノードの処理を先に行い、最後に自分自身のデータを出力する方式を「帰りがけ順（後行順）」と呼びます。本問では特に右の子ノードから優先して処理を進める定義になっています。

正解の根拠

問題文で定義された再帰処理 f(ノード n) は、以下の順序で実行されます。

  1. 右の子ノードがあれば、そのノードに対して処理を実行する。
  2. 左の子ノードがあれば、そのノードに対して処理を実行する。
  3. 自分自身のノードのデータを出力する。

この定義に従って、根ノード「＋」から順番に処理を追うと次のようになります。

  1. ノード「＋」
    右の子「÷」へ進みます（左の子「A」と自身「＋」の出力は保留）。

  2. ノード「÷」
    右の子「－」へ進みます（左の子「×」と自身「÷」の出力は保留）。

  3. ノード「－」
    右の子「E」へ進みます（左の子「D」と自身「－」の出力は保留）。

  4. ノード「E」
    子ノードがないため、手順3により自身のデータ 「E」 を出力します。

  5. ノード「－」に戻り、左の子「D」へ進みます。

  6. ノード「D」
    子ノードがないため、自身のデータ 「D」 を出力します。

  7. ノード「－」の子の処理が終わったため、自身のデータ 「－」 を出力します。

  8. ノード「÷」に戻り、左の子「×」へ進みます。

  9. ノード「×」
    右の子「C」へ進みます（左の子「B」と自身「×」の出力は保留）。

  10. ノード「C」
    子ノードがないため、自身のデータ 「C」 を出力します。

  11. ノード「×」に戻り、左の子「B」へ進みます。

  12. ノード「B」
    子ノードがないため、自身のデータ 「B」 を出力します。

  13. ノード「×」の子の処理が終わったため、自身のデータ 「×」 を出力します。

  14. ノード「÷」の子の処理が終わったため、自身のデータ 「÷」 を出力します。

  15. ノード「＋」に戻り、左の子「A」へ進みます。

  16. ノード「A」
    子ノードがないため、自身のデータ 「A」 を出力します。

  17. 最後に、ノード「＋」自身のデータ 「＋」 を出力して終了します。

これらの出力を順番に並べると「ED－CB×÷A＋」となります。したがって、正解はエです。

各選択肢の解説

  • ア: ＋÷－ED×CBAは、自分自身の出力、右の子、左の子の順で処理した場合の文字列であり、条件の定義に照らして誤りです。

  • イ: ABC×DE－÷＋は、左の子、右の子、自分自身の出力の順で処理した場合の文字列であり、条件の定義に照らして誤りです。

  • ウ: E－D÷C×B＋Aは、右の子、自分自身の出力、左の子の順で処理した場合の文字列であり、条件の定義に照らして誤りです。

  • エ: ED－CB×÷A＋は、右の子、左の子、自分自身の出力の順に処理した正しい結果です。

Spineチーム