問題プレビューID: 004d7d12基本情報技術者試験 午前免除試験 2012年7月22日

問 5
基本情報技術者試験 午前免除試験 2012年7月22日

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

〔テキスト表現〕

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

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

図の 2 分木は,根の節番号が 3,その左部分木の根が 2(左の子が 1,右の子は空),右部分木の根が 5(左の子が 4,右の子が 6)である。

解説

正解は「ウ」です。

規定に従うと,各部分木は (左部分木,節番号,右部分木) の順で表します。

  • 節番号 2 は左の子が 1,右の子が空なので,部分木は (1, 2, x) となります。
  • 節番号 5 は左の子が 4,右の子が 6 なので,部分木は (4, 5, 6) となります。
  • 全体は,根の節番号 3 を中央に置き,左に (1, 2, x),右に (4, 5, 6) を並べて ((1, 2, x), 3, (4, 5, 6)) となります。

よって「ウ」が正解です。

  • ア: 節番号 2 の右部分木が空であることを表す x が欠けています。
  • イ: 左部分木を (1, 2, 3) としており,根の節番号 3 が重複しています。
  • エ: 右部分木を (6, 5, 4) としており,左右の子の順序が逆になっています。

関連問題

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