うごく基本情報

サンプル問題セット(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 手を表示)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9},tree = {{2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {14}, {}, {}, {}, {}, {}, {}, {}}
25行目○order(整数型: n)n = 1
36行目if (tree[n]の要素数 が 2 と等しい)真
45行目○order(整数型: n)n = 2
56行目if (tree[n]の要素数 が 2 と等しい)真
65行目○order(整数型: n)n = 4
76行目if (tree[n]の要素数 が 2 と等しい)真
85行目○order(整数型: n)n = 8
96行目if (tree[n]の要素数 が 2 と等しい)偽
1010行目elseif (tree[n]の要素数 が 1 と等しい)偽
1114行目nを出力
127行目order(tree[n][1])n = 4
138行目nを出力
145行目○order(整数型: n)n = 9
156行目if (tree[n]の要素数 が 2 と等しい)偽
1610行目elseif (tree[n]の要素数 が 1 と等しい)偽
1714行目nを出力
189行目order(tree[n][2])n = 4
197行目order(tree[n][1])n = 2
208行目nを出力
215行目○order(整数型: n)n = 5
226行目if (tree[n]の要素数 が 2 と等しい)真
235行目○order(整数型: n)n = 10
246行目if (tree[n]の要素数 が 2 と等しい)偽
2510行目elseif (tree[n]の要素数 が 1 と等しい)偽
2614行目nを出力
277行目order(tree[n][1])n = 5
288行目nを出力
295行目○order(整数型: n)n = 11
306行目if (tree[n]の要素数 が 2 と等しい)偽
3110行目elseif (tree[n]の要素数 が 1 と等しい)偽
3214行目nを出力
339行目order(tree[n][2])n = 5
349行目order(tree[n][2])n = 2
357行目order(tree[n][1])n = 1
368行目nを出力
375行目○order(整数型: n)n = 3
386行目if (tree[n]の要素数 が 2 と等しい)真
395行目○order(整数型: n)n = 6
406行目if (tree[n]の要素数 が 2 と等しい)真
415行目○order(整数型: n)n = 12
426行目if (tree[n]の要素数 が 2 と等しい)偽
4310行目elseif (tree[n]の要素数 が 1 と等しい)偽
4414行目nを出力
457行目order(tree[n][1])n = 6
468行目nを出力
475行目○order(整数型: n)n = 13
486行目if (tree[n]の要素数 が 2 と等しい)偽
4910行目elseif (tree[n]の要素数 が 1 と等しい)偽
5014行目nを出力
519行目order(tree[n][2])n = 6
527行目order(tree[n][1])n = 3
538行目nを出力
545行目○order(整数型: n)n = 7
556行目if (tree[n]の要素数 が 2 と等しい)偽
5610行目elseif (tree[n]の要素数 が 1 と等しい)真
575行目○order(整数型: n)n = 14
586行目if (tree[n]の要素数 が 2 と等しい)偽
5910行目elseif (tree[n]の要素数 が 1 と等しい)偽
6014行目nを出力

出力:8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7

サイトで、1行ずつ予想しながら動かす →