基本情報技術者令和4年免除 問6
問6
2分木を入力するためのテキスト表現を,次のように規定した。図のように節に番号をつけたとき,テキスト表現として適切なものはどれか。
〔テキスト表現〕
〔テキスト表現〕
- (左部分木の節番号又はテキスト表現,節番号,右部分木の節番号又はテキスト表現)と表す。
- 部分木が空のときはxを書く。
- ((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
- 基本情報技術者 H6H31と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ウ
解説
木構造の根である"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分木全体を表すテキスト表現となるので「ウ」が正解です。
根"3"は左部分木として (1, 2, x) を、右部分木として (4, 5, 6) を持つので、根"3"を表すテキスト表現は ((1, 2, x), 3, (4, 5, 6)) となります。これが設問の2分木全体を表すテキスト表現となるので「ウ」が正解です。