カテゴリ: 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文書が動的に生成できる。
イ コンポーネントが容易に再利用できる。
ウ 分散トランザクション処理ができる。
エ メッセージングによって非同期に通信できる。




【正解】イ

 

1.スタック領域とヒープ領域

メモリ領域にはいくつかの種類があります。
その中で、スタック領域とヒープ領域について簡単に違いを理解しておきましょう。
過去問(H26秋AP問15)では、「プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある」として、「サブルーチンからの戻り番地の退避にはスタック領域が使用され,割当てと解放の順序に関連がないデータの格納にはヒープ領域が使用される。」とあります。

以下は、H26秋SC午後1問1の過去問から引用しています。
こんな風にわかれているんだなぁと、雰囲気だけつかんでください。

メモリ領域
応用情報技術者試験を勉強する成子 

なぜ、領域が分かれているのですか?
メモリを使用する変数において、サイズが明確なものと、そうでないものがあるからです。
①明確なもの
変数の値やアドレスなどのサイズがわかっている値を格納する際は、スタック領域を使います。
高速に処理できます。
②動的にメモリを確保するもの
たとえば、ファイルを読み込む際には、ファイルサイズがわからないので、ヒープ領域を使います。自由度が高いですが、ポインタなどでアドレスを参照する必要があり、同じ物理メモリでありながら、スタックよりも低速になります。
また、プログラムで不要な領域を解放することも可能なので、メモリ領域を効率よく使うことが可能。メモリサイズが小さいときは、スタック領域を大きくなりすぎないようにする工夫をしたりします。
⇒一方、メモリを解放しないと、使用効率が悪くなるので、ガーベジコレクションが必要です。
 

sm.seeeko.com

 ヒープ領域に関しては、IPAの資料が参考になります。

www.ipa.go.jp

2.メモリ領域の過去問を解いてみよう

(1)H26秋AP

問15 プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある。それらの領域に関する記述のうち,適切なものはどれか。
ア サブルーチンからの戻り番地の退避にはスタック領域が使用され,割当てと解放の順序に関連がないデータの格納にはヒープ領域が使用される。
イ スタック領域には未使用領域が存在するが,ヒープ領域には未使用領域は存在しない。
ウ ヒープ領域はスタック領域の予備領域であり,スタック領域が一杯になった場合にヒープ領域が動的に使用される。
エ ヒープ領域も構造的にはスタックと同じプッシュとホップの操作によって,データの格納と取出しを行う。





イ:ヒープ領域は未使用領域が存在します。
ウ:ヒープ領域とスタック領域は別々の用途で利用され、予備領域という概念はありません。

【正解】ア

■H25春
問8 流れ図に示す処理の動作の記述として,適切なものはどれか。ここで,二重線は並列処理の同期を表す。
H25h-問8
ア ABC又はACBを実行してデッドロックになる。
イ AB又はACを実行してデッドロックになる。
ウ Aの後にBC又はCB,BC又はCB,・・・と繰り返して実行する。
エ Aの後にBの無限ループ又はCの無限ループになる。

【正解】ウ

 

1.コンパイラ

プログラムは、CやJavaなどのプログラミング言語で書かれます。これは、人間にとっては分かりやすいのですが、コンピュータはこのままでは理解できません。コンピュータが理解できるのは、01の2進数で表された機械語だけです。

そこで、プログラム言語をコンピュータが実行できる機械語に変換する処理(コンパイル)をします。この処理のソフトウェアをコンパイラと言います。
過去問では、「コンパイラ」に関して、「コンピュータが直接実行可能な機械語に,プログラムを変換するソフトウェア(H25春IP問53不正解選択肢)」とあります。

