HOME»サンプル問題»[科目B]問9

サンプル問題 [科目B]問9

問9

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

 手続 order は,図の2分木の,引数で指定した節を根とする部分木をたどりながら,全ての節番号を出力する。大域の配列 tree が図の2分木を表している。配列 tree の要素は,対応する節の子の節番号を,左の子,右の子の順に格納した配列である。例えば,配列 tree の要素番号1の要素は,節番号1の子の節番号から成る配列であり,左の子の節番号2,右の子の節番号3を配列{2,3}として格納する。手続 order を order(1) として呼び出すと, の順に出力される。
b09_1.png/image-size:466×260
〔プログラム〕
b09_2.png/image-size:501×294
  • 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

分類

アルゴリズムとプログラミング » データ構造及びアルゴリズム

正解

解説

プログラム order を見ると、処理対象となっている節が有する子の数(tree[n]の要素数)によって、3つの処理に分岐させています。
その節が2つの子を持つ(tree[n]の要素数が2)
要素の1番目の節番号(左の子)を探索する、自身の節番号を出力する、要素の2番目の節番号(右の子)を探索する(tree[n]の要素数が1)
その節が1つの子を持つ
要素の1番目の節番号(左の子)を探索する、自身の節番号を出力する
その節が子を持たない(tree[n]の要素数が0)
自身の節番号を出力する
節番号1を根として探索をすると、以下のように処理されています。
  1. order(1)を呼び出す
  2. 配列 tree[1] は2つの要素{2, 3}を持つので、そのうち1番目の要素(tree[1][1])である節番号2を対象として order(2) を呼び出す
  3. 配列 tree[2] は2つの要素{4, 5}を持つので、そのうち1番目の要素(tree[2][1])である節番号4を対象として order(4) を呼び出す
  4. 配列 tree[4] は2つの要素{8, 9}を持つので、そのうち1番目の要素(tree[4][1])である節番号8を対象として order(8) を呼び出す
  5. 配列 tree[8] は要素を持たないので8を出力して終了し、呼出し元の order(4) の処理に戻る
  6. order(4) は自身の節番号4を出力した後、2番目の要素(tree[4][2])である節番号9を対象として order(9) を呼び出す
  7. 配列 tree[9] は要素を持たないので9を出力して、order(4) の処理に戻る
まだ処理は続いていきますが、ここまでの出力順は8→4→9であることから、正解は「ウ」であると判断できます。
b09_3.png/image-size:491×378
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop