09 過去問演習ー2（全分野 横断・2周目）

正解：エ

配列 A の「＊」を、流れ図（i を 0〜7、その中で j を 0〜7 まで回す二重ループ）ですべて配列 B の別の場所へ写す問題です。空欄 a の代入式を選びます。

まず A がどんな形かを見ます。左端の列（j=1）に縦一本、上端の行（i=0）に横一本、真ん中あたり（i=3）にも横一本がある「F」のような形です。これが B ではどこへ動いたかを、目印になる「＊」で追いかけます。

A の上端の横棒 A(0,1)〜A(0,6) は、B では一番右の列（j=7）に縦に並んでいます。つまり「行の位置」が「列の位置」に化けています。1つだけ座標を代入して確かめます。

A の縦棒 A(0,1)〜A(7,1)（i が 0→7）はエだと B(1, 7)〜B(1, 0)、つまり第1行が左まで全部＊になります。図3の第1行がまるごと＊なのと一致します。

他の選択肢との違い

• ア B(7−i, 7−j)：点対称（180度回転）になる式。形が回るだけで、行と列の入れ替わりが起きないため図3にならない。
• イ B(7−j, i)：エと同じ「行と列の入れ替え」だが回す向きが逆。A(0,1) が B(6,0) に行き、＊の並びが図3と左右反対になる。
• ウ B(i, 7−j)：行はそのまま、列だけ左右反転。行と列が入れ替わらないので「横棒が縦棒になる」変化を説明できない。

速解法：「横に伸びた棒が縦に立った」＝行と列が入れ替わった、とわかった時点で B(●, ●) の中身が (j, …) で始まる選択肢（イかエ）に絞れます。あとは端の1点 A(0,1) を入れて、左右が合うほうを選べば一発です。

正解：ウ

逆ポーランド記法（後置記法）は「演算子を2つの値の“後ろ”に書く」書き方です。読むときは左から順にたどり、値はスタックに積み、演算子が来たら直前の2つを取り出して計算し、結果をまた積むという手順で元の式に戻せます。

式 EF－G÷CD－AB＋÷＋ を左から1文字ずつ処理します（「直前2つ」の順番に注意：先に取り出したほうが右側の値）。

最後に残った ((E−F)÷G)+((C−D)÷(A+B)) がウそのものです。

他の選択肢との違い：最後の演算子が ＋ なので、一番外側の計算は「たし算」でなければなりません。エは一番外が ÷ なので不適。ア・イは (A+B) や (E−F) の作られ方（後置の順序）が式と合いません。

速解法：後置記法は「一番右の演算子＝最後に行う一番外側の計算」です。この式の末尾は ＋ なので、外側が「÷」のエをまず消せます。次に末尾から2つ目のかたまりを見て、÷ でつながる形（ウ）に決まります。

正解：イ

スタックは「あとに入れたものを先に取り出す（LIFO）」箱です。PUSH は一番上に乗せ、POP は一番上を取り除きます。10個の命令を実行した後の一番下（＝最初のほうに入れて残ったもの）が何かを追います。

命令は次の順（PUSH が7回、POP が3回）です。PUSH には入れた順に P1〜P7 と番号を付けて追跡します。

問題文は「ある状態から」始めているので、スタックには最初から入っていた古いデータ（図の一番下の 29）があります。今回の10命令で入れて残ったのは、下から順に P1, P3, P4, P7 の4つです。これを図の上から 192, 55, 326, 7 に、その下の 29 は元からあったデータに対応させます。

よって1番目のPUSHで入れたデータは 7 です。

他の選択肢との違い：29（ア）はこの10命令より前から入っていた無関係なデータ。326（ウ）は4番目のPUSH、55（エ）は5番目のPUSHにあたり、いずれも「1番目」ではありません。

速解法：残る個数だけ先に数えると速いです。PUSH7回・POP3回なので今回ぶんは差し引き4個残ります。図の下から4個が今回のもの、5個目（29）は元から。今回ぶんの一番下＝最初のPUSHなので、下から4個目の 7 が答えです。

正解：イ

スタックは「あとに入れたものから先に取り出す（後入れ先出し・LIFO）」構造です。どの処理がこの性質にぴったり合うかを選びます。

イは「途中結果をいったんしまい込み、別の計算をしてから、直前にしまった途中結果を取り出して使う」という流れです。これは最後にしまったものを最初に取り出すというスタックの動きそのもので、電卓の計算やカッコ付きの数式の処理でよく使われます。

他の選択肢との違い

