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

午前問12

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

Proc(ノードn){
 nに左の子lがあればProc(l)を呼び出す
 nに右の子rがあればProc(r)を呼び出す
 nに書かれた記号を出力する
}
12.gif/image-size:124×148
  • [この問題の出題歴]
  • 基本情報技術者 H26春期 問6

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

与えられたプログラムを設問の2分木に適用すると次のようになります。
  1. 最初に2分木の根である"+"から始まります。
    [proc(+)]
    "+"の左には"a"があるので、Proc(a)が呼び出されます。
  2. [Proc(a)]
    "a"の左右にはノードがないので、aを出力し、Proc(+)の処理に戻ります。
  3. "+"の右には"*"があるので、Proc(*)が呼び出されます。
  4. [Proc(*)]
    "*"の左には"-"があるので、Proc(-)が呼び出されます。
  5. [Proc(-)]
    "-"の左には"b"があるので、Proc(b)が呼び出されます。
  6. [Proc(b)]
    "b"の左右にはノードがないので、bを出力し、Proc(-)の処理に戻ります。
  7. "-"の右には"c"があるので、Proc(c)が呼び出されます。
  8. [Proc(c)]
    "c"の左右にはノードがないので、cを出力し、Proc(-)の処理に戻ります。
  9. Proc(-)は、-を出力し、Proc(*)に戻ります。
  10. "*"の右には"d"があるので、Proc(d)が呼び出されます。
  11. [Proc(d)]
    "d"の左右にはノードがないので、dを出力し、Proc(*)の処理に戻ります。
  12. Proc(*)は、*を出力し、Proc(+)に戻ります。
  13. Proc(+)は、+を出力し、処理が終了します。
出力された記号を順番に並べると「abc−d*+」になります。
12a.gif/image-size:138×158
© 2010-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop