カテゴリ: 2.ソフトウェア

 

1.整列アルゴリズムとは

整列アルゴリズムとは、昇順または降順に並び替えることです。
たとえば、以下が昇順に整列させたようすです。
45836 →34568

整列アルゴリズムには、いくつかの方法があります。
試験ではそれほど問われませんが、たまに問われる内容です。順に見ていきましょう。

2.選択ソート

過去問(H17秋SW午前問12)では、「未整列の並びに対して,最小のキー値をもつ要素と先頭の要素とを入れ換える。同様の操作を,未整列の並びの長さを一つずつ減らしながら繰り返す。」と述べられています。

3.バブルソート

過去問(H20春SW午前問11不正解選択肢)では、「隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。」と述べられています。

簡単な例を述べます。小さい数字が上に来るように並べ替えます。一番下の2とその上の1を比べます。次に、1と4を比べます。1の方が小さいので入れ替えます。次に、1と3を比べ、小さい1を上にします。こうやって、一番上にはもっとも小さい数字が来ます。これを繰り返します。
aa

 過去問(H25秋AP午前問9)を見てみましょう。

問9 未整列の配列α[i] (i=1,2, …,n)を,流れ図で示すアルゴリズムによって昇順に整列する。n=6でa[1]~a[6]の値がそれぞれ, 21,5,53,71,3,17の場合,流れ図において,a[j-1]とa[j]の値の入替えは何回行われるか。
流れ図

ア 3  イ 6  ウ 8 エ 15






バブルソートを利用しています。

【正解】ウ

4.マージソート

過去問(H26秋AP午後問3)では、マージソートに関して、「マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である」と述べています。

過去問(H26秋AP午後問3)に具体的なイメージがあるので、みてみましょう。

問3 マージソートに関する次の記述を読んで,設問1~3に答えよ。
 マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である。
 ここでは,それぞれの要素数が1になるまでデータ列の分割を繰り返し,分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として,要素数が8の場合のアルゴリズムの流れを図1に示す。
2
(後半略)

 応用情報技術者試験を勉強する成子 

分割したあと、併合(マージ)するからマージソートですね!
では、過去問を見てみよう!
■H26秋AP
問6 データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで図中のデータ列申の縦の区切り線は,その左右でデータ列が分割されていることを示す。
H26a-問6
ア クイックソート     イ シェルソート
ウ ヒープソート      エ マージソート
【正解】エ

5.挿入ソート 

過去問(H17秋SW午前問12)では、「未整列要素の並びの先頭の要素を取り出し,その要素を整列済みの要素の申の正しい位置に挿入する。」と述べられています。

6.シェルソート

過去問(H20春SW午前問11不正解選択肢)では、「ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。」と述べられています。

7.クイックソート

過去問(H20春SW午前問11不正解選択肢)では、「中間的な基準値を決めて,それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。」と述べられています。

8.ヒープソート

まず、ヒープとはなんでしょう。
過去問(平成17年春FE午後問4)では、以下の解説があります。 

ヒープとは,図のように,各節の値が自分の子の節の値以上になっている2分木である。
17-FE問4-1
このように、ヒープ(2分木)を使って整列させる方法です。過去問(H20春SW午前問11)では、「ヒープソートでは,未整列の部分を順序木に構成し,そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して,未整列部分を縮めていく。」とあります。
da
かなり簡略化していますが、イメージをつかんでいただきたいと思います。
まず、(ⅰ)で、3412を2分木にします。
(ⅱ)一番大きな値である4が一番上に来るように入れ替えます。
(ⅲ)最大値の4を取り出します。
(ⅳ)以降、このような最大値を取り出すことを繰り返します。

■過去問平成28年秋期 午前 問6
問6 ヒープソートの説明として,適切なものはどれか。
ア ある間隔あきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。
イ 中間的な基準値を決めて,それよりも大きな値を集めた区分と,小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。
ウ 隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。
エ 未整列の部分を順序木にし,そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して,未整列の部分を縮めていく。





アはシェルソート
イはクイックソート
ウはバブルソート
正解は、エです。
 

 過去問(H20春SW午前)をみてみましょう。

問11 データの整列方法に関する記述のうち,適切なものはどれか。
クイックソートでは,ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。
シェルソートでは,隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。
バブルソートでは,中間的な基準値を決めて,それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。
エ ヒープソートでは,未整列の部分を順序木に構成し,そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して,未整列部分を縮めていく。