• ア：「格納した順番に取り出す」＝先に入れたものが先に出る（先入れ先出し）。これはキューの性質で、スタックとは逆です。
• ウ：「並んだ列の“中間”だけを変更する」＝途中の要素を直接いじる操作。スタックは端（上）しか触れないので不向き。配列向きです。
• エ：「リストの中間に挿入する」＝真ん中への出し入れ。これも端しか操作できないスタックには合わず、連結リスト向きです。

速解法：選択肢の中から「取り出す順番＝入れた順」（ア＝キュー）と「中間を操作」（ウ・エ＝配列やリスト）を先に消すと、残るイが自動的に答えになります。

正解：イ

スタック（後入れ先出し）とキュー（先入れ先出し）を同時に使う手続きです。関数の意味は、push(y)＝スタックに積む、pop()＝スタックの一番上を取り出して返す、enq(y)＝キューの末尾に入れる、deq()＝キューの先頭を取り出して返す、です。関数の引数の中身（enq(pop()) など）は先に内側を実行します。1行ずつ両方の中身を追います。

最後の pop() で取り出されるのはスタックの一番上にある b なので、x には b が入ります。

他の選択肢との違い：a（ア）はスタックの一番下でまだ取り出されていない。c（ウ）はキューの中に残ったまま。d（エ）は b の下にあり、最後の pop では取り出されません。

速解法：注目は最後の pop()＝スタックの一番上だけ。直前の push(deq()) でキュー先頭 b を積んだので、その b がそのまま取り出されます。キューの先頭は最初に enq(pop()) で入れた b なので、答えは b と即断できます。

正解：ウ

待ち行列（キュー）は「先に入れたものから先に取り出す（先入れ先出し・FIFO）」構造です。ENQ n は末尾に n を追加、DEQ は先頭を取り出します。操作を順に並べてトレースします。

ここまでで取り出された順は 1→2→3→4。次の DEQ で先頭にいるのは 5 です。

他の選択肢との違い：1（ア）・2（イ）はすでに取り出し済み。6（エ）は最後に入れたばかりで、まだ 5 の後ろに並んでいます。

速解法：キューでは「入れた順にそのまま出る」ので、取り出しは 1,2,3,4,5,… の順と決まっています。すでに DEQ が4回済んでいる（1〜4が出た）ので、次に出るのは自然と5番目に入れた 5 です。

正解：エ

配列と連結リストの違いを問う問題です。ポイントは2つ。配列は番号で一発アクセスできる（ランダムアクセス可）が、途中への挿入・削除では後ろの要素をずらす必要がある。連結リストは各要素が「次の要素の場所（ポインタ）」を持ってつながっており、挿入・削除はポインタの付け替えだけで済むが、目的の要素へは先頭から順にたどるしかない、という点です。

エは「挿入は数個のポインタを書き換えるだけなので短い」。連結リストの最大の長所そのものなので正しい記述です。

他の選択肢との違い

• ア：「更新する場合、ポインタを順にたどるだけなので短い」。連結リストは目的の要素まで先頭から順にたどるため時間がかかります。「短い」は誤り。
• イ：「削除で後ろの全要素を前に移動する」。これは配列の話。連結リストはポインタを付け替えるだけで移動は不要なので誤り。
• ウ：「参照はランダムアクセスできるので短い」。ランダムアクセスできるのは配列。連結リストはたどる必要があり不可なので誤り。

速解法：「ランダムアクセス」「後ろの要素をずらす」と書いてあれば配列の説明＝連結リストとしては不適、と切り分けられます。残る「ポインタを書き換えるだけで挿入できる」がリスト本来の長所で、これがエです。

正解：ウ

双方向リストは、各要素が「次の要素の場所（次ポインタ）」と「前の要素の場所（前ポインタ）」の両方を持ちます。まず追加前のつながりを読み取ります。

• 社員A(100)：次=300、前=0 … 先頭
• 社員K(300)：次=200、前=100
• 社員T(200)：次=0、前=300 … 末尾

つまり並びは A → K → T です。ここに社員G(400)を A と K の間へ入れ、A → G → K → T にします。変わるのは「差し込む隙間の両側だけ」なので、そこだけ確認します。

Gを差し込むと、A の「次」は G を指すよう変わり（a）、K の「前」も G を指すよう変わります（f）。社員T は隙間から離れているので、その次・前（c・d）は無関係で不変。K の「次」（e）も T のままで変わりません。よって変わるのは a と f だけ。

他の選択肢との違い：ア(a,b,e,f) は変化しない b・e を含み過剰。イ(a,e,f) は変化しない e を含む。エ(b,e) は実際に変わる a・f を含まず不足。ちょうど a・f だけのウが正解です。

