サンプル問題セット(2022年12月公開) 科目B 問9
次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
手続 order は,図の 2 分木の,引数で指定した節を根とする部分木をたどりながら,全ての節番号を出力する。大域の配列 tree が図の 2 分木を表している。配列tree の要素は,対応する節の子の節番号を,左の子,右の子の順に格納した配列である。例えば,配列 tree の要素番号 1 の要素は,節番号 1 の子の節番号から成る配列であり,左の子の節番号 2,右の子の節番号 3 を配列{2,3}として格納する。
手続 order をorder(1)として呼び出すと,[ ]の順に出力される。
12 376548 9 10 11 12 13 14
注記 1 ○の中の値は節番号である。
注記 2 子の節が一つの場合は,左の子の節とする。
図プログラムが扱う 2 分木
大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9},
{10, 11}, {12, 13}, {14}, {}, {}, {},
{}, {}, {}, {}} // {}は要素数0の配列
○order(整数型: n)
if (tree[n]の要素数 が 2 と等しい)
order(tree[n][1])
nを出力
order(tree[n][2])
elseif (tree[n]の要素数 が 1 と等しい)
order(tree[n][1])
nを出力
else
nを出力
endif
| 答え | |
|---|---|
| ア | 1,2,3,4,5,6,7,8,9,10,11,12,13,14 |
| イ | 1,2,4,8,9,5,10,11,3,6,12,13,7,14 |
| ウ | 8,4,9,2,10,5,11,1,12,6,13,3,14,7 |
| エ | 8,9,4,10,11,5,2,12,13,6,14,7,3,1 |
出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問9
正解と解説を見る
正解:ウ
ポイント:「左の子 → 自分 → 右の子」の順に出力するのが中間順(間順)の走査。左の葉までまず降りる。
order(n) は、子が2つなら「左の子を処理 → n を出力 → 右の子を処理」、子が1つなら「子を処理 → n を出力」、子がなければ n を出力します。これは木の中間順(間順)の走査です。
tree から木の形を読むと、1 の子は 2, 3、2 の子は 4, 5、4 の子は 8, 9、5 の子は 10, 11、3 の子は 6, 7、6 の子は 12, 13、7 の子は 14 だけです。
order(1) は、まず左の 2 → さらに左の 4 → さらに左の 8 まで降ります。8 は葉なので 8 を出力、戻って 4、右の 9。次に 2、右の部分木で 10, 5, 11。そして 1、右の部分木で 12, 6, 13, 3, 14, 7。
出力は 8,4,9,2,10,5,11,1,12,6,13,3,14,7 で(ウ)。
イは先行順(自分 → 左 → 右)、エは後行順(左 → 右 → 自分)の結果です。
7 は子が 14 だけなので、14 を出力してから 7 を出力する点に注意。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。
正解のプログラムを動かしてみる
order(1) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 64 手、最初の 60 手を表示)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9}, | tree = {{2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {14}, {}, {}, {}, {}, {}, {}, {}} |
| 2 | 5行目○order(整数型: n) | n = 1 |
| 3 | 6行目if (tree[n]の要素数 が 2 と等しい) | 真 |
| 4 | 5行目○order(整数型: n) | n = 2 |
| 5 | 6行目if (tree[n]の要素数 が 2 と等しい) | 真 |
| 6 | 5行目○order(整数型: n) | n = 4 |
| 7 | 6行目if (tree[n]の要素数 が 2 と等しい) | 真 |
| 8 | 5行目○order(整数型: n) | n = 8 |
| 9 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 10 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 偽 |
| 11 | 14行目nを出力 | |
| 12 | 7行目order(tree[n][1]) | n = 4 |
| 13 | 8行目nを出力 | |
| 14 | 5行目○order(整数型: n) | n = 9 |
| 15 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 16 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 偽 |
| 17 | 14行目nを出力 | |
| 18 | 9行目order(tree[n][2]) | n = 4 |
| 19 | 7行目order(tree[n][1]) | n = 2 |
| 20 | 8行目nを出力 | |
| 21 | 5行目○order(整数型: n) | n = 5 |
| 22 | 6行目if (tree[n]の要素数 が 2 と等しい) | 真 |
| 23 | 5行目○order(整数型: n) | n = 10 |
| 24 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 25 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 偽 |
| 26 | 14行目nを出力 | |
| 27 | 7行目order(tree[n][1]) | n = 5 |
| 28 | 8行目nを出力 | |
| 29 | 5行目○order(整数型: n) | n = 11 |
| 30 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 31 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 偽 |
| 32 | 14行目nを出力 | |
| 33 | 9行目order(tree[n][2]) | n = 5 |
| 34 | 9行目order(tree[n][2]) | n = 2 |
| 35 | 7行目order(tree[n][1]) | n = 1 |
| 36 | 8行目nを出力 | |
| 37 | 5行目○order(整数型: n) | n = 3 |
| 38 | 6行目if (tree[n]の要素数 が 2 と等しい) | 真 |
| 39 | 5行目○order(整数型: n) | n = 6 |
| 40 | 6行目if (tree[n]の要素数 が 2 と等しい) | 真 |
| 41 | 5行目○order(整数型: n) | n = 12 |
| 42 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 43 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 偽 |
| 44 | 14行目nを出力 | |
| 45 | 7行目order(tree[n][1]) | n = 6 |
| 46 | 8行目nを出力 | |
| 47 | 5行目○order(整数型: n) | n = 13 |
| 48 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 49 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 偽 |
| 50 | 14行目nを出力 | |
| 51 | 9行目order(tree[n][2]) | n = 6 |
| 52 | 7行目order(tree[n][1]) | n = 3 |
| 53 | 8行目nを出力 | |
| 54 | 5行目○order(整数型: n) | n = 7 |
| 55 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 56 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 真 |
| 57 | 5行目○order(整数型: n) | n = 14 |
| 58 | 6行目if (tree[n]の要素数 が 2 と等しい) | 偽 |
| 59 | 10行目elseif (tree[n]の要素数 が 1 と等しい) | 偽 |
| 60 | 14行目nを出力 |
出力:8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7