アはシェルソート
イはバブルソート
ウはクイックソート

正解は、エです。

 

平成17年春期 FE 午後 問4

問4 次のプログラムの説明及びプログラムを読んで,設問1~3に答えよ。

〔プログラムの説明〕
 副プログラムHeapSortは,配列に格納されている整数値をヒープソートで昇順に整列するプログラムである。

(1)整列するNum個(Num≧2)の整数値は,大域変数の配列A[1],A[2],・・・,A[Num]に格納されている。

(2)ヒープソートは,2分木を用いてデータを整列する。2分木を配列で表現するには,ある節がA[i]に対応するとき,その左側の子の節をA[2×i]に,右側の子の節をA[2×i+1]に対応させる。図では,丸が節を,丸中の数字が節の値を示し,実際に値が格納されている配列の要素を丸の脇に示している。

(3)ヒープとは,図のように,各節の値が自分の子の節の値以上になっている2分木である。
17-FE問4-1
(4)整列の手順は,次のとおりである。
 ① 配列Aの中の,A[1],A[2],・・・,A[Num]を整列対象とする。
 ② 整列対象の各要素が,(2)で述べたような2分木を表現しているものとして,要素の値を入れ換えてヒープを作る。その結果,木の根(A[1])には整列対象の要素の最大値が入る。
 ③ 木の根(A[1])の値と,木の最後の節(整列対象の最後の要素に対応する節)の値とを交換する。
 ④ 木の最後の節を2分木から取り除く(整列対象の要素を一つ減らす)。 
 ⑤ ④の結果が,木の根だけになるまで,②~④の処理を繰り返す。

(5)ヒープを作り直す手順は,次のとおりである。
 ① 木の根を親の節とする。
 ② 子の節がなければ終了する。
 ③ 二つの子の節のうち値が大きい方と親の節の値を比較し,親の節の方が小さいときは,値を交換する。親の節の値が子の節の値以上のときは,何もしないで終了する。
 ④ 値を交換した子の節を根とする部分木に対して,①~③の処理を繰り返す。
17-FE問4-3

 

設問1 プログラム中の[   ]に入れる正しい答えを,解答群の中から選べ。

aに関する解答群
 ア L ← Top
 ウ L ← Top × 2
 イ L ← Top + 1
 エ L ← Top × 2 + 1

bに関する解答群
 ア L ≦ Last
 ウ R ≦ Last - 1
 イ L  < Last
 エ R ≦ Last - 2

正解は、
a ウ
b ア です。


設問2 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。

 図のヒープを用いて,〔プログラムの説明〕の(4)の③,④を1回だけ実行して,②が終了したとき,最初A[10]に入っていた値12が格納されている配列要素の添字は[ c ]である。また,それまでに節の値を交換した回数は[ d ]である。

解答群
ア 2  イ 3  ウ 4  エ 5  オ 6
カ 7  キ 8  ク 9

正解は、
c キ
d ウ です。


設問3 最初にビーフを作成する副プログラムInitHeapはMakeHeapを使って作る
ことができる。次のプログラム中の[   ]に入れる正しい答えを,解答群
の中から選べ。
17-FE問4-4
解答群
ア Idx: 1,Idx ≦ Last,2
イ Idx: 1,Idx ≦ Last ÷ 2,1
ウ Idx: Last,Idx ≧ 1,-2
エ Idx: Last ÷ 2,Idx ≧ 1,-1

正解は、エです。

配列を作ると、メモリにアドレスが確保されます。その様子をプログラムで実行します。
#include <stdio.h>
void main() {
    int A[100];  // 配列変数Aを定義。保存可能個数は100個でA[1]-A[100]を使用可能。
    int k;// 整数型の変数kを定義
    // kを1から100まで、1ずつ増やす(k++)
    for (k = 1; k <= 100; k++) {
        A[k] = k; 
        printf("A[%d]_add:%p\n",k,&A[k]); //A[k]のアドレスを表示
    }
}

結果は、以下のようになります。

c:\work>pg1.exe
A[1]_add:0028FDA0
A[2]_add:0028FDA4
A[3]_add:0028FDA8
A[4]_add:0028FDAC
A[5]_add:0028FDB0
A[6]_add:0028FDB4
A[7]_add:0028FDB8
・・・・
続きを読む

■H25春
問7 配列Aに対して次の手続を実行して,2≦k≦100である素数kだけを全て出力したい。a,b,cに入るループの初期値,終値,増分として,適切な組合せはどれか。

