修了試験 2012-07-22実施分 基本情報技術者試験 問5

解説

正解は3です。 図の2分木は、根が節3です。 節3の左の子は節2で、節2の左の子が節1、右の子はありません。 節3の右の子は節5で、節5の左の子が節4、右の子が節6です。 規則(1)により、部分木は必ず「左部分木，節番号，右部分木」の3要素で書きます。 規則(2)により、空の部分木はxと書きます。 【選択肢別解説】 1：× 左部分木を(1，2)と2要素で書いており、節2の右部分木が空であることを示すxが抜けています。 規則どおりに書くと(1，2，x)です。 2：× 根の位置にxが書かれており、根が空であるかのような表現になっています。 また(1，2，3)は節2の右の子が節3という意味になり、図と異なります。 3：○ 左部分木は、節2の左に節1、右が空なので(1，2，x)です。 右部分木は、節5の左に節4、右に節6なので(4，5，6)です。 全体は((1，2，x)，3，(4，5，6))となり、図と一致します。 4：× 右部分木を(6，5，4)と書いており、節5の左の子が節6、右の子が節4という意味になります。 図では左が節4、右が節6なので、正しくは(4，5，6)です。 【ポイント】 2分木のテキスト表現では、左右の順序と空の部分木の書き方が問われます。 子が片方しかない節では、ない側をxで明示することを忘れないようにしましょう。