基本情報技術者の科目B擬似言語はこう読む|基礎構文と頻出5パターン(配列・連結リスト・スタック・再帰・OOP)

基本情報技術者対策の第3回です。合格ライン600点を超えるための核心、科目B擬似言語の基礎構文と頻出5大処理パターンを扱います。学習時間の6〜7割をここに投じましょう。

科目Bの全体像と時間配分

出題配分はアルゴリズムとプログラミングが16問(約8割)、情報セキュリティが4問(約2割)。目標所要時間は情報セキュリティ(問17〜20)計15〜20分、アルゴリズム短文・基本問題1問あたり約4分、長文・応用問題1問あたり約6分、見直し5分。

擬似言語の基礎構文

代入と配列:x ← 10(xに10を代入)、array[1] ← 5(配列添字は原則「1始まり」が多い、問題文を必ず確認)

条件分岐:if(条件式) 処理1 elseif(条件式2) 処理2 else 処理3 endif

繰り返し:for(iを1から10まで1ずつ増やす) 処理 endfor / while(条件式) 処理 endwhile

パターン1:配列の走査と集計・極値探索

配列の中から最大値・最小値を見つける基本形です。

試験のツボ:
①初期値の設定で最大値の初期値に0を入れると、配列がすべて負の数だった場合にバグが発生する。必ず配列の先頭要素で初期化する。
②ループの開始点は、初期値に1番目の要素を使った場合、2から開始するのが定石。

図解:配列の最大値探索のトレース
配列の最大値探索のトレース

パターン2:連結リスト(ポインタ操作)

配列を用いた「単方向連結リスト」の実装です。data(値を格納する配列)、next(次の要素の添字を格納する配列、-1は末尾)、head(先頭要素の添字)という構成で、cur ← head として while(cur ≠ -1) でnextを辿りながら出力していきます。物理的なメモリの並び順と、論理的なデータ順序(ポインタ)が異なる点を把握することが重要です。

図解:連結リストのたどり方
配列で作る 単方向連結リスト添字1234dataBDACnext4−112head = 3A添字3B添字1C添字4D添字2−1=末尾cur ← headcur ← next[cur]cur が −1 で終了

パターン3:スタックとキューの操作

スタック(LIFO):push処理はtop ← top + 1してstack[top] ← xで積む。pop処理はval ← stack[top]を取り出しtop ← top - 1で減らす。topが0のときのpopはアンダーフローエラー。

リングバッファによるキュー(FIFO):剰余演算(mod)を利用して配列の末尾に達したら添字1に戻す処理が頻出。tail ← (tail mod MAX_SIZE) + 1、head ← (head mod MAX_SIZE) + 1

図解:スタックとキュー
スタックと キューCBApushpopスタック:後入れ先出し(LIFO)ABCenqueuedequeueキュー:先入れ先出し(FIFO)関数呼出し・元に戻す → スタック / 印刷待ち・処理待ち → キュー

パターン4:再帰関数とコールスタック

再帰処理は「終了条件」と「引数の変化」を追跡します。ユークリッドの互除法gcd(a,b)の例:bが0ならaを返す、そうでなければgcd(b, a mod b)を返す。

トレースの書き方:gcd(24,9)→gcd(9,6)→gcd(6,3)→gcd(3,0)でb=0に到達し「3」を返す。再帰が深くなるときは、戻り値が下から上へバケツリレーのように返っていく様子を矢印でメモする。

図解:再帰関数のトレース
再帰のトレース:gcd(24, 9)gcd(24, 9)24 mod 9 = 6gcd(9, 6)9 mod 6 = 3gcd(6, 3)6 mod 3 = 0gcd(3, 0)b=0 → 3 を返す3333戻り値が上へ終了条件(b=0)と 引数の変化(b, a mod b)を必ずメモする

パターン5:オブジェクト指向(クラス・継承)

近年の擬似言語では、カプセル化・継承・ポリモーフィズムを用いたクラス設計問題が定番化しています。

