アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20150726 実施分 問5
2 分木を入力するためのテキスト表現を，次のように規定した。図のように節に番号をつけたとき，テキスト表現として適切なものはどれか。
〔テキスト表現〕
(1)（左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテキスト表現）と表す。
(2) 部分木が空のときは x を書く。
2分木。根は節3。3の左の子は節2，右の子は節5。2の左の子は節1（右の子なし）。5の左の子は節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))
出典：基本情報技術者試験 科目A免除 修了試験 20150726 実施分 問5
答えと解説を見る
正解：ウ
覚える知識
2分木のテキスト表現(左部分木,節,右部分木)の読解
2分木のテキスト表現は(左部分木,節番号,右部分木)で再帰的に表し、空の部分木はxと書く。
この問題で必要なこと
(左,節,右)の形式で再帰的に表す。根3の左部分木は節2を根とし左に1、右が空なので(1,2,x)、右部分木は(4,5,6)。
ひっかけ
空の部分木のxを書き忘れた形や、根の位置・左右の順序を入れ替えた選択肢で誤らせる。
この知識の出題：本試験系 0 回・免除試験 3 回（公開問題での観測値）