問題プレビューID: 43cf1ab3基本情報技術者試験 2023年(令和5年度)サンプル問題 科目B

問 9
基本情報技術者試験 2023年(令和5年度)サンプル問題 科目B

次の記述中の [  ] に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。

手続 order は,図の 2 分木の,引数で指定した節を根とする部分木をたどりながら,全ての節番号を出力する。大域の配列 tree が図の 2 分木を表している。配列 tree の要素は,対応する節の子の節番号を,左の子,右の子の順に格納した配列である。例えば,配列 tree の要素番号 1 の要素は,節番号 1 の子の節番号から成る配列であり,左の子の節番号 2,右の子の節番号 3 を配列 {2, 3} として格納する。 手続 order を order(1) として呼び出すと,[  ] の順に出力される。

注記1:○の中の値は節番号である。 注記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

解答群

解説

正解は「ウ」です。 この order 手続は、「左の子を探索 → 自分自身を出力 → 右の子を探索」という 「中間順(In-order)」 の木巡回アルゴリズムです。

  1. 根(1)から開始:
    • order(2) を実行
      • order(4) を実行
        • order(8) -> 8 を出力
        • 4 を出力
        • order(9) -> 9 を出力
      • 2 を出力
      • order(5) を実行 ...
    • 1 を出力(ここで全体の中心となる 1 が出力されます)
    • order(3) を実行 ...

この順序で辿ると、出力は 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7 になります。

関連問題

本文が同じ・似ている問題を表示しています