日本の国家資格の一つである情報処理技術者試験。その中でも、IT人材に必要とされる情報処理の基本的な知識・機能・活用能力を試されるのが基本情報技術者試験です。令和元年度秋期の試験では受験者数6万人を超え、とても人気のある資格試験です。
アルゴリズムとは、問題を解決するための方法や手順を一般化したものです。プログラミングにおいては、このアルゴリズムを用いてコンピュータに処理方法を指示することになるため、プログラム作成の基礎となるものです。 基本情報技術者試験の午後試験において、アルゴリズムを扱う問題「データ構造及びアルゴリズム」の分野は必須解答問題のひとつです。配点も高くとても重要な問題なのですが、苦手とする人が非常に多いという話も耳にします。
本記事ではデータ構造及びアルゴリズムの勉強方法や問題を解く際のポイントについて丁寧に解説していきます。受験者にとって役に立つことができれば幸いです。
あなたは午前免除制度について、ご存じでしょうか?
基本情報技術者試験の合格率は基本的に20%~30%の合格率で遷移しています。半分以上が落ちてしまうことから、難易度の高さが伺えるのではないでしょうか。そこで、少しでも合格率を高めるために活用したいのが「午前免除制度」です。
基本情報技術者試験に合格する為には、知識を問う午前試験、技能を問う午後試験の2つの試験に合格する必要があります。午前免除制度とは、IPAに認定されたeラーニング講座などを事前に受講し、午前免除修了試験に合格すると、本試験の午前試験が1年間免除されるという制度です。事前に午前試験の免除の権利を手に入れておけば、午後試験に集中することができるので、合格がぐっと近づくこと間違いなしです!
- 1.基本情報試験のアルゴリズム問題の種類
- 1.1.プログラムを穴埋めして完成させる問題
- 1.2.プログラムの途中経過・最終結果を答える問題
- 1.3.その他の問題
- 1.4.アルゴリズムとデータ構造の過去問題例
- 2.基本情報試験のアルゴリズム問題の勉強方法
- 2.1.基本的なアルゴリズムとデータ構造を記憶する
- 2.2.疑似言語の読み方を事前に覚えておく
- 2.3.制限時間を設けて過去問を解く
- 3.基本情報試験のアルゴリズム問題を解く際のポイント
- 3.1.設問と選択肢をすぐに見る
- 3.2.プログラムの説明に具体例が示されている場合、想定して読む
- 3.3.プログラムを読む際はプログラムの説明と関連づけて読む
- 3.4.理解しやすい変数から読み取る
- 3.5.問題を解きながらメモを取る
- 3.6.配列の要素番号と内容に注意する
- 4.まとめ
1.基本情報試験のアルゴリズム問題の種類
・プログラムを穴埋めして完成させる問題
・プログラムの途中経過・最終結果を答える問題
・その他の問題
特に先の2つは出題率の高さから必ず押さえるべき問題です。以下、解説していきます。
あなたは午前免除制度について、ご存じでしょうか?
基本情報技術者試験の合格率は基本的に20%~30%の合格率で遷移しています。半分以上が落ちてしまうことから、難易度の高さが伺えるのではないでしょうか。そこで、少しでも合格率を高めるために活用したいのが「午前免除制度」です。
基本情報技術者試験に合格する為には、知識を問う午前試験、技能を問う午後試験の2つの試験に合格する必要があります。午前免除制度とは、IPAに認定されたeラーニング講座などを事前に受講し、午前免除修了試験に合格すると、本試験の午前試験が1年間免除されるという制度です。事前に午前試験の免除の権利を手に入れておけば、午後試験に集中することができるので、合格がぐっと近づくこと間違いなしです!
1.1.プログラムを穴埋めして完成させる問題
1.2.プログラムの途中経過・最終結果を答える問題
1.3.その他の問題
- プログラム内の処理の実行回数を問う問題
- プログラムの処理量を問う問題
- プログラムによるメモリの使用量を問う問題
- プログラムにおいてエラーが起こる原因を問う問題
1.4.アルゴリズムとデータ構造の過去問題例
BizLearnのeラーニングより
平成30年度春期出題より
次のプログラムの説明及びプログラムを読んで,設問に答えよ。
ヒープの性質を利用して、データを昇順に整列するアルゴリズムを考える。ヒープは二分木であり、本問では、親は一つ又は二つの子をもち、親の値は子の値よりも常に大きいか等しいという性質をもつものとする。ヒープの例を図1に示す。図1において、丸は節を、丸の中の数値は各節が保持する値を表す。子をもつ節を、その子に対する親と呼ぶ。親をもたない節を根と呼び、根は最大の値をもつ。

