問題プレビューID: e5d2decc基本情報技術者試験 午前免除試験 2011年1月

問 5
基本情報技術者試験 午前免除試験 2011年1月

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

〔テキスト表現〕

(1) (左部分木の節番号又はテキスト表現,節番号,右部分木の節番号又はテキスト表現)と表す。

(2) 部分木が空のときは x を書く。

解説

正解は「ウ」です。

図の 2 分木は,根が 3 であり,3 の左部分木の根が 2,右部分木の根が 5 です。また,2 の左の子は 1 で右の子はなく,5 の左の子は 4,右の子は 6 です。

テキスト表現は「(左部分木の表現,節番号,右部分木の表現)」の順に書き,部分木が空なら x と書きます。

  • 根 3 の左部分木は,根が 2 でその左の子が 1,右の子が空なので,(1, 2, x)と表します。
  • 根 3 の右部分木は,根が 5 でその左の子が 4,右の子が 6 なので,(4, 5, 6)と表します。

以上を組み合わせると,((1, 2, x), 3, (4, 5, 6))となり,「ウ」が正解です。

  • ア: 節 2 の右の子(空)を表す x が欠けており,誤りです。
  • イ: 節 2 の右の子の位置に x が入っていますが,左部分木の構成が誤っており,さらに 3 が左部分木に入ってしまっています。
  • エ: 右部分木の並びが(6, 5, 4)となっており,左部分木・節番号・右部分木の順序が逆になっています。

関連問題

本文が同じ・似ている問題を表示しています