AP過去問 令和6年度春期 午前 問6
AP過去問 令和6年度春期 午前 問5前の問題へ
AP過去問 令和6年度春期 午前 問7次の問題へ
問6(問題文)
各ノードがもつデータを出力する再帰処理 f(ノードn) を定義した。この処理を、図の2分木の根(最上位のノード)から始めたときの出力はどれか。
〔f(ノードn)の定義〕
ノードnの右に子ノードrがあれば、f(ノードr)を実行
ノードnの左に子ノードlがあれば、f(ノードl)を実行
再帰処理 f(ノードr)、f(ノードl) を未実行の子ノード、又は子ノードがなければ、ノード自身がもつデータを出力
終了
ア ＋÷－ED×CBA
イ ABC×DE－÷＋
ウ E－D＋C×B＋A
エ ED－CB×÷A＋
回答・解説
右側に子ノードがあれば、再帰的にf(ノードn)を呼び出すというのが最初に行われるので、f(ノード[＋])→f(ノード[÷])→f(ノード[－])→f(ノード[Ｅ])によってEが格納されているノードの処理まで進みます。ノード[Ｅ]には子ノードがないので、再帰処理を未実行の右、左のノードもないし、子ノードもないので、ノード[Ｅ]自身を出力しますので、最初はEが出力されます。これでf(ノード[Ｅ])の処理がおわるので、f(ノード[－])の処理に戻ります。次は左ノードがあるので、f(ノード[Ｄ])が呼び出されます。ここでは子ノードがないのでまた出力してDが出力されます。EDと出力されたのでここでもう答えはエしかないです。
ちなみにまたf(ノード[－])に戻ると、次は再帰処理 f(ノードr)、f(ノードl) を未実行の子ノード、又は子ノードがなければ、ノード自身がもつデータを出力という処理で、未実行の子ノードもないので、自身が持つデータを出力するので、-が出力されます。ED-と出力された状態になります。法則的なものを考えると、右の子ノードから優先して出力され、次にその親のノードが持つ左の子ノードを出力して、親のノードが出力されます。右、左、親の順で出力されるということですね。次にf(ノード[÷])の処理に戻って、左のノードf(ノード[×])が呼ばれ、f(ノード[Ｃ])でCが出力され、f(ノード[Ｂ])が呼ばれて、Bが出力されます。そうすると親の処理のf(ノード[×])処理に戻って、未処理の子ノードがないので×が出力されます。これでED-CB×と出力され、また親のf(ノード[÷])に処理が戻ると、ここでは未処理の子ノードがないので÷が出力されます。これでED-CB×÷と出力されたことになります。f(ノード[＋])に処理が戻ると、左のノードの処理が呼び出されf(ノード[Ａ])でAが出力されます。そして最後にf(ノード[＋])に処理が戻ると未処理の子ノードがないので+が出力されます。したがってED-CB×÷A+と出力されます。
したがって
エ
が答えです。
AP過去問 令和6年度春期 午前 問5前の問題へ
AP過去問 令和6年度春期 午前 問7次の問題へ