(1)配列の要素番号は、0から始まる。
(2)副プログプラムmakeHeapは、整数型の1次元配列dataに格納されているhnum個(hnum>0)のデータを、次の①~③の規則で整数型の1次元配列heapに格納して,ヒープを配列で実現する。この状態を、“配列heapは,ヒープの性を質満たしている”という。
① 配列要素heap[i](i=@,1,2,…)は、節に対応する。配列要素heap[i]には、節が保持する値を格納する。
② 配列要素heap[0]は、根に対応する。
③ 配列要素heap[i](i=9,1,2,…)に対応する節の左側の子は配列要素heap[2×i十1]に対応し、右側の子は配列要素heap[2×i十2]に対応する。子がーつの場合、左側の子として扱う。
(3)図1のヒープの例に対応した配列heapの内容を、図2に示す。

①整数型:lchild(整数型:i)
要素番号iの配列要素に対応する節の左側の子の配列要素の要素番号2×i十1を計算して返却する。
②整数型:rchild(整数型:i)
要素番号iの配列要素に対応する節の右側の子の配列要素の要素番号2×i十2を計算して返却する。
③整数型:parent(整数型:i)
要素番号iの配列要素に対応する節の親の配列要素の要素番号(i-1)÷2(小数点以下切捨て)を計算して返却する。
(5)副プログラムswapは、二つの配列要素に格納されている値を交換する。
(6)副プログラムmakeHeapの引数の仕様を表1に,副プログラムswapの引数の仕様を表2に示す。


Q1
aに関する解答群
A. heap[k] > heap[lchild(k)]
B. heap[k] > heap[parent(k)]
C. heap[k] > heap[rchild(k)]
D. heap[k] < heap[lchild(k)]
E. heap[k] < heap[parent(k)]
F. heap[k] < heap[rchild(k)]
Q2
bに関する解答群 A. heap[hnum - 1]
B. heap[k]
C. parent(hnum - 1)
D. parent(k)
[プログラム2の動作]の記述中の□に入れる正しい答えを、解答群の中から選べ。
[プログラム2の説明]
(1) 副プログラム heapSort は、最初に副プログラム makeHeap を使って、配列heap にデータを格納する。配列 heap は、整列対象領域と整列済みデータ領域に分かれている(図3参照)。last は、整列対象領域の最後の配列要素の要素番号を示している。最初は、配列 heap 全体が整列対象領域であり、このとき last の値は hnum-1 である。

(2) 整列対象領域がヒープの性質を満たすとき、配列要素 heap[0] の値は、この領域での最大の値となっている。そこで、配列要素 heap[0] の値と配列要素 heap[last]の値を交換し、 last の値を1減らして、整列対象領域の範囲を狭め、整列済みデータ領域を広げる。値の交換によって、整列対象領域はヒープの性質を満たさなくなるので、副プログラム downHeap を使って、整列対象領域のデータがヒープの性質を満たすように再構成する。これを繰り返すことによって、整列済みデータ領域には昇順に整列されたデータが格納されることになる。
(3) 副プログラム heapSort の引数の仕様を表3に、副プログラム heapSort で使用する副プログラム downHeap の引数の仕様を表4に示す。