速解法：双方向リストの「間に1個入れる」では、書き換わるのは必ず差し込む位置の左側の“次”と右側の“前”の2本だけ（新ノード自身のポインタは別途セット）。ここでは左=Aの次(a)、右=Kの前(f)。この2本、と覚えておけば即答できます。

正解：ウ

表現のルールは「(左部分木, 節番号, 右部分木)」で、部分木が無いところは x と書く、というものです。図の木を読み取ると、根は節3で、左の子が節2、右の子が節5。さらに、節2は左の子が節1だけ（右の子は無い）、節5は左の子が節4・右の子が節6です。

葉から順に文字にしていきます。

• 節1・節4・節6は子がいない葉なので、そのまま 1・4・6。
• 節2は左が1、右が無い（x）なので (1, 2, x)。ここが最大のポイントで、右の子が無い分を必ず x で埋めます。
• 節5は左が4、右が6なので (4, 5, 6)。
• 根の節3は、左部分木が節2の表現、右部分木が節5の表現なので ((1, 2, x), 3, (4, 5, 6))。

よって正解はウ。

なぜ他は違うのか：アは節2を (1, 2) と2つ組にしていて、右の子が無いことを x で示せていない（形が違う）ので誤り。イは (1, 2, 3) のように節3を節2の右の子に入れてしまい、根が3であることと矛盾。エは右部分木を (6, 5, 4) と左右逆に並べていて、節4が左・節6が右という図と合わないので誤り。

速解法：まず根がどれかを見て、いちばん外側のカッコの真ん中の数字が根と一致する選択肢に絞る（真ん中は3のはず）。次に「子が片方しか無い節2は必ず x が入る」ことを手がかりにすると、x を正しい位置に置いたウだけが残ります。

正解：イ

2分探索木のルールはただ一つ、「どの節点でも、左側にあるものは全部その節点より小さく、右側にあるものは全部その節点より大きい」です。ここで大事なのは「直接の子だけでなく、その下にぶら下がる全部」がこの条件を満たすことです。1か所でも破れていたらアウトなので、各選択肢を上から順にチェックします。

• ア（根16）：左の子15の、そのまた右の子が14。14は15より小さいので、15の右にあってはいけません。ルール違反でアウト。
• イ（根17）：左部分（14を根に10と16）は全部17より小さく、10<14<16の並びも正しい。右部分（19の左に18）は全部17より大きく、18<19も正しい。すべてOK。これが答え。
• ウ（根18）：左の子16の右の子が14。14は16より小さいのに右にあるのでアウト。
• エ（根20）：右の子19の右の子が16。16は19より小さいのに右にあるのでアウト。さらに19は根20の右にあるべきなのに20より小さく、ここも変です。

速解法：親と子の大小だけでなく、「小さい方の子は左、大きい方の子は右」を全部の節点で確認するだけ。特に「右の子なのに親より小さい数」を見つけたら即アウト、という目で探すと速いです。ア・ウ・エはいずれもこのパターンで外れます。

正解：エ

問題の木は「葉以外は必ず子が2つ」「根から葉までの深さが全部同じ」というきれいに詰まった2分木（完全に埋まった2分木）です。深さは根から葉までの枝の本数で数えます。小さい例で確かめると法則がすぐ見えます。

たとえば深さ2の木（節点は根1個＋その下2個＋さらに下4個＝合計7個、葉は4個）で各選択肢を検証します。

エが正しい理由をもう少し。この形の木では、根から順に節点が2倍ずつ増えていくので、葉の数がちょうど（葉以外の節点の数）＋1になります。だから葉がn個なら、葉以外はn-1個です。

速解法：迷ったら「深さ1の一番小さい木（節点3個・葉2個・枝2本）」や「深さ2の木」を実際に描いて数を当てはめるのが最速で確実。公式を暗記するより、小さい例で選択肢を1つずつ潰すのがおすすめです。

正解：エ

隣接行列は「どの節点とどの節点が枝でつながっているか」を表です。第 i 行 第 j 列が 1 なら、節点 Vi と Vj の間に枝があります。行ごとに 1 の場所を読み取って、枝の一覧を作ります。

重複を除くと、枝は V1-V2、V1-V3、V2-V4、V3-V4 の4本です。逆に V1-V4 はなく、V2-V3 もない点が重要です。各節点の枝の本数（次数）はすべて2本ずつになります。

この4本の枝をちょうど持ち、V1-V4 と V2-V3 を持たない図はエです。エは V1 が V2・V3 とつながり、真ん中の V4 が V2・V3 とつながっていて、これが上の一覧と完全に一致します。よってエが正解です。

