高度情報処理技術者試験・情報処理安全確保支援士試験 令和6年度 春期 午前I 問3
各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根（最上位のノード）から始めたときの出力はどれか。 〔f(ノード n)の定義〕 1. ノードnの右に子ノードrがあれば、f(ノード r)を実行 2. ノードnの左に子ノードlがあれば、f(ノード l)を実行 3. 再帰処理f(ノード r)、f(ノード l)を未実行の子ノード、又は子ノードがなければ、ノード自身がもつデータを出力 4. 終了
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】エ
図の二分木では、根が「＋」、その左の子がA、右の子が「÷」です。「÷」の左には「×」があり、その子は左がB、右がCです。「÷」の右には「－」があり、その子は左がD、右がEです。処理は各ノードで、右の子、左の子、ノード自身の順に進みます。まず根の右側の「÷」へ進み、その右側の「－」ではE、D、「－」の順に出力するので「ED－」です。次に「÷」の左側の「×」ではC、B、「×」の順となり「CB×」です。その後に「÷」を出力するため、右部分木全体は「ED－CB×÷」となります。続いて根の左のA、最後に根の「＋」を出力するので、全体は「ED－CB×÷A＋」となり、エが正解です。
アの「＋÷－ED×CBA」は誤りです。これは各ノード自身を先に出力し、その後に右、左の順でたどる先行順に相当します。
イの「ABC×DE－÷＋」は誤りです。これは左、右、ノード自身の順でたどる一般的な後行順です。
ウの「E－D÷C×B＋A」は誤りです。これは右、ノード自身、左の順でたどる中間順に相当します。
【ポイント】 再帰的な木の走査では、ノード自身を出力する位置と、左右のどちらを先に処理するかを分けて確認します。 本問は一般的な左優先ではなく、右、左、自分という順序です。
出典：令和6年度 春期 高度情報処理技術者試験・情報処理安全確保支援士試験 午前I 問3
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の30問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる