修了試験 2011-07-24実施分 基本情報技術者試験 問6

解説

正解は3です。 図は、2分木の外側を左回りに一筆書きでたどる様子を示しています。 根の＋から出発し、a、＊、－、b、cと下りて戻り、dを回って根に戻ります。 どの時点で節の記号を書くかによって、前置・中置・後置の各記法が得られます。 【選択肢別解説】 1：× 前置記法は、節に「下りたとき」に記号を書きます。 こうすると＋、a、＊、－、b、c、dの順になり、図の前置記法と一致します。 上に戻るときに書くのは後置記法です。 2：× 節に下りたときに記号を書く方法は前置記法の手順です。 中置記法は、左の枝から右の枝に移るときに演算子を書きます。 3：○ 節から上に戻るときに記号を書くと、a、b、c、－、d、＊、＋の順になります。 これは図の後置記法「abc－d＊＋」と一致します。 4：× 左括弧・右括弧を書き、左から右の枝へ移るときに演算子を書く手順は、括弧付きの中置記法の書き方です。 図の(a＋((b－c)＊d))がこれに当たり、後置記法ではありません。 【ポイント】 前置記法は「行きがけ」、中置記法は「通りがけ」、後置記法は「帰りがけ」に記号を書きます。 後置記法は逆ポーランド記法とも呼ばれ、スタックを使った式の計算に用いられます。