■プログラム言語
#include <stdio.h>
void main() {
int A[100];
・・・・

   →    

■機械語
001010100111000
100011111010110
110101010111101
010111101

2.コンパイルの流れ

コンパイラにおける処理は、まず、ソースコードを解析します。このとき、字句解析,構文解析,意味解析の流れで解析をします。たとえば構文解析では、ソースコードの文法に誤りがないかをチェックします。
 次にプログラムの実行時間を短縮するための最適化を行います。たとえば、途中で値が変更されない変数を定数で置き換えることで、処理速度を速めます。
 最後に、最適化されたソースコードを機械語に変換してコンパイルが完了します。
上記の流れを、過去問(H25秋AP問20)を基に整理します。

(1)ソースコード解析

①字句解析
プログラムを表現する文字の列を,意味のある最小の構成要素の列に変換する。
②構文解析
言語の文法に基づいてプログラムを解析し,文法誤りがないかチェックする。
③意味解析
変数の宣言と使用とを対応付けたり,演算におけるデータ型の整合性をチェックする。

(2)最適化

レジスタの有効利用を目的としたレジスタ割付けや,不要な演算を省略するためのプログラム変換を行う。
応用情報技術者試験を勉強する成子 

たとえば、どんな処理がありますか?
過去問(H27秋AP問19)では、「コンパイラが行う最適化の方法」として,「定数が格納される変数を追跡し,途中で値が変更されないことが確認できれば,その変数を定数で置き換える」とあります。
他には、たとえば、ループ処理の中に、毎回変数の値をセットしているとする。それは、ループの中で処理する必要がなければ、外に出しておく。そうすると、処理ステップ数が減る。

(3)機械語に変換

最適化されたソースコードを機械語に変換します。

3.コンパイラに関する過去問

(1)H27秋AP
問19 目的プログラムの実行時間を短くするためにコンパイラが行う最適化の方法として,適切なものはどれか。
ア 繰返し回数が多いループは,繰返し回数がより少ないループを複数回繰り返すように変形する。例えば,10,000回実行するループは,100回実行するループを100回繰り返すようにする。
イ 算術式の中で,加算でも乗算でも同じ結果が得られる演算は乗算で行うように変更する。例えば,“X+X”は“X*2”で置き換える。
ウ 定数が格納される変数を追跡し,途中で値が変更されないことが確認できれば,その変数を定数で置き換える。
エ プログラム中の2か所以上で同じ処理を行っている場合は,それらをサブルーチン化し,元のプログラムのそれらの部分をサブルーチン呼出しで置き換える。





 【正解】ウ

(2)H27春AP

問19 あるコンピュータ上で,異なる命令形式のコンピュータで実行できる目的プログラムを生成する言語処理プログラムはどれか。
ア エミュレータ     イ クロスコンパイラ
ウ 最適化コンパイラ  エ プログラムジェネレータ





 【正解】イ

(3)H25秋AP

問20 コンパイラにおける処理を字句解析,構文解析,意味解析,最適化の四つのフェーズに分けたとき,意味解析のフェーズで行う処理はどれか。
ア 言語の文法に基づいてプログラムを解析し,文法誤りがないかチェックする。
イ プログラムを表現する文字の列を,意味のある最小の構成要素の列に変換する。
ウ 変数の宣言と使用とを対応付けたり,演算におけるデータ型の整合性をチェックする。
エ レジスタの有効利用を目的としたレジスタ割付けや,不要な演算を省略するためのプログラム変換を行う。





ア:構文解析
イ:字句解析
エ:最適化

【正解】ウ

(4)H20春FE午前

問38 コンパイラによる最適化の主な目的はどれか。
ア ソースプログラムのレベルでのデバッグを容易にする。
イ プログラムの実行時間を短縮する。
ウ プログラムの保守性を改善する。
エ 目的プログラムを生成する時間を短縮する。





正解はイです。

1.アルゴリズムとは

アルゴリズムとは、「コンピュータに,ある特定の目的を達成させるための処理手順(H25春IP問53)」です。
また、アルゴリズムを視覚的に表したものがフローチャートです。

sm.seeeko.com

2.アルゴリズムに関する過去問

(1)過去問(H25春IP)
問53 コンピュータを利用するとき,アルゴリズムは重要である。アルゴリズムの説明として,適切なものはどれか。
ア:コンピュータが直接実行可能な機械語に,プログラムを変換するソフトウェア
イ:コンピュータに,ある特定の目的を達成させるための処理手順
ウ:コンピュータに対する一連の動作を指示するための人工言語の総称
エ:コンピュータを使って,建築物や工業製品などの設計をすること





アはコンパイラ
ウはプログラム言語
エはCAD です。

正解はイです。

■H28春
問6 流れ図に示す処理の動作の記述として,適切なものはどれか。ここで,二重線は並列処理の同期を表す。
H28h-問6
ア ABC又はACBを実行してデッドロックになる。
イ AB又はACを実行してデッドロックになる。
ウ Aの後にBC又はCB,  BC又はCB,…と繰り返して実行する。
エ Aの後にBの無限ループ又はCの無限ループになる。





【正解】ウ

■H27春
問6 モンテカルロ法によって,正方形に内接する円の面積を近似的に求める方法はどれか。
ア 円に内接する正多角形の面積によって求める。
イ 正方形内に多数の小円を重ならないようにぎっしり詰めて,円の中にある小円の個数によって求める。
ウ 正方形内に乱数を用いて多数の点を一様に打ち,円の中にある点の個数によって求める。
工 正方形内を微細な間隔の格子点で区切り,円の中にある格子点の個数によって求める。





【正解】ウ

■H26春
問5 記憶領域を管理するアルゴリズムのうち,ベストフィット方式の特徴として,適切なものはどれか。
ア 空きブロック群のうち,アドレスが下位のブロックを高い頻度で使用するので,アドレスが上位の方に大きな空きブロックが残る傾向にある。
イ 空きブロック群のうち,要求された大きさを満たす最小のものを割り当てるので,最終的には小さな空きブロックが多数残る傾向にある。
ウ 空きブロックの検索にハッシュ関数を使用しているので,高速に検索することができる。
エ 空きブロックをアドレスの昇順に管理しているので,隣接する空きブロックを簡単に見つけられ,より大きな空きブロックにまとめることができる。





【正解】イ

 

1.木構造とは

木構造は、データ間の関係を階層的に表現します。
過去問(H16春FE午前問43)では、木構造に関して「ア 階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である。」と述べられています。
tree
階層の○の部分ですが、最上位が「根」、最下位が「葉」、その間を「節」と呼びます。また、根や葉などを接続する線を「枝」と呼びます。

(1)2分木

すべての節が二つ以内の子(節や葉)をもつもの

(2)完全2分木

2分木の中で、「すべての葉が同じ深さであり,かつ,葉以外のすべての節点が二つの子をもつ(H19春SW午前問9)」ものである。別の過去問では、「根からどの葉に向かって木をたどっても,途中で通るノートの数が同じである完全2分木(H18秋SW午後Ⅰ)」という表現もされている。

(3)B木

枝が2つなのが2分木でしたが、枝が2つより多い場合を多分木と言います。
多分木の中で、葉までの階層が全て同じなどの特徴を持つものをB木と言います。
aaa

2.木構造の過去問を解いてみよう

(1)H29秋AP午前

問6 ノート1~5をもつグラフを隣接行列で表したもののうち,木となるものはどれか。ここで,隣接行列のi行j列目の成分は,ノートiとノートjを結ぶエッジがある場合は1,ない場合は0とする。
H29a-問6






【正解】イ

(2)H25秋AP午前

問6 葉以外の節点は全て二つの子をもち,根から葉までの深さが全て等しい木を考える。
  この木に関する記述のうち,適切なものはどれか。ここで,深さとは根から葉に至るまでの枝の個数を表す。また,節点には根及び葉も含まれる。

ア 枝の個数がnならば,節点の個数もnである。
イ 木の深さがnならば,葉の個数は2n-1である。
ウ 節点の個数がnならば,深さはlog2nである。
エ 葉の個数がnならば,葉以外の節点の個数はn-1である。






【正解】エ

XMLには関連する技術がいくつかあります。たとえば、Webサイトにおいて動画や音声の再生のタイミングを調整することができるSMIL(Synchronized Multimedia Integration Language)スマイルと読みます)です。

