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

 

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

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

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

2.選択ソート

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

3.バブルソート(交換法)

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

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

aa
 
では、以下をやってみましょう。6個の要素を持つ以下の配列があります。
a(6)={21,5,53,71,3,17}
右から左へのバブルソートによって、昇順に整列させます。
比較するのは、6つ目と5つ目、5つ目と4つ目、4つ目と3つ目・・・・2つ目と1つ目です。そして、小さい方に入れ替えます。1回目は以下のようになります。
アルゴリズム
右から左なので、17と3を比較し、3の方が小さいのでそのままです。次に、3と71を比較し、3の方が小さいので入れ替えます。
このようにすると、最後は
3  21  5  53  71  17 です。
2回目→ 3  5  21  17  53  71
3回目→ 3  5  17  21  53  71
となり、3回で整列します。しかし、実際にはもう少し時間がかかる場合もあれば、最初から整列している場合には、1回もやらずに整列する場合もあります。最長は、5回(n-1)です。
では、これをアルゴリズムにしてみましょう。1回目の操作だけに着目します。

①a[6](=17) とa[5](=3)を比較し、a[5]の方が大きければ、a[5]とa[6]を入れ替えます。
②a[5](=3) とa[4](=71)を比較し、a[4]の方が大きければ、a[4]とa[5]を入れ替えます。
③・・・
⑤a[2](=3) とa[1](=21)を比較し、a[1]の方が大きければ、a[1]とa[2]を入れ替えます。

なんとなく、アルゴリズムが見えてきましたね。
・ループ条件:j=6(初期値)、j>=2(継続条件)、j--(増分の式)
・判断:a[j-1]>a[j]
・処理(Yesの場合):a[j-1]とa[j]を入れ替え。

ただし、a[j-1]とa[j]を入れ替えるのは、人間には簡単ですが、プログラムでは工夫が必要です。
・a[j-1]→w (値をwに退避)
・a[j]→a[j-1] 
・w→a[j]

この処理を、何回も繰り返すだけです。
では、何回繰り返すでしょうか。それは、要素数をNとすると、最長はN-1回です。1回処理することに、一番小さい数字が一番左に行きます。N-1回繰り返せば、必ず整列します。
また、2回目、3回目と繰り返す際に、上記の処理は1回ずつ少なくて済みます。なぜなら、1番小さい数は一番左にすでに配置されているからです。
なので、アルゴリズムとしては、以下のようになります。※a[j-1]とa[j]を入れ替えは簡略化されています。

