HOME»基本情報技術者平成26年春期»午前問6

基本情報技術者平成26年春期 午前問6

問6

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

Proc(ノードn){
　nに左の子lがあればProc(l)を呼び出す
　nに右の子rがあればProc(r)を呼び出す
　nに書かれた記号を出力する
}
06.png/image-size:124×148
  • ＋a*－bcd
  • a＋b－c*d
  • abc－d*＋
  • b－c*d＋a
  • [出題歴]
  • 基本情報技術者 H19秋期 問12

分類

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

正解

ウ

解説

与えられたプログラムを設問の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*＋」になります。
06a.png/image-size:138×158
© 2010-　基本情報技術者試験ドットコム　All Rights Reserved.
▲
Pagetop