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