データ構造 (全52問中1問目)

No.1

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

〔テキスト表現〕
  • (左部分木の節番号又はテキスト表現,節番号,右部分木の節番号又はテキスト表現)と表す。
  • 部分木が空のときはxを書く。
06.gif/image-size:183×107
  • ((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))
  • [出典]
  • 午前免除試験 R4-1月 問7
  • 基本情報技術者 H6秋31と同題

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

木構造の根である"3"の左部分木に着目すると、"2"が節であり左部分木は"1"、右部分木は空になっています。(左, 節, 右)のルールに従うと、この部分木のテキスト表現は (1, 2, x) となります。次に根"3"の右部分木に着目すると、"5"が節であり左部分木は"4"、右部分木は"6"となっています。先ほどと同様に考えて、この部分木のテキスト表現は (4, 5, 6) となります。

根"3"は左部分木として (1, 2, x) を、右部分木として (4, 5, 6) を持つので、根"3"を表すテキスト表現は ((1, 2, x), 3, (4, 5, 6)) となります。これが設問の2分木全体を表すテキスト表現となるので「ウ」が正解です。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop