各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたときの出力はどれか。 〔f(ノード n)の定義〕 1. ノードnの右に子ノードrがあれば、f(ノードr)を実行 2. ノードnの左に子ノードlがあれば、f(ノードl)を実行 3. 再帰処理f(ノードr)、f(ノードl)を未実行の子ノード、又は子ノードがなければ、ノード自身がもつデータを出力 4. 終了

選択肢

• ア+÷-ED×CBA
• イABC×DE-÷+
• ウE-D÷C×B+A
• エED-CB×÷A+

正解と解説

正解：エ ED-CB×÷A+

この再帰は「右部分木→左部分木→自ノード」の順に処理する、後行順走査の左右を入れ替えた走査である。根＋の右部分木÷から始まり、÷の右部分木－でE、D、－を出力、次に÷の左部分木×でC、B、×を出力、続いて÷を出力。最後に根の左の子Aを出力し、＋を出力する。よってED-CB×÷A+となる。

選択肢ごとの解説

• ア+÷-ED×CBAは自ノードを先に出力する形（先行順の変形）で、定義の順序と合わない。
• イABC×DE-÷+は左を先に処理する通常の後行順走査の結果。
• ウE-D÷C×B+Aは中間順に近い並びで、この定義では生じない。
• エ正解。右→左→自身の順に出力するとED-CB×÷A+となる。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2023年度 春期 問6