[プログラム2の動作]
副プログラム heapSort の行番号3の実行が終了した直後の α における配列 heap の内容は、図2のとおりであった。このとき、副プログラム heapSort の行番号 4 から行番号7までの1回目の繰返し処理について考える。
副プログラム heapSort の行番号5の副プログラム swap の実行が終了した直後の配列要素 heap[0] の値は、cとなる。このため、配列 heap の要素番号 0 から hnum-2 までのデータは、根に対応する配列要素 heap[0] が最大の値をもつというヒープの性質を満たさなくなる。
副プログラム heapSort の行番号6で呼び出している副プログラム downHeap は、配列 heap の整列対象領域の要素番号 0から hlast までのデータがヒープの性質を満たすように、その領域のデータを次の手順で再構成する。
(1) 配列要素の値の大きさを比較する際に使用する要素番号を n とし、 n の初期値を 0 とする。
(2) 要素番号 n の配列要素に対応する節の左側の子の要素番号を tmp に代入する。要素番号 n の子が二つあり ( rchild(n) ≦ hlast) 、右側の子の値が左側の子の値d 、右側の子の要素番号を tmp に代入する。
(3) 子に対応する配列要素 heap[tmp] の値と、その親に対応する配列要素 heap[n] の値とを比較し、配列要素 heap[tmp] の値が大きければ、配列要素 heap[n] の値と配列要素 heap[tmp] の値を交換し、 tmp を次の n として (2) に戻る。ここで、副プログラム downHeap の行番号 15 において最初に n に代入する tmp の値はe、である。
Q3
cに関する回答群
A.5
B.10
C.15
D.20
Q4
dに関する回答群 A.以下のときには
B.以上のときには
C.よりも大きいときには
D.よりも小さいときには
Q5
eに関する回答群 A.1
B.2
C.3
D.4
E.5
F.6
Q1. 正解 B
配列要素の値を交換する副プログラム swap を呼び出す条件です。ヒープの性質の中で値の大きさに関する性質を見てみると、“親の値は子の値よりも常に大きいか等しい”というものだけがあります。つまり値の交換が必要なのは、子の値が親の値より大きいときです。この条件を満たす選択肢は B です。親の値が子の値より小さいという選択肢もありますが、右側の子か左側の子だけを聞く選択肢なので不十分です。したがって、B が正解です。
Q2. 正解 D
子の値と親の値を交換しなければなりませんので、自分の親を指す D が正解です。
Q3. 正解 D
行番号5では、配列要素 heap[0] と配列要素 heap[last] の値を交換しています。行番号5実行前の配列 heap の内容は図2のとおりですから、 heap[0] の値は 60 で heap[last] の値は 20 です。この2つの値を交換するのですから、交換後の heap[0] の値は 20 となります。したがって、D が正解です。
Q4. 正解 B
副プログラム downHeap の行番号8で、右側の子の要素番号を tmp に代入しています。その条件の2つめが行番号7です。これは、heap[tmp] ≦ heap[rchild(n)] です。このとき左辺の tmp には行番号5で左側の子の要素番号 lchild(n) を代入しています。つまり、heap[lchild(n)] ≦ heap[rchild(n)] という条件となり、右側の子の値が左側の子の値以上のときという条件となり、B が正解です。
Q5. 正解 B
プログラムをトレースしていきます。最初に downHeap が呼び出されるのは、heapSort の行番号5実行後、つまり配列要素 heap[0] と配列要素 heap[last] の値を交換した後です。このとき、配列 heap の内容は下図のようになっています。

