公務員試験 H30年 国家一般職(電気・電子・情報) No.37解説

　問 題　　　　　

図のようなアルゴリズムを用いて N 個のデータS［1］、S［2］、…、S［N］ （N > 1）を昇順に整列するとき、比較操作S［j ］> w の実行回数の最小値と最大値の組合せとして最も妥当なのはどれか。

 

 

 

 

 

　解 説　　　　　

具体的な N として、N = 2だと、選択肢が結局全部同じになってしまうので、N = 3 として考えます。

まず、すでに昇順のデータを考えます。
N = 3、s[1] = 1、s[2] = 2、s[3] = 3 です。すでに昇順なので、比較回数は最小と考えられます。チャートを読んでいきます。

(i) = (2)
(i,w,j) = (2,2,1)nn 比較１回め
(i,w,j) = (3,2,1)
(i,w,j) = (3,3,2)ny 比較２回め　でおしまいです。よって、最小値の方の選択肢を検討すれば、正解は 1~3 です。

次に、降順になっているデータを考えます。
N = 3,s[1] = 3,s[2] = 2,s[3] = 1 です。

(i) = (2)
(i,w,j) = (2,2,1)y 比較１回め。s[2] に 「3」 を代入します。
(i,w,j) = (2,2,0)yn s[1] = 2 を代入します。この時点で s[1] = 2,s[2] = 3,s[3] = 1 です。
(i,w,j) = (3,2,0)
(i,w,j) = (3,1,2)y 比較２回め。s[3] に 「3」を代入します。
(i,w,j) = (3,1,1)ny 比較３回め。s[2] に 「2」を代入します。
(i,w,j) = (3,1,0)yy s[1] に 「1」 を代入します。 おしまいです。

よって、最大の方の選択肢を検討すれば、 N = 3 の時 3 になるのは 選択肢 1 です。

以上より、正解は 1 です。
類題H28no37