うごく基本情報

サンプル問題セット(2022年12月公開) 科目B 問11

配列 ・ ビンソート ・ トレース

次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 binSort を binSort([ ]) として呼び出すと,戻り値の配列には未定義の要素は含まれておらず,値は昇順に並んでいる。

○整数型の配列: binSort(整数型の配列: data)
  整数型: n ← dataの要素数
  整数型の配列: bins ← {n個の未定義の値}
  整数型: i
  for (i を 1 から n まで 1 ずつ増やす)
    bins[data[i]] ← data[i]
  endfor
  return bins
a
ア{2, 6, 3, 1, 4, 5}
イ{3, 1, 4, 4, 5, 2}
ウ{4, 2, 1, 5, 6, 2}
エ{5, 3, 4, 3, 2, 6}

出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問11

正解と解説を見る

正解:ア

ポイント:このビンソートは「値=入れる位置」。1〜n の値が重複なくそろっていないと、空きや上書きが起きる。

binSort は、値 data[i] を bins の data[i] 番目に入れます。bins の要素数は n(=data の要素数)なので、正しく整列できるのは、data が 1〜n の値を重複なく1つずつ含むときだけです。
ア {2, 6, 3, 1, 4, 5}:1〜6 が1つずつあるので、bins={1, 2, 3, 4, 5, 6} と正しく整列されます。
イ {3, 1, 4, 4, 5, 2}:4 が2つで 6 がないので、bins[6] が未定義のまま残ります。
ウ {4, 2, 1, 5, 6, 2}:2 が2つで 3 がないので、bins[3] が未定義のまま。
エ {5, 3, 4, 3, 2, 6}:3 が2つで 1 がないので、bins[1] が未定義のまま。
よって(ア)。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

サイトで、1行ずつ動かして読む →