■H28秋AP午前問25
問25 動画や音声などのマルチメディアコンテンツのレイアウトや再生のタイミングをXMLフォーマットで記述するためのW3C勧告はどれか。

ア Ajax
イ CSS
ウ SMIL
エ SVG
正解は、ウです。

問24 Webページの設計の例のうち,アクセシビリティを高める観点から最も適切なものはどれか。

ア 音声を利用者に確実に聞かせるために,Webページの表示時に音声を自動的に再生する。
イ 体裁の良いレイアウトにするために,表組みを用いる。
ウ 入力が必須な項目は,色で強調するだけでなく,項目名の隣に“(必須)”などと明記する。
エ ハイパリンク先の内容が推測できるように,ハイパリンク画像のalt属性にリンク先のURLを付記する。
正解は、ウです。

 

1.2分探索木とは

2分探索木に関して過去問(H18秋SW午後1問5)では、「ノードが一つずつデータをもつ2分探索木は,どのノートNから見ても,左側の部分木のノートがもつデータはすべてNのデータよりも小さく,逆に右側の部分木のノートがもつデータはすべてNのデータよりも大きい,という性質をもつ。」と述べられている。

2.2分探索木の過去問を解いてみよう

(1)H28秋FE午前

問6 2分探索木になっている2分木はどれか。
a