for k = 2 to 100 step 1:
  A[k] = 1;
for m = 2 to 10 step 1:
    for k =[   a   ] to [   b   ] step [   c   ]:
   A[k] = 0;
for k = 2 to 100 step 1:
  if A[k]≠0:
   print k;

H25h-問7
【正解】イ
実際のプログラムの例は以下
#include<stdio.h>   // stdio.h(標準入出力を行うための関数が定義されたファイル)を読み込む
// main関数。引数は取らない。処理後に値を返さない
void main() {
    int A[101];    // 配列変数Aを定義。保存可能個数は101個でA[0]-A[100]を使用可能。
    int k, m;  // 整数型の変数kとmを定義
    // kを2から100まで、1ずつ増やす(k++)
    for (k = 2; k <= 100; k++) {
        A[k] = 1;  // A[2]-A[100]をすべて1にしている
    }
    // 2の倍数-10の倍数をリストから消していく
    for (m = 2; m <= 10; m++) { // mを2から10まで1ずつ増やす
        for (k = 2*m; k <= 100; k += m) {
            // kを2mから100までmずつ増やす
            // つまりkは2m, 3m, 4m,・・・と変化
            A[k] = 0;  // kはmの倍数=素数ではないから0にする
        }
    }
    for (k = 2; k <= 100; k++) { // kを2から100まで1ずつ増やす
        if (A[k] != 0) {  // A[k]が0でない、つまりkが素数なら
            printf("%d,", k);  // kを表示
        }
    }
}
【処理の解説】
・エラトステネスのふるい法を使って素数を求めています。
・変数Aは、0か1の値になるが、A[k]=0なら非素数、A[k]=1なら素数(処理の途中では「素数の可能性」)
・まず2から100をすべて素数かもしれないリストに入れる
   (k=2-100についてA[k] = 1)
素数とは「約数として自分と1だけもつ」ことから、「何かの倍数であれば素数ではない」という考えで、倍数をすべて消していく。具体的にはA[k] = 0

プログラミング

・プログラム言語は、「コンピュータに対する一連の動作を指示するための人工言語の総称(H25春IP問53不正解選択肢)」です。


■H28春、H25春
問20 メインプログラムを実行した後,メインプログラムの変数X,Yの値は幾つになるか。ここで,仮引数Xは値呼出し(call by value),仮引数yは参照呼出し(call byreference)であるとする。

H28h-問20
【正解】イ

少し補足します。
①仮引数Xは値呼出し(call by value
main関数での「値」を呼び出します。add関数実行では、main関数とは違うアドレスに記録します。
よってmain関数のXの値が変化しません

②仮引数yは参照呼出し(call byreference)
main関数でのyの値が入った「アドレス」を呼び出します。add関数実行により、main関数でのYの値を書き換えるので、Yの値が変化します。

#include <stdio.h>

//add関数
void add(int X, int *Y)
{
 //"Y"は参照呼び出し(ポインタ)で渡されるため
 // 値を参照する場合や、値を代入する場合は"*Y"を使用

 X = X+*Y;  //"X"に"Y"の値を加えて"X"に代入
 *Y = X+*Y;  //"X"に"Y"の値を加えて"Y"に代入
}

//main関数
void main(){
 int X, Y;  //"X","Y"をint型変数で定義
 X = 2;
 Y = 2;

 //add関数の実行
 add(X,&Y);
 //add関数実行後の"X","Y"の値を表示

 printf("add(X,Y)はX=%d,Y=%dです\n", X, Y);

}

"X"は値呼び出しで渡されるため、add関数実行により値が変化しない
 "Y"は参照呼び出しで渡されるため、add関数実行により値が変化する
具体的には、X=2+2=4、Y=4+2=6

aa

■メモ
メモリ上のアドレスと、その値
http://sc.seeeko.com/archives/5377814.html

■ポインタで変数を宣言する意味

ポインタ変数はデータを格納するアドレスそのものを変数として定義します。「char *a」と宣言すると変数aにはアドレスが格納されます。このアドレスを他の関数にもアドレス情報として渡せばデータそのものをコピーしたりする必要がありません。
 一方、「char a」と宣言すると変数aはデータの中身を示します。データの中身は他の関数に渡す場合、このままだと渡す先の変数に同じデータがコピーされるため、メモリを余分に使うことになります。
もちろん、マスターのデータを変えたくないのであれば、このままでもよいと思います。

↑このページのトップヘ