令和6年度 春期 応用情報技術者試験 午前 問6

テクノロジアルゴリズム

この問題は2024(R6)春 応用情報技術者 午前に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

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

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

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

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

根ノードは「＋」
「＋」の左の子ノードは「A」、右の子ノードは「÷」
「÷」の左の子ノードは「×」、右の子ノードは「－」
「×」の左の子ノードは「B」、右の子ノードは「C」
「－」の左の子ノードは「D」、右の子ノードは「E」

解答・解説を読む

正解: 選択肢エ

本設問は、2分木の木構造を再帰処理でたどる問題です。
与えられた処理の定義を整理すると、以下の順番でノードを走査します。

  1. 右の部分木を走査
  2. 左の部分木を走査
  3. ノード自身を出力

これは一般的な帰りがけ順（後順）走査（左→右→親）の左右を反転させた「右→左→親」の順序に該当します。

問題文に図はありませんが、選択肢の文字列から一般的な数式の構文木を推測できます。
通常の帰りがけ順で走査すると逆ポーランド記法である「ABC×DE－÷＋」（選択肢イ）になるような構文木です。
この木の構造は以下のようになります。

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

指定された手順「右→左→親」に従って走査をトレースします。

  1. ＋から右の子÷へ
  2. ÷から右の子－へ
  3. －から右の子Eへ（子がないので E を出力）
  4. －の左の子Dへ（子がないので D を出力）
  5. － 自身を出力（－）
  6. ÷の左の子×へ
  7. ×の右の子Cへ（C を出力）
  8. ×の左の子Bへ（B を出力）
  9. × 自身を出力（×）
  10. ÷ 自身を出力（÷）
  11. ＋の左の子Aへ（A を出力）
  12. ＋ 自身を出力（＋）

以上の順により、出力は「ED－CB×÷A＋」となります。

各選択肢の解説

  • ア：通常の行きがけ順（前順：親→左→右）の左右反転（親→右→左）で走査した場合の出力です。
  • イ：通常の帰りがけ順（後順：左→右→親）で走査した場合の出力です（逆ポーランド記法）。
  • ウ：通常の間がけ順（中順：左→親→右）の左右反転（右→親→左）で走査した場合の出力です。
  • エ：正解です。「右→左→親」の順序で正しく走査されています。