例題と解説あり【基本情報技術者試験】アルゴリズム問題の勉強方法・解き方を徹底解説！

BizLearnではeラーニング「基本情報技術者試験 合格総合対策コース」を提供しています。
日本の国家資格の一つである情報処理技術者試験。その中でも、IT人材に必要とされる情報処理の基本的な知識・機能・活用能力を試されるのが基本情報技術者試験です。令和元年度秋期の試験では受験者数6万人を超え、とても人気のある資格試験です。
アルゴリズムとは、問題を解決するための方法や手順を一般化したものです。プログラミングにおいては、このアルゴリズムを用いてコンピュータに処理方法を指示することになるため、プログラム作成の基礎となるものです。 基本情報技術者試験の午後試験において、アルゴリズムを扱う問題「データ構造及びアルゴリズム」の分野は必須解答問題のひとつです。配点も高くとても重要な問題なのですが、苦手とする人が非常に多いという話も耳にします。
本記事ではデータ構造及びアルゴリズムの勉強方法や問題を解く際のポイントについて丁寧に解説していきます。受験者にとって役に立つことができれば幸いです。

データ構造及びアルゴリズムの分野の問題において、問題には一定のパターンがあり、大きく3つに分けられます。
・プログラムを穴埋めして完成させる問題
・プログラムの途中経過・最終結果を答える問題
・その他の問題
特に先の2つは出題率の高さから必ず押さえるべき問題です。以下、解説していきます。

プログラムを穴埋めして完成させる問題は、アルゴリズムの中では簡単な問題に入ります。しかしながら、うっかりミスが発生しやすいという特性もあります。問題が連続しているためミスがその後の回答に影響を与えることが多いので、慎重に答えるようにしましょう。

プログラムの途中経過・最終結果を答える問題では、実際のプログラムの動作をトレースして回答を導き出します。勘や予測では答えにくく、時間がかかりやすいため難しい問題です。プログラムを読んだ経験や、プログラムを実行した場合の動作などを理解することが重要となります。

上記2つの問題のほかに、以下のような問題が出題されることもあります。

• プログラム内の処理の実行回数を問う問題
• プログラムの処理量を問う問題
• プログラムによるメモリの使用量を問う問題
• プログラムにおいてエラーが起こる原因を問う問題

この中では、処理の実行回数を問う問題の出題率が高く、対策の優先度が高いといえるでしょう。

それでは、実際のデータ構造及びアルゴリズムの過去問題と解答、解説を実際に見てみましょう。下記の事例は、プログラムを穴埋めして完成させる問題とプログラムの途中経過・最終結果を答える問題を組み合わせたものとなっています。
BizLearnのｅラーニングより

---

