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

テクノロジアルゴリズム

この問題は2024(R6)春 高度試験共通 午前Iに出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

各ノードがもつデータを出力する再帰処理 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」

解答・解説を読む

正解: 選択肢エ

本問で定義されている再帰処理 f(n)f(n) は、2分木の各ノードを以下の順序で処理するアルゴリズムです。

  1. 右の子ノードを再帰的に処理する
  2. 左の子ノードを再帰的に処理する
  3. ノード自身のデータを出力する

これは、一般的な後行順走査（左→右→根）の左右を反転させた「右→左→根（RLN）」の順でノードを巡回する走査方法です。

図が省略されていますが、選択肢の構成から対象となる2分木は数式 A+(B×C)/(D−E)A + (B \times C) / (D - E) を表す構文木であると推測されます。
この木構造を復元すると以下のようになります。

  • 根ノード： ＋
  • ＋ の左の子： A、右の子： ÷
  • ÷ の左の子： ×、右の子： －
  • × の左の子： B、右の子： C
  • － の左の子： D、右の子： E

この木に対して「右→左→根」の順で出力を行うと、以下のようになります。

  1. 根 ＋ から右の子 ÷、その右の子 －、さらにその右の子 E へ進む。E は子を持たないため E を出力。
  2. 戻って － の左の子 D を出力し、親の － を出力。
  3. 戻って ÷ の左の子 × へ進み、その右の子 C、左の子 B、親の × の順に出力。
  4. ÷ の左右の子が処理終わったので、÷ を出力。
  5. 戻って ＋ の左の子 A を出力。
  6. 最後に根ノード ＋ を出力。

全体をつなげると、出力は ED－CB×÷A＋ となり、正解は エ です。

各選択肢の解説

  • ア：＋÷－ED×CBA。これは「根→右→左」の順で処理した場合の出力です。
  • イ：ABC×DE－÷＋。これは一般的な後行順走査である「左→右→根」の順で処理した場合の出力（逆ポーランド記法）です。
  • ウ：E－D÷C×B＋A。これは「右→根→左」の順で処理した場合の出力です。
  • エ：正解。本問の処理「右→左→根」の順での出力です。