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

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秋AP午後問3)に具体的なイメージがあるので、みてみましょう。
問3 マージソートに関する次の記述を読んで,設問1〜3に答えよ。
 マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である。
 ここでは,それぞれの要素数が1になるまでデータ列の分割を繰り返し,分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として,要素数が8の場合のアルゴリズムの流れを図1に示す。
2
(後半略)
 応用情報技術者試験を勉強する成子 

分割したあと、併合(マージ)するからマージソートですね!


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

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

完全2分木
2分木の中で、「すべての葉が同じ深さであり,かつ,葉以外のすべての節点が二つの子をもつ(H19春SW午前問9)」ものである。別の過去問では、「根からどの葉に向かって木をたどっても,途中で通るノートの数が同じである完全2分木(H18秋SW午後機法廚箸いι集修發気譴討い襦

問27 B+木インデックスが定義されている候補キーを利用して,1件のデータを検索するとき,データ総件数Xに対するB+木インデックスを格納するノートへのアクセス回数のオーダを表す式はどれか。

ア √X
イ logX
ウ X
エ X!
正解は、イです。

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

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

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

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

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

過去問(H28秋FE午前問6)を見てみよう。

2分探索木になっている2分木はどれか

a

問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 エ
です。

過去問(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

この問題を使って、流れ図の記号の意味を解説します。
loop

問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
です。

このページのトップヘ