他の選択肢がなぜ違うか。

• ア：V1 が V4 とだけつながり（V1-V4 がある）、さらに V2-V3 もある。必要な V1-V2・V1-V3 がなく、不要な枝を持つので不一致。
• イ：V1 が V2・V3・V4 の3本とつながり、V2-V3 もあるなど枝が多すぎ。次数が2にならず不一致。
• ウ：V1 が V2・V3 に加えて V4 ともつながる（V1-V4 がある）が、行列に V1-V4 は無い。逆に必要な V2-V4・V3-V4 が足りず不一致。

速解法：行列は左上から右下への対角線を境に上下が鏡写し（対称）になっているはずで、まずそれを確認。あとは「ある枝」より「無い枝」に注目するのが速く、V1-V4 なし・V2-V3 なしを満たす図はエだけなので一発で絞れます。

正解：イ

「再帰的（リカーシブ）」とは、プログラムが実行の途中で自分自身をもう一度呼び出せる性質のことです。階乗やフィボナッチ、木のたどり方（この回の問7でも登場）などが代表例で、まさにイの説明そのものです。

まぎらわしいのは、名前の似た「再〇〇可能」という別の性質が選択肢に並んでいる点です。区別して覚えましょう。

速解法：この4つはよくセットで出題されます。「再帰＝自分を呼ぶ」「再使用＝もう一度使える」「再配置＝どこに置いてもよい」「再入＝同時に共有できる」と、キーワードだけ結びつけて暗記しておけば確実に得点できます。

正解：イ

この関数Fはユークリッドの互除法（2つの数の最大公約数を求める方法）そのものです。「yが0になったら、そのときのxが答え」「yが0でなければ、(y, xをyで割った余り) に置きかえて繰り返す」というルールに従い、ただ計算をたどるだけです。x mod y は「xをyで割った余り」です。

yが0になった瞬間のxが答えなので、3、すなわちイです。実際、231と15の最大公約数は3（231＝3×7×11、15＝3×5）なので、計算が正しいことも確認できます。

速解法：この形の関数を見たら「これは最大公約数を求める互除法だ」と気づけると強いです。あとは表を1行ずつ、割り算の余りを次のyに送るだけ。余りが0になったときの割る数（この問では最後のx＝3）が最大公約数＝答えになります。ア・ウ・エは途中計算のどこかで割り算の余りを取り違えると出てしまう値ですが、余りを丁寧に出せば3で確定します。

正解：ウ（n > M）

2つの流れ図が同じ x になるようにする問題です。まず左の流れ図が何を計算しているかを確定させ、次に右がそれと同じになる条件を探します。

左の流れ図：x←1 のあと、ループで n を M から 1 まで −1 ずつ動かしながら x←x×n を繰り返します。つまり

x = M × (M−1) × … × 2 × 1 = M!（M の階乗）

右の流れ図：x←1, n←1 のあと、「x←x×n → n←n+1 → 判断a」を繰り返します。判断が Yes なら終了、No ならループの先頭へ戻ります。判断は掛け算のあとにある点が重要です。k 回まわった時点の状態を表にします。

左と同じ M! にしたいので、ちょうど M 回まわった直後に終了させたい。そのとき n は M+1 になっています。よって条件 a は「n が M+1 以上になったら Yes」＝ n > M。これがウです。

なぜ他の選択肢が違うか（1回ずれると階乗が丸ごと変わります）

• ア n < M：n は 2, 3, … と増えるので、最初から条件を満たしてすぐ終了してしまい、x=1! のような小さい値で止まります。そもそも増える変数に「小さければ終了」は不適切。
• イ n > M−1：n ≥ M で終了＝k = M−1 回で止まるので x = (M−1)!。1回足りない。
• エ n > M+1：n ≥ M+2 で終了＝k = M+1 回まわるので x = (M+1)!。1回多い。

速解法：この手の「後判定ループの条件を埋める」問題は、小さい M で試すのが最速です。たとえば M = 3（左は 3! = 6）とし、右で x が 6 になった瞬間の n を見ると n = 4。n = 4 のとき初めて Yes になる条件を選択肢から探すと、n > 3（＝n > M）だけが当てはまります。

正解：ア

オーダとは「データの数nが増えたとき、処理時間がおよそどのくらいの勢いで増えるか」を表すものです。3つの探索法それぞれの速さを思い出せば選べます。

この「log2 n ／ n ／ 1」の組合せがそろっているのはアだけなので、答えはアです。