頻出チェックポイント:initialize(コンストラクタ、生成時に自動実行される初期化処理)、extends(継承関係、子クラスは親クラスの変数・メソッドを引き継ぐ)、メソッドのオーバーライド(子クラス側で処理を上書き定義した場合、子クラスのインスタンスでは上書き後の処理が優先実行される)。

トレース(変数追跡)の極意

科目Bの点数が伸びない最大の原因は「頭の中だけでプログラムを動かすこと」です。余白用紙にループ回数・変数の変化を表形式で愚直にメモする習慣を徹底してください。

境界値チェックの必須テクニック:選択肢が「x < n」か「x <= n」か迷った場合、要素数が1個または2個の極小ケースを仮定して手動トレースする。ループの「1周目」と「最終周」の変数値だけを代入して確認する。

実戦演習:文字列圧縮(ランレングス法)

連続する同一文字を「文字」と「連続する回数」の組に変換して圧縮する処理で、ループ終了後に最後の文字群がまだresultに結合されていない、という点が最重要トラップです。極小データ"AAB"でトレースすると、ループ終了時点でBの1文字分が未結合であることが分かり、ループの外で最後の文字とその回数を結合する処理が必要と判明します。

次回は「科目Bセキュリティ実践+科目A最新トレンド」編で、フィッシング対策・ランサムウェア対応、AI・クラウド・アジャイルの最新出題を扱います。

配列と再帰のトレースを4択で

問題1

関数gcd(a, b)は「bが0ならaを返し、そうでなければgcd(b, a mod b)を返す」。gcd(30, 12)の戻り値はどれか。

  1. 2
  2. 3
  3. 6
  4. 12

正答:3

  • 肢1 × 2は30と12の公約数だが最大ではない。
  • 肢2 × 3も公約数の一つだが最大ではない。
  • 肢3 ○(正答) gcd(30,12)→gcd(12,6)→gcd(6,0)でbが0になり6を返す。
  • 肢4 × 12は最初の引数bの値で、30を割り切れないので最大公約数ではない。

問題2

空のスタックに対して push(1)、push(2)、pop()、push(3)、push(4)、pop() の順に操作した。このとき、スタックの一番上にある値はどれか。

  1. 1
  2. 2
  3. 3
  4. 4

正答:3

  • 肢1 × 1は最初に積んだ値で、スタックの一番下にある。
  • 肢2 × 2は1回目のpop()で取り出されている。
  • 肢3 ○(正答) [1,2]→pop→[1]→[1,3]→[1,3,4]→pop→[1,3]なので一番上は3。
  • 肢4 × 4は最後に積まれたが、2回目のpop()で取り出されている。

問題3

要素数5の配列でリングバッファを作り、末尾の添字を tail ← (tail mod 5) + 1 で進める。tailが5のとき、この処理を1回行った後のtailの値はどれか。

  1. 0
  2. 1
  3. 5
  4. 6

正答:2

  • 肢1 × 5 mod 5=0だが、そのあと1を足すので0にはならない。添字が1始まりの配列なので0は使わない。
  • 肢2 ○(正答) (5 mod 5)+1=0+1=1。末尾の次は先頭(添字1)に戻る。
  • 肢3 × tailが変わらないと、同じ位置に上書きし続けてしまう。
  • 肢4 × 6は単純に1を足した値で、配列の範囲を超えてしまう。

擬似言語のトレースで迷う所

よくある間違い正しい理解
最大値を求めるときの初期値は0でよい要素がすべて負の数だと誤る。配列の先頭要素で初期化する
ランレングス圧縮はループ内の処理だけで完成するループ終了後に、最後の文字とその回数を結合する処理が必要
子クラスでオーバーライドしても親クラスのメソッドが動く子クラスのインスタンスでは、子クラスで上書きした処理が実行される
擬似言語の配列は必ず0から始まる1始まりの出題が多いが、問題文の定義を必ず確認する

擬似言語の記述ルールの公式資料

コメント

このブログの人気の投稿