アルゴリズムとプログラミング
基本情報技術者試験 科目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 回(公開問題での観測値)