2007年(平成19年) 秋期 基本情報技術者 午前 問12

2分木の各ノードがもつ記号を出力する再帰的なプログラムProc(ノードn )は、次のように定義される。
このプログラムを、図の2分木の根(最上位のノード)に適用したときの出力はどれか。

Proc(ノードn ) {
　n に左の子l があればProc(l )を呼び出す。
　n に右の子r があればProc(r )を呼び出す。
　n に書かれた記号を出力する
}

　ア 　b-c*d+a 　イ 　+a*-bcd
　ウ 　a+b-c*d 　エ 　abc-d*+

答え　エ

【解説】
まず、問題の2分木の根であるノード『+』に対しプログラムProc( )を適用します。

@ 　ノード『+』は左の子『a』があるので、『a』に対しプログラムProc( )を適用します。
A 　ノード『a』は子がないので、『a』を出力します。
B 　ノード『+』の左の子の処理が終わったので、右の子の処理を行います。
ノード『+』は右の子『*』があるので、『*』に対しプログラムProc( )を適用します。
C 　ノード『*』は左の子『-』があるので、『-』に対しプログラムProc( )を適用します。
D 　ノード『-』は左の子『b』があるので、『b』に対しプログラムProc( )を適用します。
E 　ノード『b』は子がないので、『b』を出力します。
F 　ノード『-』の左の子の処理が終わったので、右の子の処理を行います。
ノード『-』は右の子『c』があるので、『c』に対しプログラムProc( )を適用します。
G 　ノード『c』は子がないので、『c』を出力します。
H 　ノード『-』の左右の子の処理が終わったので、『-』を出力します。
I 　ノード『*』の左の子の処理が終わったので、右の子の処理を行います。
ノード『*』は右の子『d』があるので、『d』に対しプログラムProc( )を適用します。
J 　ノード『d』は子がないので、『d』を出力します。
K 　ノード『*』の左右の子の処理が終わったので、『*』を出力します。
L 　ノード『+』の左右の子の処理が終わったので、『+』を出力します。
したがって、出力されるのはabc-d*+(エ)になります。

【キーワード】
・2分木

【キーワードの解説】
  • 2分木(二分木)
    木構造と呼ばれるデータ構造の中の1つで、1つのノードの子として高々2であるものをいいます。
    子は「左」の子と「右」の子と呼ばれます。
    2分木を使用するものには、2分探索とバイナリヒープ(ソートアルゴリズム)があります。

もっと、「2分木」について調べてみよう。

戻る 一覧へ 次へ