【正解】イ

(2)H29秋AP午前

問5 配列A[1],A[2],・・・,A[n]で,A[1]を根とし,A[i]の左側の子をA[2i],右側の子をA[2i+1]とみなすことによって,2分木を表現する。このとき,配列を先頭から順に調べていくことは,2分木の探索のどれに当たるか。
ア 行きがけ順(先行順)深さ優先探索
イ 帰りがけ順(後行順)深さ優先探索
ウ 通りがけ順(中間順)深さ優先探索
エ 幅優先探索






【正解】エ

(3)H18秋SW午後1

問5 2分探索木に関する次の記述を読んで,設問1~4に答えよ。

 ノートが一つずつデータをもつ2分探索木は,どのノートNから見ても,左側の部分木のノートがもつデータはすべてNのデータよりも小さく,逆に右側の部分木のノートがもつデータはすべてNのデータよりも大きい,という性質をもつ。ここでは,ノートがもつデータはすべて自然数で重複がないものとする。図1に2分探索木の例を示す。ノート内の数が,データを表している。
2分探索木に対して,表1に示す二つの操作を定義する。
18-SW問5-1
 2分探索木を扱うために,それぞれのノートの情報を保持するデータ構造nodeを定義する。データ構造nodeへは, nodeの場所を指す変数であるポインタによってアクセスする。nodeがもつ変数を表2に示す。ここで,nilは,どのnodeも指していないことを示すポインタである。
18-SW問5-2
 nodeとnodeへのポインタの関係を図2に示す。図2では,変数pはnode0へのポインタであり,また,node0の変数left,rightは,それぞれnode1,node2へのポインタである。
 このとき,node0の三つの変数はそれぞれp->value,p->left,p->rightと表す。また,図2に示す状況で,p->leftの値をpへ代入すると,変数pはnode1へのポインタとなる。
