本文へスキップ

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


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、、3、、4、

(1) データ数は9だから、 9÷3 = 3→H
(2) [7、3、4] [] [] の部分列を整列する。
   3、、4、、7、
(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、、1、 でシェルソートする。

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

問5 目次 問7