他の選択肢との違い：イは2分探索を n log2 n としていて遅すぎ（これは整列アルゴリズムの目安）。ウは線形探索を n の2乗としていて誤り。エは2分探索を n の2乗、線形探索を1としていて、速い遅いが完全に逆さまです。3つのうちハッシュ探索がデータ数によらず一定（1）で最も速いと押さえておけば、1が入っていないイをまず外せます。

速解法：「2分探索＝log、線形探索＝n、ハッシュ＝1（一定）」の3点セットを暗記しておけば即答できます。半分ずつ絞るものはlog、1個ずつ見るものはn、直接飛べるものは1、と仕組みと結びつけると忘れません。

正解：イ

探索は「①どのブロックにあるか探す」→「②そのブロックの中を探す」の2段階です。それぞれの平均比較回数を出して足し算します。

①ブロックを探す段階

• 全体は n 個で、m 個ずつのブロックに分けるので、ブロックの数は n/m 個です。
• 各ブロックの「最後尾のデータ」だけを、先頭から順に線形探索して当たりのブロックを探します。
• 線形探索の平均比較回数は「候補の個数の約半分」なので、n/m 個を調べる平均は n/(2m) 回です。

②ブロックの中を探す段階

• 当たったブロックの中は m 個です。この中を線形探索します。
• 平均比較回数は個数の半分なので m/2 回です。

合計＝ m/2 + n/(2m)。これがそのままイの式です。

なぜ他が違う？

• ア（m + n/m）…「半分」の割り算を忘れて、個数そのものを比較回数にしてしまった形。平均ではなく最悪回数に近い。
• ウ（n/m）…ブロックを探す回数だけ。ブロックの中を探す②が抜けている。
• エ（n/(2m)）…①の平均だけ。②の m/2 が抜けている。

速解法：「2段階探索は各段階の平均（＝候補数の半分）を足す」。ブロック数 n/m の半分と、ブロック内 m の半分を足すだけ、と覚えるとすぐ選べます。

正解：ア

2分探索は「まん中を見て、目的が前半か後半かを判断し、探す範囲を毎回半分に絞る」方法です。範囲を半分に切れるのは、データが小さい順（または大きい順）に並んでいる（整列済み）からこそです。だからアが正しい説明です。

なぜ他が違う？

• イ…「常に速い」が誤り。データがごく少ないときは、まん中を計算する手間の分、単純な線形探索の方が速いこともあります。「常に」は言い過ぎ。
• ウ…先頭から順に見るのは線形探索。2分探索が最初に見るのはまん中です。
• エ…比較回数は log₂n（範囲を半分ずつにするので回数はおよそ底2の対数）に比例します。n log₂n はマージソートなど「整列」の計算量で、探索1回の回数ではありません。

速解法：2分探索のキーワードは「整列済みが前提」「まん中から」「1回で半分に絞る＝log₂n」。この3点でほぼ判定できます。

正解：エ

これはハッシュ法で、置きたい場所が埋まっていたら次の候補へずらす（オープンアドレス法）問題です。規則どおり 16→43→73→24→85 の順に置いていき、最後の 85 がどこに入るかを追います（x mod 10 は「10で割った余り」＝1の位）。配列は最初すべて0です。

85 は最初の候補（5番）も次の候補（6番）も埋まっていて、規則(3)の (k+4) mod 10 = 9 でようやく空いていた A[9] に入ります。よってエ。

なぜ他が違う？ア A[3]・イ A[5]・ウ A[6] は、いずれも 85 が置こうとしたがすでに埋まっていた場所です。「余りが同じでも先客がいれば次へずらす」ことを見落とすとこれらを選んでしまいます。

速解法：先に 16→43→73→24 の置き場所（6,3,4,5番）をメモしておき、85 の候補 5→6→9 と照らせば一発です。

正解：ア

クイックソートは「基準となる値（ピボット）を1つ決め、それより大きいグループと小さいグループに振り分ける（分割する）」のがポイント。分けた各グループでまた同じことを繰り返すと、最後には並びます。これを説明しているのがアです。

なぜ他が違う？（有名な整列アルゴリズムの説明とすり替えてあります）

• イ…「最も小さい要素を順に取り出す」は選択ソートの説明。
• ウ…「取り出して、並びを保つよう挿入する」は挿入ソートの説明。
• エ…「隣り合う要素を比べて逆なら交換」はバブルソート（交換法）の説明。

速解法：クイックソートのキーワードは「基準（ピボット）で大小2つに分割」「それを繰り返す（分割統治）」。この2語があればア確定です。