18-SW問5-3
 操作lookupでは,2分探索木を根から葉の方向へ順次たどりながら探索を行う。まず,探索するデータと木の根がもつデータとを比べて,等しければ探索は終了する。探索するデータの方が小さければ左の子のノートに,大きければ右の子のノートに移動する。ここで,移動しようとした先に子のノートが存在しない場合,探索するデータが2分探索木内に見つからなかったことになり,探索終了となる。移動した先のノートでも同様にデータを比較し,探索するデータが見つかるか,又は見つからないことが分かるまで繰り返す。



設問1  図1の2分探索木に,操作insertを使って40,34,38の順にデータを挿入したときの2分探索木を,解答欄に示せ。






【正解】
18-SW問5-4

問6 次のCプログラムの説明及びプログラムを読んで,設問に答えよ。

〔プログラムの説明〕
 金額を表すときのように,整数を3けた区切り形式の文字列に変換する関数convertである。
(1)次のルールに基づいて変換を行う。
 ① 整数値が負の場合,先頭にマイナス符号を付ける。
 ② 数値の下位から3けたごとにコンマを挿入する。
  変換例を表に示す。
H20秋FE午後1問6表
(2) プログラム中で定義されている関数の仕様は,次のとおりである。
   void convert(long num,char str[ ]);
    引数:整数num.変換後の文字列strr】
    返却値:なし
    機能:整数numを3けた区切り形式の文字列に変換してstr[ ]に先頭から格納する。str[ ]には変換後の文字列を格納するのに十分な領域が確保されているものとする。また,整数numは9けた以下とする。

〔プログラム〕
 void convert(long, char[ ]);

 void convert(long num,char str[ ]){
       int minus = 0, i = 0, j = 0;
       char table[ ] =  "0123456789";
       char tmp;
     
       if(num < 0){
         minus = 1;
         num = -num;
       }

      do{
           str[j++] = table[num % 10]; /* 数値の下位から順に文字に変換 */
           num [  a  ];
           i++;
           if([  b  ] == 0 && num ! = 0){
              str[j++] = ’,’
           }
     }while(num != 0);

    if(minus != 0)[
       str[j++] = '-';
    }
    str[j--] = '\0’;

    for(i =0; [  c  ]){        /* 順序を逆にする */
         tmp = srt[i];
         str[i] = str[j];
         str[j] = tmp;
    }
  }


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

aに関する解答群
ア %= 10イ *=  -1
ウ *= -10
エ *= 10
オ /= 10

bに関する解答群
ア (i + 1) % 3
イ (i + 2) % 3
ウ (j + 1) % 3
エ (j + 2) % 3
オ i  %  3
力 j  %  3

cに関する解答群
ア i != j; i++
ウ i < j; i++
イ i != j; i++, j--
エ i < j; i++,j--
正解は、
a オ
b オ
c エ
です。

問3 コンピュータ間でのデータ受渡しに関する次の記述を読んで,設問1~3に答えよ。

 コンピュータ間でデータを受け渡す際の汎用的なデータ形式として,CSV(Comma Separated Value)とXML(Extensible Markup Language)がある。
 CSVは,データをコンマで区切って並べたデータ形式であり,多くの表計算ソフトやデータベースソフトで利用できるので,異なる種類のアプリケーションソフト間のデータ交換に使われることが多い。
 XMLは,SGML(Standard Generalized Markup Language)のサブセットとして1998年にW3CWorld Wide Web Consortium)が仕様を策定したメタ言語である。XMLで記述したデータオブジェクトをXML文書と呼ぶ。 XML文書には,XMLの文法に従って記述されだ“整形式の文書(well-formed document)”と,XMLの文法に従った上で更にDTD(Document Type Definition)が定義するデータ構造にも従って記述されている“妥当な文書(valid document)”がある。