過去問(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になるまでこれを繰り返す。
イ 中間的な基準値を決めて,それよりも大きな値を集めた区分と,小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。
ウ 隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。
エ 未整列の部分を順序木にし,そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して,未整列の部分を縮めていく。





アはシェルソート
イはクイックソート
ウはバブルソート
正解は、エです。
 
みましょう。
問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はデータの中身を示します。データの中身は他の関数に渡す場合、このままだと渡す先の変数に同じデータがコピーされるため、メモリを余分に使うことになります。
もちろん、マスターのデータを変えたくないのであれば、このままでもよいと思います。

 

1.再帰とは

再帰」とは、「再び帰ってくる」ですが、どこに帰ってくるかというと、自分自身です。
過去問(H29春AP問7を部分的に抜粋)では、「再帰的プログラムは,手続の中でそれ自体を呼び出すプログラム」とあります。

f:id:mamori_yuto:20181103063502j:plain

以下に、再帰的(リカーシブ)、再入可能(リエントラント)などを含めて解説しています。

sm.seeeko.com

2.過去問および再帰的なプログラムの具体例

(1)H29秋AP午前問7

問7 fact(n)は,非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。
ア if n=0 then return 0 else return n×fact(n-1)
イ if n=0 then return 0 else return n×fact(n+1)
ウ if n=0 then return 1 else return n×fact(n-1)
エ if n=0 then return 1 else return n×fact(n+1)

【正解】ウ

fact(1)=1
fact(2)=2×fact(1)=2×1=2
fact(3)=3×fact(2)=3×2×1=6
fact(4)=4×fact(3)=4×3×2×1=24

たとえばn=3とすると
fact(3)=3×fact(2)
fact(2)=2×fact(1)
fact(1)=1×fact(0)
fact(0)= ←ここを0にしてしまってはダメで、1にすべき。
そうしないと
fact(3)=3×2×1×0=0になってしまう。

実際のプログラムは、以下に記載しました。
 

sm.seeeko.com

http://sm.seeeko.com/archives/65924343.html
これの、再帰的に書く方です。

(2)H25秋AP

問8 再帰的に定義された手続procで,proc(5)を実行したとき,印字される数字を順番に並べたものはどれか。
     proc(n)
      n=0ならば戻る
      そうでなければ
      {
       nを印字する
       proc(n-1)を呼び出す
       nを印字する
     }
     を実行して戻る

ア 543212345
イ 5432112345  
ウ 54321012345  
エ 543210012345

【正解】イ

実際のプログラムは以下

#include<stdio.h> // stdio.h(標準入出力を行うための関数が定義されたファイル)を読み込む

// proc関数。整数を一つ(int n)受け取って処理を行い、処理後に値は返さない(void)
void proc(int n) {
    if (n == 0) // もしnが0なら
        return; //   何もせず戻る
    else        // そうでなければ(nが0以外なら)
    {
        printf("%d", n); // nを表示
        proc(n-1);       // proc(n-1)を実行
        printf("%d", n); // nを表示
    }
}

// main関数。引数は取らない。処理後に値を返さない
void main() {
    proc(5);
}


補足解説
  proc(n)の流れは
    ・nを表示
    ・proc(n-1)を実行
    ・nを表示
  の3段階。
 
  したがって、proc(5)を呼び出すと、
    ・5を表示
    ・proc(4)を実行
    ・5を表示
 
  proc(4)の処理は
    ・4を表示
    ・proc(3)を実行
    ・4を表示
  

  これを続けていくと、
    ・5を表示
     ・4を表示
      ・3を表示
       ・2を表示
        ・1を表示
         ・proc(0)を実行
        ・1を表示
       ・2を表示
      ・3を表示
     ・4を表示
    ・5を表示

  proc(0)は何もせずにreturnするため、
  最終的に、
      ・5を表示
     ・4を表示
      ・3を表示
       ・2を表示
        ・1を表示
        ・1を表示
       ・2を表示
      ・3を表示
     ・4を表示
    ・5を表示
  という処理になる。

 

1.ミドルウェアとは

ミドル(middle)とは「中間」という意味で、WindowsLinuxなどのOSと、アプリケーションソフト(メールソフトやApacheなどのWebサーバのソフトウェア)などの中間に位置するものです。
代表例が、OSとWebアプリケーションを繋ぎ、JavaサーブレットJSPを処理するTomcatがあります。

2.ミドルウェアに関する過去問

(1)H29秋AP問19

問19 Hadoopの説明はどれか。
ア Java EE 仕様に準拠したアプリケーションサーバ
イ LinuxWindowsなどの様々なプラットフォーム上で動作するWebサーバ
ウ 機能の豊富さが特徴のRDBMS
エ 大規模なデータを分散処理するためのソフトウェアライブラリ




【正解】エ

(2)H29春AP問17

問17 サーバアプリケーションの開発のための,オブジェクト指向技術に基づいたコンポーネントソフトウェアの仕様はどれか。
ア EAI (Enterprise Application Integration)
イ EJB (Enterprise JavaBeans)
ウ ERP (Enterprise Resource Planning)
エ UML (Unified Modeling Language)




【正解】イ

(3)H29春AP問18

問18 ホワイトボックステストにおいて,プログラムの実行された部分の割合を測定するのに使うものはどれか。
ア アサーションチェッカ
イ シミュレータ
ウ 静的コード解析ツール
エ テストカバレージ分析ツール




【正解】エ

(4)H27秋AP問17

問7 JavaBeansを利用してソフトウェア開発を行うメリットとして,適切なものはどれか。
ア HTML文書が動的に生成できる。
イ コンポーネントが容易に再利用できる。
ウ 分散トランザクション処理ができる。
エ メッセージングによって非同期に通信できる。




【正解】イ

↑このページのトップヘ