アルゴリズムとプログラミング(擬似言語・データ構造)

基本情報技術者試験は2023年4月から通年CBT方式へ移行し、科目A(四肢択一60問・90分)と科目B(多肢選択20問・100分)で構成され、いずれも1000点満点中600点以上で合格となる(IRT=項目応答理論による採点)。IPA公表の出題構成では、科目B20問のうち約8割が「アルゴリズムとプログラミング」分野、残り約2割が情報セキュリティ分野からの出題であり、本章は合否を最も左右する領域である。科目Bの出題はIPAが試験要綱で公開する「擬似言語の記述形式」に従ったプログラムの読解が中心で、空欄補充や実行結果を問う形式が主流である。科目Aでも、試験要綱・シラバスのテクノロジ系・大分類1「基礎理論」中分類2「アルゴリズムとプログラミング」から、データ構造・探索・整列・計算量が定番論点として繰り返し出題されている。本章では擬似言語の文法、主要データ構造、探索・整列アルゴリズムと計算量を体系的に整理する。

科目Bのプログラムは、IPAが試験要綱で公表する「擬似言語の記述形式」に従って記述される。変数・配列は「整数型: x」「文字列型: s」のように型名を付けて宣言し、代入は「←」で表す。選択処理は if〜elseif〜else〜endif、繰返し処理は前判定の while(条件式)〜endwhile、後判定の do〜while(条件式)、および for(制御記述)〜endfor の3系統がある。前判定は条件が偽なら一度も実行されないが、後判定は必ず1回は実行される点が頻出の引っかけである。手続・関数は「○整数型: fn(整数型: n)」の形式で宣言し、値の返却は return で行う。論理式には and・or・not を用いる。配列の要素番号は1から始まる旨が問題文に明記されるのが通例で、0始まりと思い込むと誤答する。プログラム読解では、変数の値の変化をトレース表に書き出して1行ずつ追跡するのが最も確実な解法である。

データ構造の基本は配列とリスト(連結リスト)である。配列は要素が連続した領域に格納されるため、添字を指定した参照はO(1)で行えるが、途中への挿入・削除は後続要素の移動が必要でO(n)を要する。一方、単方向リストは各要素(セル)がデータ部と次要素へのポインタ部をもち、挿入・削除はポインタの付替えだけで済むが、k番目の要素の参照には先頭から順にたどる必要がありO(n)かかる。この「参照は配列が速く、挿入・削除はリストが速い」というトレードオフは、科目A・科目B双方で繰り返し問われてきた定番論点である。双方向リストは前後2本のポインタをもち逆方向の走査が可能で、環状リストは末尾が先頭を指す。リストへの挿入処理では、新要素のポインタを先に設定してから前要素のポインタを付け替える、という順序を誤ると要素が失われる点が擬似言語問題の典型的な出題ポイントである。

スタックは後入れ先出し(LIFO: Last-In First-Out)の構造で、データの格納をpush、取出しをpopと呼び、常に最後に格納した要素が最初に取り出される。関数呼出しの戻り先管理、再帰処理の実現、逆ポーランド表記法(後置表記法)の式の評価、深さ優先探索などに用いられる。キューは先入れ先出し(FIFO: First-In First-Out)の構造で、格納をenqueue、取出しをdequeueと呼び、待ち行列の処理や幅優先探索などに用いられる。「A、B、Cの順にpushし、2回popすると取り出される順はC、B」のような操作列の追跡問題が科目Aの定番である。後置表記法「AB+」は中置表記法の「A+B」に相当し、オペランドをスタックに積み、演算子が現れたら2つ取り出して演算し結果を積み直す、という評価手順まで含めて理解しておく必要がある。

木構造は節(ノード)と枝で階層関係を表すデータ構造で、各節が高々2つの子をもつものを2分木という。2分探索木は「左部分木のすべての値<親の値<右部分木のすべての値」という制約をもち、平衡していれば探索はO(log n)で行えるが、木が偏ると最悪O(n)に劣化する。走査順には先行順(前順)・中間順(間順)・後行順(後順)の3種があり、2分探索木を中間順で走査すると昇順の整列列が得られる点は頻出である。ヒープは「親の値が子の値以上(または以下)」という制約だけをもつ完全2分木で、根が常に最大値(最小値)となり、優先度付きキューやヒープソートの基礎となる。2分探索木と異なり左右の子どうしの大小関係は不定である点を混同させる出題が多い。ハッシュ表はキーからハッシュ関数で格納位置を計算する構造で、平均O(1)の探索を実現するが、異なるキーが同じ位置に対応する衝突(シノニム)への対処が必要となる。

探索アルゴリズムでは、線形探索は先頭から順に比較する方法で、n個のデータに対する平均比較回数は約(n+1)/2回、計算量はO(n)である。2分探索は整列済みであることを前提に、中央の要素と比較して探索範囲を半分に絞り込む方法で、計算量はO(log n)となる。「整列済みが前提」という条件を落とした誤り選択肢が科目Aの定番の引っかけである。オーダ記法(O記法)は、データ量nの増加に対する処理時間の増え方を最高次の項だけで表す漸近的な尺度であり、係数や低次の項は無視する。O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2のn乗)という大小関係は暗記必須である。ハッシュ法による探索は衝突がなければデータ量に依存せずほぼO(1)であり、IPAシラバスでも線形探索法・2分探索法・ハッシュ表探索法の3方式として整理されている。

整列アルゴリズムは方式と計算量の対応が最頻出である。隣接要素の比較・交換を繰り返すバブルソート(交換法)、未整列部分から最小値を選び先頭と交換する選択ソート、整列済み部分の適切な位置へ挿入していく挿入ソートは、いずれも平均計算量O(n²)の基本整列である。クイックソートは基準値(ピボット)より小さい群と大きい群にデータを分割する操作を再帰的に繰り返す方式で、平均O(n log n)だが、分割が偏る最悪の場合はO(n²)に劣化する。マージソートとヒープソートは最悪でもO(n log n)を保証する。再帰関数は自分自身を呼び出す関数で、必ず停止条件(基底条件)をもち、階乗・フィボナッチ数列・マージソートなどの題材で問われる。科目B対策としては、IPA公開のサンプル問題・公開問題を擬似言語の記述形式と照らして実際にトレースし、ループの開始・終了条件や配列の端といった境界で誤りやすい箇所を体で覚えることが合格への最短経路である。