[応用情報技術者試験] 次の手順はシェルソートによる整列を示している。何回繰り返して完了するか。

learning_ap

応用情報技術者試験の過去問を解くだけの書き溜め型の勉強記事です。
少なくとも一日一問以上ずつ問いていくので、気軽に読んでください。

広告

先に出典: 平成31年度 春期 応用情報技術者試験 午前 問6

問題

問題文

次の手順はシェルソートによる整列を示している。データ列7,2,8,3,1,9,4,5,6を手順(1)~(4)に従って整列するとき,手順(3)を何回繰り返して完了するか。ここで,[ ]は小数点以下を切り捨てた結果を表す。

〔手順〕
(1)[データ数÷3]→H とする。
(2)データ列を,互いにH要素分だけ離れた要素の集まりからなる部分列とし,それぞれの部分列を,挿入法を用いて整列する。
(3)[H÷3]→H とする。
(4)Hが0であればデータ列の整列は完了し,0でなければ(2)に戻る。

ap_kakomon_6

(いい感じのLaTeXプラグインを入れるまでは当面スクショします)

回答

(ア) 2回

自己解説

個人的にソートは好き。
でも、こういう問題では、
問題文に書いてある通りにやれば正解にたどり着く

回答の流れ

  1. スタート:[7,2,8,3,1,9,4,5,6]
  2. H=3
  3. 部分列: [7,3,4], [2,1,5], [8,9,6]
  4. 整列: [3,4,7], [1,2,5], [6,8,9]
  5. H%3=1でH≠0なのでもう一度
  6. H=1
  7. 部分列: [3, 4, 7, 1, 2, 5, 6, 8, 9]
  8. 整列: [1, 2, 3, 4, 5, 6, 7, 8, 9]
  9. H%3=0
  10. 終了

問題の著作権について

その他の項目で下記の質問に対し、
許諾、使用料の必要性がないとのことなのでありがたく使わせていただきます。

試験の過去問題の使用方法(申請方法、使用料等)について教えてください。
 当機構で公表している過去の試験問題の使用に関し、許諾や使用料は必要ありません。



次回は、問7です。
じゃあね〜〜。