設問1 次の(1)~(4)に示す要件が求められている場合,それぞれCSVXMLのどちらを採用するのが適切か。それぞれ適切なものを解答群の中から選び,記号で答えよ。

 (1)国内だけでなく,国外の業者とも取引する必要がある。
 (2)ネットワークの帯域幅が狭いので,データ量は少ない方がよい。
 (3)情報機器,半導体・電子部品,半導体製造,電気通信,物流業界におけるグローバルなサプライチェーンを構築するために必要な技術仕様を策定しているRosettaNet標準にのっとる必要がある。
 (4)商品の種類によっては,色やサイズなど商品に固有な情報が追加で必要となる可能性がある。追加される情報は,現時点では予測できない。

解答群
CSV
XML
ウ どちらとも言えない
正解は、
(1) ウ
(2) ア
(3) イ
(4) イ です。

18-SW問3-P10

正解は、
(1) イ
(2) ウ
(3) ア です。


18-SW問3-P11
正解は、
a 注文明細
b <注文
   発注者 = "ABC商事"
   発注年月日 = "2006-10-20"
   希望納期 = "2006-10-31" >
c <注文明細>
d </注文明細> です。

リスト構造に関して、以下の過去問(平成17年春期 FE 午後 問1)を見てみましょう。

問1 リストに関する次の記述を読んで,設問1~3に答えよ。

リストの構造は図1のとおりとする。
17-FE問1-1
(1)ROOTは,リストの先頭を指す。
(2)リストの要素は連続する2語からなる。第1語には値が,第2語には次の要素へのポインタが格納されている。
(3)リストの各要素は値の昇順に連結されていて,値はすべて異なる。最後の要素の第2語にはポインタとして0000が格納されている。
(4)図1の構造をもつリストが,図2のとおりに主記憶の00FF番地から0117番地までに格納されている。00FF番地はROOTである。
(5)1語は16ビットからなり,語単位で番地が付いている。
17-FE問1-2



設問1 010C番地の内容として正しい答えを,解答群の中から選べ。

解答群
ア 0099  イ 00A1  ウ 00A3  エ 00A4  オ 00A5






【正解】イ

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

 0110番地及び0111番地からなる要素をリストから削除するには,[ a ]番地の内容を[ b ]に変えればよい。

解答群
ア 0101  イ 0102  ウ 0103  エ 0104  オ 0105
カ 0113  キ 0114  ク 0115  ケ 0116  コ 0117






【正解】
a コ  
b イ

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

 0118番地から011D番地に格納されている3要素からなるサブリストと,設問2で要素を削除する前のリストを併合するには,[ c ]番地の内容を011Aに,[ d ]番地の内容を0102に,[ e ]番地の内容を011Cに,[ f ]番地の内容を0108にそれぞれ変えればよい。

解答群
ア 0109  イ 010B  ウ 010D  エ 010F  オ 0111
力 0113  キ 0115  ク 0117  ケ 0119  コ 011B






【正解】
c オ
d コ
e キ
f ケ

過去問(H27秋AP午前問6)を見てみましょう。
問6 次に示すユークリッドの互除法(方法1,方法2)で,正の整数a, bの最大公約数は,それぞれmとnのどちらの変数に求まるか。ここで,mod nは,mをnで割った余りを表す。
flow
【正解】ウ

 

1.フローチャートとは

流れ図(フローチャート)に関して過去問(H27春IP問59)では、「プログラムの処理手順を図式を用いて視覚的に表したもの」と述べられています。

過去問(H25秋AP午前問9)を使って、流れ図の記号の意味を解説します。
loop
 また、並行四辺形の記号が出てくることがあります。これは、「入出力」が一般的です。
なので、ユーザからの入力や、画面表示になります。

2.フローチャートの問題

過去問(H27春IP問48)では、以下の流れ図があります。
問48 表に示す構成のデータを,流れ図の手順で処理する場合について考える。流れ図中のx,y,zをそれぞれデータ区分A, B, Cと適切に対応させれば,比較(“xか?”,“yか?”',“zか?”)の回数の合計は,最低何回で済むか。
流れず

ア 170  イ 190  ウ 230  工 250





正解:ア

↑このページのトップヘ