本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成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) にもどる。

ア 2  イ 3  ウ 4  エ 5


正解


解説

シェルソートは、ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返すソート方法である。

解答するにあたり、(2) については考える必要はないが、一応記載しておく。

データ列: 7、28、3、19、4、56
(1) データ数は9だから、9÷3 = 3 → H
(2) [7、3、4] [215] [896] の部分列を整列する。
   3、16、4、28、7、59
(3) 3÷3 = 1 → H
(4) H=1なので、(2)に戻る。
(2) 間隔が1なので、全体を整列する。
 1、2、3、4、5、6、7、8、9
(3) 1÷3 = 0 → H
(4) Hが0なので、データ列の整列は完了。

よって、手順(3)は2回繰り返して完了する。


なお、9文字を3つの要素でソートするより、8文字を2つの要素でソートする方がシェルソートを理解しやすい。

データ列: 7、283、1、945 でシェルソートする。
(1) データ数は8だから、 8÷2 = 4 → H
(2) [7、1] [29] [84] [35] の部分列を整列する。
 1、243、7、985 
(3) 4÷2 = 2→ H
(4) H=2なので、(2)に戻る。
(2) [1、4、7、8] [2395] の部分列を整列する。
 1、243、7、589
(3) 2÷2 = 1 → H
(4) H=1なので、(2)に戻る。
(2) 間隔が1なので、全体を整列する。
 1、2、3、4、5、6、7、8、9
(3) 1÷3 = 0 → H
(4) Hが0なので、データ列の整列は完了。

問5 目次 問7