downHeap の実行に入ります。このとき hlast には5が入っています。
行番号3: n = 0 となります。
行番号4: lchild(0) は 2 × 0 + 1 = 1、hlast は 5 なので、条件を満たし行番号5以下に進みます。
行番号5: tmp = lchild(0) = 1 となります。
行番号6: rchild(0) は 2 × 0 + 2 = 2、hlast は 5 なので、条件を満たし行番号7以下に進みます。
行番号7:上図より heap[tmp] つまり heap[1] は 30、heap[rchild(0)] つまり heap[2] は 45 なので、条件を満たし行番号8に進みます。
行番号8: tmp = rchild(0) = 2 となります。
行番号 11:上図より heap[tmp] つまり heap[2] は 45、heap[0] は 20 なので、条件を満たし行番号 12 に進みます。
行番号 12: swap(heap,0,2) を実行し、heap[0] の 20 と heap[2] の 45 を交換します。この後、条件文を抜けます。
行番号 15: n = tmp = 2 となります。
行番号 15 において最初に n に代入する tmp の値を聞いていますので、2となり、B が正解です。
このようにBizLearnのeラーニングは丁寧な解説付きで、基本情報技術者試験に向けての勉強をサポートしてくれます。
あなたは午前免除制度について、ご存じでしょうか?
基本情報技術者試験の合格率は基本的に20%~30%の合格率で遷移しています。半分以上が落ちてしまうことから、難易度の高さが伺えるのではないでしょうか。そこで、少しでも合格率を高めるために活用したいのが「午前免除制度」です。
基本情報技術者試験に合格する為には、知識を問う午前試験、技能を問う午後試験の2つの試験に合格する必要があります。午前免除制度とは、IPAに認定されたeラーニング講座などを事前に受講し、午前免除修了試験に合格すると、本試験の午前試験が1年間免除されるという制度です。事前に午前試験の免除の権利を手に入れておけば、午後試験に集中することができるので、合格がぐっと近づくこと間違いなしです!
2.基本情報試験のアルゴリズム問題の勉強方法
2.1.基本的なアルゴリズムとデータ構造を記憶する
代表的なアルゴリズム
- バブルソート
- マージソート
- クイックソート
- 選択法
- 挿入法
- 線形探索法
- 二分探索法
- ハッシュ表探索法
代表的なデータ構造
- 配列
- 構造体の配列
- 連結リスト
- 二分探索木
- ヒープ
- キュー
- スタック
2.2.疑似言語の読み方を事前に覚えておく
例えば、加算を意味する演算子は「+」の記号で表現されるといったルールは基本的に同様ですので、事前に覚えておく事項となります。
2.3.制限時間を設けて過去問を解く
3.基本情報試験のアルゴリズム問題を解く際のポイント
3.1.設問と選択肢をすぐに見る
3.2.プログラムの説明に具体例が示されている場合、想定して読む
3.3.プログラムを読む際はプログラムの説明と関連づけて読む
3.4.理解しやすい変数から読み取る
3.5.問題を解きながらメモを取る
3.6.配列の要素番号と内容に注意する
4.まとめ
基本情報技術者試験の午後のデータ構造及びアルゴリズムの対策として有効なものの一つに、eラーニングを利用する勉強方法があります。豊富な過去問題とわかりやすい解説、時間を計る機能など、データ構造及びアルゴリズムの問題を解くサポートをしてくれます。
当社のeラーニング「基本情報技術者試験 合格総合対策コース」は、効率的な学習で受講者の合格をサポートします。蓄積されていく個人ごとの練習問題の正誤結果により、間違いの多い分野の分析が容易になるため、自身の弱点に特化して対策を行えます。また、チュータ担任制度もあり、チュータが質問に回答してくれる仕組みとなっているため、難しい問題でつまってしまっても質問することでスムーズに解決をすることができます。また合格ナビゲーション付きのコースでは、どのようなペースで勉強していけばよいのか、モデルケースを示し、継続的なスケジュールに沿った勉強のサポートもしてくれます。もちろん、午前免除制度にも対応しています。
あなたは午前免除制度について、ご存じでしょうか?
基本情報技術者試験の合格率は基本的に20%~30%の合格率で遷移しています。半分以上が落ちてしまうことから、難易度の高さが伺えるのではないでしょうか。そこで、少しでも合格率を高めるために活用したいのが「午前免除制度」です。
基本情報技術者試験に合格する為には、知識を問う午前試験、技能を問う午後試験の2つの試験に合格する必要があります。午前免除制度とは、IPAに認定されたeラーニング講座などを事前に受講し、午前免除修了試験に合格すると、本試験の午前試験が1年間免除されるという制度です。事前に午前試験の免除の権利を手に入れておけば、午後試験に集中することができるので、合格がぐっと近づくこと間違いなしです!
基本情報技術者試験・プロジェクトマネジメントなどビジネスに役立つ記事を公開中!
【公式LINE運用中!】
LINEにて、キャンペーン情報やブログ更新情報をお届けいたします。
もしよろしければ、下記のボタンよりご登録ください。