平成30年度春期出題より
次のプログラムの説明及びプログラムを読んで,設問に答えよ。
ヒープの性質を利用して、データを昇順に整列するアルゴリズムを考える。ヒープは二分木であり、本問では、親は一つ又は二つの子をもち、親の値は子の値よりも常に大きいか等しいという性質をもつものとする。ヒープの例を図1に示す。図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に示す。
(4)親の要素番号と子の要素番号を関係付ける三つの関数がある。
①整数型: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の説明］
(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

---

このようにBizLearnのｅラーニングは丁寧な解説付きで、基本情報技術者試験に向けての勉強をサポートしてくれます。

データ構造及びアルゴリズムの問題について、簡単に解答できるようになる特別な方法はありません。しかし、ポイントを押さえて勉強することで、効率よく学ぶことは可能です。以下、そのポイントについて記載します。

テキストなどを用いて基本的なアルゴリズム、データ構造を覚えましょう。ある程度出題されると思われるアルゴリズムとデータ構造は限られているため、すべて覚えておくのが無難です。

代表的なアルゴリズム

• バブルソート
• マージソート
• クイックソート
• 選択法
• 挿入法
• 線形探索法
• 二分探索法
• ハッシュ表探索法

代表的なデータ構造

• 配列
• 構造体の配列
• 連結リスト
• 二分探索木
• ヒープ
• キュー
• スタック

アルゴリズムとデータ構造の問題では、基本情報技術者試験専用の疑似言語でプログラムが表記されます。その仕様については、問題に付属して定義の記載があるものの、試験時にすべてを読んでいては時間が不足してしまう可能性があります。疑似言語の演算子、記述形式などは過去の問題と共通したものが利用されてきているため、事前に過去問題で疑似言語について慣れておきましょう。
例えば、加算を意味する演算子は「+」の記号で表現されるといったルールは基本的に同様ですので、事前に覚えておく事項となります。

アルゴリズムとデータ構造の過去問題に取り組む場合には、実際の試験と同様に制限時間を設けて挑んでみましょう。時間配分から考えると、30分が制限時間の目安となります。ペース配分を考えながら回答することに慣れておく必要があります。

アルゴリズムとデータ構造の問題について、取り掛かりとなる各問題を解く際のポイントを以下に記載していきます。

まず、問題に取り掛かる際には、設問と選択肢をざっと見ましょう。アルゴリズムとデータ構造の問題全体の構成を確認します。さらに問題を読み進める前に、設問と選択肢から答えを得るために必要なことを読み取り、それを見つけられるようにプログラムの説明とプログラムを見ることで効率的に問題に取り組むことができます。

プログラムの説明に具体例が示されている場合、出題者がヒントとして具体例を示しています。このヒントを有効活用して問題に取り組みましょう。例に従って、具体的な値を挿入してみるとプログラムが理解しやすくなります。また具体例について値の設定前/設定後の例を自分で出してみて、問題を解くのも解答を導き出すのには有効です。

問題内の疑似言語によるプログラムとプログラムの説明は、一対になって出題されています。プログラムの説明と関連付けてプログラムを読んでいくことで、プログラムへの理解度が高まります。また、それだけで解けるような問題が出題される場合もあります。

プログラムを読み、回答を導き出す際には、理解しやすい変数から追いかけていくのがオススメです。段階を追って解いていく際には、簡単な変数を難しい変数を理解するためのヒントとして読んでみてください。

データ構造及びアルゴリズムの問題では、プログラムの処理や変数、配列の要素といった内容をひとつずつ追いかけ、プログラムの処理をトレースすることが必要となります。特に処理結果を求める問題ではトレースは必須です。その際には、理解した内容や変数、配列の要素などについてメモを取っておき、後から振り返ることができるようにしておくと、回答を導き出すのに利用できます。メモを取っておいた方が良い内容としては、変数、配列要素、データ構造内のデータなど、プログラムの処理が進むたびに内容が変わっていく値がターゲットとなります。可能であれば、状況の変化によりどのように値が変わっていったかをメモにしておくと、後から再度プログラムを読み、課題を解く際に有用です。

データ構造の中でも、基本的な構造のため出題率の高いのが配列を利用した問題です。配列において注意すべきポイントとして、要素番号と紐づけて値が保持されていることです。プログラム上では要素番号に変数をあてることで、配列の各要素の読み出し、書き換えを行うため、要素番号に利用される変数をきちんと見定めておく必要があります。また、配列の内容と要素番号を書き出し、メモを取っておくと、効率よく確実に解答に近づけるようになります。

基本情報技術者試験の午後試験において、データ構造及びアルゴリズムの問題は配点上大きなウェイトを占めています。きちんと対策を取って、点数を取っておきたい問題です。その問題形式はプログラムやその説明文の穴埋め問題とプログラムの実行結果を求める問題が多く出題されており、プログラムの読解力とプログラムの動きのトレースをする能力が回答には必要です。 さらには、アルゴリズムとデータ構造の代表的なものを覚えること、疑似言語について読み方を知っておくこと、メモを取りながら実際に問題を解いていくことなど対策としてやらなくてはいけないことは少なくありません。
基本情報技術者試験の午後のデータ構造及びアルゴリズムの対策として有効なものの一つに、ｅラーニングを利用する勉強方法があります。豊富な過去問題とわかりやすい解説、時間を計る機能など、データ構造及びアルゴリズムの問題を解くサポートをしてくれます。
当社のeラーニング「基本情報技術者試験 合格総合対策コース」は、効率的な学習で受講者の合格をサポートします。蓄積されていく個人ごとの練習問題の正誤結果により、間違いの多い分野の分析が容易になるため、自身の弱点に特化して対策を行えます。また、チュータ担任制度もあり、チュータが質問に回答してくれる仕組みとなっているため、難しい問題でつまってしまっても質問することでスムーズに解決をすることができます。また合格ナビゲーション付きのコースでは、どのようなペースで勉強していけばよいのか、モデルケースを示し、継続的なスケジュールに沿った勉強のサポートもしてくれます。もちろん、午前免除制度にも対応しています。