問題プレビューID: 3a604032基本情報技術者試験 午前免除試験 2009年12月

問 7
基本情報技術者試験 午前免除試験 2009年12月

6 個の数値 180,315,282,410,645,525 を並べ替える。手順 1〜4 は途中までの手順を示したものである。手順 4 まで終わったときの結果はどれか。

〔手順〕

手順 1 並びの左側から順に,数値の 1 の位の値によって 0〜9 のグループに分ける。

手順 2 次に 0 のグループの数値を左から順に取り出して並べ,その右側に 1 のグループ,以下順に 2〜9 のグループの数値を並べていく。

手順 3 手順 2 で得られた数値の並びの左側から順に,数値の 10 の位によって 0〜9 のグループに分ける。

手順 4 手順 2 と同様に,0 のグループの数値から順に並べる。

ここで,グループ内では,処理が行われた数値を左から順に並べるものとする。

解説

正解は「ウ」です。

この手順は,1 の位,10 の位の順に着目して整列する基数ソート(LSD 方式)である。

手順 1・2 では 1 の位に着目する。各数値の 1 の位は 180 → 0,315 → 5,282 → 2,410 → 0,645 → 5,525 → 5 である。0 のグループ(180,410),2 のグループ(282),5 のグループ(315,645,525)を位の小さい順に並べると,

180, 410, 282, 315, 645, 525180,\ 410,\ 282,\ 315,\ 645,\ 525

となる。

手順 3・4 では,この並びの 10 の位に着目する。10 の位は 180 → 8,410 → 1,282 → 8,315 → 1,645 → 4,525 → 2 である。1 のグループ(410,315),2 のグループ(525),4 のグループ(645),8 のグループ(180,282)を位の小さい順に並べると,

410, 315, 525, 645, 180, 282410,\ 315,\ 525,\ 645,\ 180,\ 282

となる。したがって,正解は「ウ」です。

  • ア: 1 の位だけで整列した結果に近く,10 の位の処理が反映されていない。
  • イ・エ: グループの並べ方や着目する位の取り方を誤った結果である。

関連問題

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