平成31年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム次の手順はシェルソートによる整列を示している。データ列 7，2，8，3，1，9，4，5，6 を手順(1)〜(4)に従って整列するとき，手順(3)を何回繰り返して完了するか。ここで，[ ] は小数点以下を切り捨てた結果を表す。 〔手順〕 (1) “H ← [データ数÷3]” とする。 (2) データ列を，互いに H 要素分だけ離れた要素の集まりから成る部分列とし，それぞれの部分列を，挿入法を用いて整列する。 (3) “H ← [H÷3]” とする。 (4) H が0であればデータ列の整列は完了し，0でなければ(2)に戻る。
出典：平成31年度 春期 応用情報技術者試験 午前 問6
- ア2
- イ3
- ウ4
- エ5
正解：ア
解説
データ数は9個なので，手順(1)で H＝[9÷3]＝3 となり，手順(2)で3要素離れた部分列を整列します。次に手順(3)で H＝[3÷3]＝1（1回目）となり，H≠0 なので手順(2)に戻ります。その後の手順(3)で H＝[1÷3]＝0（2回目）となり，手順(4)で整列が完了します。したがって手順(3)の繰返しは2回です。
選択肢ごとの解説
- ア正しい。H は 3→1→0 と変化し，手順(3)は H を1にするときと0にするときの2回だけ実行されます。
- イ誤り。3 は，H＝0 になった後にもう一度手順(3)を実行すると数えるなど，終了判定を1回多く数えた場合の値です。
- ウ誤り。4 は，手順(1)の H＝[9÷3] も手順(3)の繰返しに含めるなど，数え方を取り違えた場合の値です。
- エ誤り。5 は，H を3で割るのではなく1ずつ減らしていくと考えた場合などの値で，[H÷3] という計算とは合いません。