第2種情報処理技術者試験 2000年度 = 平成12年度・春期 午前 問14

 2分木を入力するためのテキスト表現を、次のように規定した。図のように節に番号をつけたとき、テキスト表現として正しいものはどれか。

〔テキスト表現〕
 (1)  (左部分木の節番号又はテキスト表現,節番号,右部分木の節番号又はテキスト表現)と表す。
 (2)  部分木が空のときはxを書く。

    3         ●       2/ \5     ●   ●   1/  4/ \6 ●   ●   ●


 ア ((1, 2), 3, (4, 5, 6))  イ ((1, 2, 3), x, (4, 5, 6))
 ウ ((1, 2, x), 3, (4, 5, 6))  エ ((1, 2, x), 3, (6, 5, 4))

解答

 ウ

解説

 まず、根とその子に着目しましょう。

3 / \ L R

 入力形式は、
  (左部分木の節番号又はテキスト表現,節番号,右部分木の節番号又はテキスト表現)
ですから、
  (L, 3, R)
となります。ここで、Lは、

2 / 1

であり、右の子は空ですから、入力テキストは(1, 2, x)です。したがって、
  ((1, 2, x), 3, R)
となります。また、Rは、

5 / \ 4 6

であり、入力テキストは(4, 5, 6)です。したがって、全体の入力形式は
  (1, 2, x), 3, (4, 5, 6)
となります。


BohYoh.comトップページへ