アルゴリズムとプログラミング

基本情報技術者試験 科目A免除 修了試験 200912 実施分 問7

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 のグループの数値から順に並べる。 ここで,グループ内では,処理が行われた数値を左側から順に並べるものとする。
  • ア 180,282,315,410,525,645
  • イ 315,410,525,180,282,645
  • ウ 410,315,525,645,180,282
  • エ 645,525,410,315,282,180

出典:基本情報技術者試験 科目A免除 修了試験 200912 実施分 問7

答えと解説を見る

正解:ウ

覚える知識

基数ソートの手順トレース

基数ソートは、下位の桁から順に安定な分配を繰り返して整列させる手法である。

この問題で必要なこと

1の位でグループ分けして0〜9の順に並べ直し、次に10の位で同じことをする。グループ内の順序は保たれる。結果は410,315,525,645,180,282。

ひっかけ

整列済みを期待してアを選ぶ。手順4で終わるのは10の位までなので100の位は整列されない。

この知識の出題:本試験系 0 回・免除試験 1 回(公開問題での観測値)

この知識をアプリで解いて覚える レッスン「整列(ソート)アルゴリズムの比較」で学ぶ