応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

2.プログラミング

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

整列アルゴリズムには、いくつかの方法があります。
試験ではそれほど問われません。

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

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

簡単な例を述べます。小さい数字が上に来るように並べ替えます。一番下の2とその上の1を比べます。次に、1と4を比べます。1の方が小さいので入れ替えます。次に、1と3を比べ、小さい1を上にします。こうやって、一番上にはもっとも小さい数字が来ます。これを繰り返します。
aa
マージソート
過去問(H26秋AP午後問3)では、マージソートに関して、「マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である」と述べています。
過去問は、以下に掲載しています。
http://sm.seeeko.com/archives/65912768.html

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

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

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

Д辧璽廛宗璽
過去問(H20春SW午前問11)では、「ヒープソートでは,未整列の部分を順序木に構成し,そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して,未整列部分を縮めていく。」

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

線形探索の問題は
■H26春
問6 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて,与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。
 ここで,検索する従業員番号はランダムに出現し,探索は常に表の先頭から行う。また,与えられた従業員番号がこの表に存在しない確率をaとする。

H26h-問6ans
【正解】エ

■H19春SW
問13 配列上に不規則に並んだ多数のデータの中から,特定のデータを探し出すのに適したアルゴリズムはどれか。
ア 2分探索法 ウ ハッシュ法
イ 線形探索法 エ モンテカルロ法

正解はイ

ハッシュ表探索の問題は以下です。

■H27秋
問5 キーが小文字のアルファベット1文字(a,b,…,zのいずれか)であるデータを,大きさが10のハッシュ表に格納する。ハッシュ関数として,アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは,昇順に連続した2進数が,アルファペット順にコードとして割り当てられている。
ア aとi     イ bとr     ウ cとl     エ dとx
【正解】エ
アルファベットのASCIIコードおよび1の位の数は次のようになります。
アルファベット ASCIIコード 1の位の数
   a    97   7
   b    98   8
   c    99   9
   d    100   0
   ・・・
   i    105   5
   ・・・
   r    114   4
   ・・・
   x    120   0
ただ、ASCIIコードを覚えている人はいないことでしょう。
2つも文字がいくつ離れているのかを考えれば衝突するかがわかります。dとxは、20離れていて、ハッシュ関数は、1の位の数を用いているので、衝突することがわかります。

■H27春
問5 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(r)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x  mod nはxをnで割った余りを表す。
ア a+bがnの倍数
イ a-bがnの倍数
ウ nがa+bの倍数
エ nがa-bの倍数
【正解】イ

■H26春
問19 ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。
H26h-問19
【正解】エ

■H25秋
問7 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x mod n はxをnで割った余りを表す。
ア a+bがnの倍数
ウ nがa+bの倍数
イ a-bがnの倍数
エ nがa-bの倍数

【正解】イ

過去問(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
【正解】ウ
バブルソートを利用しています。

配列を作ると、メモリにアドレスが確保されます。その様子をプログラムで実行します。
#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秋
問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を表示
  という処理になる。

■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

整数nが与えられた場合、nの階乗であるfact(n)を求めるプログラムを考えます。
たとえば、n=3と4で考えます。
・3の階乗:fact(3)=3×2×1 = 6
・4の階乗:fact(4)=4×3×2×1 = 4×fact(3) = 24
            ̄ ̄ ̄ ̄
           =fact(3)
           
4の階乗であるfact(4)を求めるには、自分自身であるfact(3)を呼び出すことで、計算ができます。     
このように、自分自身を呼び出すことが可能プログラムのことを再帰的と言います。

問題の例はこちら
http://sm.seeeko.com/archives/65924345.html

実際のプログラムの例はこちら
http://sm.seeeko.com/archives/65924343.html

スポンサードリンク

このページのトップヘ