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

正解：エ

この問題は「10進数を2進数に直す筆算」を、そのまま流れ図にしたものです。まずは手で計算するやり方を思い出しましょう。

10進数を2進数にするときは、2で割った余りを下から順に並べるのでしたね。たとえば13なら：

出てきた余りを下から読むと 1101。これが13の2進数です。ここで大事なのは、最初に出た余りが2進数のいちばん下の桁（1の位）だということ。問題文でも「2進数は下位桁から順に NISHIN(1) から格納される」と書かれていて、この筆算の順番とぴったり一致します。

流れ図と筆算を対応させる

ループは k : 1, 1, 8、つまり k が1から8まで1ずつ増えながら8回まわります。1回のループで「1桁分」を作るわけです。1回のループの中でやるべきことは2つだけ：

1. 余りを取り出して配列にしまう … NISHIN(k) ← j mod 2
2. 次の桁のために j を2で割った商に更新する … j ← j div 2

この2つが a と b に入ります。ということは、問題は「どっちを先にやるか」だけです。

順番がひっくり返るとどうなるか（ここが最大のポイント）

j ← j div 2 を先にやってしまうと、j の中身が書き換わってしまいます。その後で j mod 2 を計算しても、それはもう「元の j の余り」ではなく「割った後の j の余り」＝ひとつ先の桁の値になってしまいます。j = 13 で実際に確かめてみましょう。

逆順だと、いちばん下の桁（1の位）がまるごと消えて、答えが「13を2で割った6」になってしまいました。だから a に NISHIN(k) ← j mod 2、b に j ← j div 2 の エ が正解です。

ほかの選択肢がダメな理由

• ア：上で試した「逆の順」そのものです。先に j を割ってしまうので、1の位が失われて答えが半分の値になります。
• イ：j ← j mod 2 としているのが致命的です。j が余り（0か1）に置き換わってしまうので、2回目以降は j が 0 か 1 のまま動かなくなり、変換がそこで死んでしまいます。しかも配列には商を入れており、役割が完全に逆です。
• ウ：配列に商を入れ、j に余りを入れています。イと同じく j が壊れ、格納する値も間違いです。

速解法

この形の問題は、選択肢を全部トレースする必要はありません。次の2段階でふるいにかけます。

1. 「配列に入るのは余り、変数を更新するのは商」と決める。これで イ と ウ が即消えます（j に mod を代入している時点でアウト）。
2. 残った ア と エ は順番違いだけ。「保存してから壊す」が鉄則なので、余りを配列にしまう方が先 → エ。

合言葉は「取ってから割る」。使う予定の値を、使う前に上書きしてはいけない――これは流れ図の穴埋め問題で何度も出てくる考え方なので、覚えておくと得です。

正解：エ

逆ポーランド表記法（後置記法）は「計算する2つの数を先に書き、記号（＋−＊）を後ろに書く」書き方です。a+b なら ab+ と書きます。読むときは、記号が出たらその直前の2つを計算します。かっこは要りません。

選択肢エの逆ポーランド abcd−＊＋ を、左から順に処理して元の式に戻してみます（スタックに積んでいくイメージ）。

できあがった式は a+(b*(c−d))。これは選択肢エの左側の計算式とぴったり一致します。よってエが正解です。

なぜ他が違うのか（各組を実際に戻すとズレます）：

• ア 逆ポーランド abc＊+d− を戻すと、c＊→(b×c)、+→a+(b×c)、d−→(a+(b×c))−d となり、左の式 ((a+b)*c)−d と食い違います。
• イ 逆ポーランド ab+c＊d− を戻すと ((a+b)*c)−d になり、左の式 (a+(b*c))−d と食い違います（アとイは式と表記が入れ替わっています）。
• ウ 逆ポーランド abc＊d−+ を戻すと a+((b*c)−d) となり、左の式 (a+b)*(c−d) と食い違います。

速解法：逆ポーランドは「記号が出たら直前2つを計算して、その結果をまた1つの数として置く」を左から順にやるだけ。頭からたどって元の式に戻し、左の計算式と一致するものを選べば確実です。

正解：イ

スタックは「あとで入れたものを先に取り出す（後入れ先出し・LIFO）」データ構造です。計算式の処理では「いま計算している途中の値をいったん置いておき、別の計算を先に済ませてから、さっき置いた値を取り出して使う」という場面でスタックが役立ちます。この特徴に合う選択肢を探します。

• ア：入れた順番どおりに取り出すのは「先入れ先出し（FIFO）」で、これはキューの動きです。スタックではありません。
• イ：途中結果をしまい、別の計算をしたあとで、その結果と途中結果を計算する——まさに「あとで取り出して使う」LIFOの動きで、スタックが最適。よって正しい。
• ウ：昇順に並んだ列の真ん中だけを書き換える、という操作はスタックの得意分野ではありません（途中を直接いじれない）。
• エ：リストの途中に新しい要素を挿入するのは連結リストの得意技で、スタックとは違います。

速解法：選択肢の中で「取り出す順番が入れた順の逆」または「途中でしまって後で戻ってくる」と読めるものがスタック。ア＝キュー、エ＝リスト、と型を見分ければイが残ります。

正解：イ

2分探索木のきまりは「どの節点でも、左側の枝にぶら下がる値はすべて自分より小さく、右側の枝にぶら下がる値はすべて自分より大きい」です。しかも“直接の子だけ”でなく“その下全部”について成り立つ必要があります。各選択肢の根から順にチェックします。

• ア：根が1なのに、その左の子が2。左は自分より小さくないといけないのに2＞1で違反。誤り。
• イ：根4。左側は2・1・3ですべて4未満、右側は8・6・9・5・7ですべて4より大きい。節2は左1・右3でOK。節8の下は6・5・7で全部8未満、右9はOK。節6は左5・右7でOK。すべての節点できまりを満たすので正しい。
• ウ：根7の右側に8があり、その左の子が3。3は根7の右側にいるのだから7より大きくなければならないのに3＜7で違反。誤り。
• エ：根9の右側に8があり、その下に5・6など9より小さい値が並ぶ。根の右側はすべて9より大きいはずなので違反。誤り。

よって正解はイ。

速解法：2分探索木は「左下から右上へ、下から順に読むと（中間順走査）値が小さい順にきれいに並ぶ」性質があります。イを左下から順にたどると 1,2,3,4,5,6,7,8,9 と昇順になり、正しいと確認できます。手早くは、根の左枝に根以上の数・右枝に根以下の数が混ざっている選択肢（ア・ウ・エ）を一発ではじけます。

正解：イ

手続 proc(n) がやることは、日本語にすると次の3行だけです。

1. n が 0 なら何もせず戻る（＝ここで打ち止め）
2. そうでなければ：n を印字 → proc(n-1) を呼ぶ → もう一度 n を印字

ポイントは「1つの n につき、印字が2回ある」こと。しかも2回目の印字は、呼び出した proc(n-1) が全部終わって戻ってきてから行われます。

呼び出しの流れをトレースする

proc(5) を実行すると、次のように内側へ潜っていき、0 で折り返して戻ってきます。

最終的な出力は 5432112345（10桁）。これが選択肢イです。

形で覚える

出力は 5 4 3 2 1（下りながらの印字）と 1 2 3 4 5（戻りながらの印字）をそのままつなげた形になります。真ん中が … 2 1 | 1 2 … と1が2つ並ぶのが特徴です。n=0 のときは印字せずに戻るので、0 はどこにも出てきません。

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

• ア（543212345／9桁）…真ん中の 1 が1つしかありません。これは「1 の印字が下りで1回きり」の形で、戻りのときの印字を数え忘れたパターンです。proc(1) も他と同じく印字を2回するので、1 は2回出ます。
• ウ（54321012345／11桁）…真ん中に 0 が入ってしまっています。proc(0) は「0 ならば戻る」で、印字する行に到達せずに帰ってしまうので、0 は絶対に出力されません。「n を印字してから 0 かどうか判定する」と読み違えるとこうなります。
• エ（543210012345／12桁）…0 が2回入っています。ウの間違い（0 を印字してしまう）に加えて、その0でも「印字→戻って印字」の2回が行われたと考えた形です。ウと同じ理由で、0 は1回も出ません。

速解法

• その1：小さい数で試す。頭の中で proc(1) をやってみると「1を印字 → proc(0)は何もしない → 1を印字」で 11。次に proc(2) は「2 → (proc(1)=11) → 2」で 2112。この時点で「真ん中は 11 で、0 は出ない」と分かるので、0 を含むウ・エは即除外、1が1つのアも除外。残るイが正解です。再帰は n=1 や n=2 の小さいケースで形を掴むのが最速です。
• その2：桁数で絞る。1〜5 の各 n が2回ずつ印字するので、出力は必ず 5 × 2 = 10 桁。選択肢の桁数を数えるだけで、9桁のア・11桁のウ・12桁のエが消え、10桁のイだけが残ります。これが一番速い解き方です。
• その3：左右対称（回文）に注目。「印字→再帰→印字」という再帰呼び出しを印字で挟む形は、必ず左右対称の出力になります。イの 5432112345 は左から読んでも右から読んでも同じ。アは対称ではないので、この時点で落とせます。

正解：イ

この関数は「自分自身を呼び出す（再帰）」形で書かれていますが、やっていることはユークリッドの互除法、つまり2つの数の最大公約数を求める手続きです。

ルールはたった2行です。

• 2番目の引数 y が 0 になったら、そのときの x を答えとして返す（これが再帰の終わり＝ベースケース）。
• そうでなければ、(x, y) を (y, x を y で割った余り) に置きかえて、もう一度同じ関数を呼ぶ。

つまり「割った余りを次の相手にして、余りが0になるまで繰り返す」だけです。f(775, 527) を順に追いかけます。

4回目でついに y = 0 になったので、そのときの x である 31 が返されます。ここで大事なのは、返ってきた 31 はそのまま一番外側まで戻るという点です。else の行が return f(...) と書かれていて、途中で足したり掛けたりしていないからです。だから f(775, 527) の値も 31 になります。

検算：775 = 31×25、527 = 31×17。確かに両方 31 で割り切れ、25 と 17 にはこれ以上の共通の約数がないので、最大公約数はぴったり 31 です。

なぜ他の選択肢が違うか

• ア（0）：「最後に y が 0 になって終わる」ところだけを見て、0 を答えにしてしまった間違い。返すのは y ではなく x です。
• ウ（248）：1回目の余りです。1ステップで止めてしまうとこうなります。余りが 0 になるまで続けるのがルールです。
• エ（527）：最初に与えられた y の値そのもの。何も計算していない状態です。

速解法：if y = 0 then return x という形を見たら、中身を細かく追う前に「これは最大公約数（gcd）だ」と決めうちしてよいです（試験で頻出の超定番パターン）。あとは 775 と 527 の最大公約数を求めるだけ。差をとる手も速く、775 − 527 = 248 なので「248 と 527 の共通約数」を考えればよく、527 = 248×2 + 31、248 = 31×8 でちょうど割り切れる → 答え 31。選択肢のうち 775 と 527 の両方を割り切れる数は 31 しかない、という消去法でも一瞬で決まります。

正解：エ

この問題は、次の手順をぐるぐる繰り返す手続きです。ポイントは②と④の2つの代入です。

• ② y ← f(x)（x を関数に入れた結果を y にする）
• ④ x ← y（その y を次の x にする）
• ⑤で②に戻り、また繰り返す

問題文は「十分に繰り返した後、③で表示される y の値に変化がなくなった」と言っています。「もう値が変わらなくなった＝落ち着いた状態（収束）」ということです。この落ち着いた状態では、繰り返す前と後で x も y も同じ値になっています。そこで x も y も同じ値だと考えて②の式を見ます。

②は y = f(x)。落ち着いた状態では ④によって x と y は等しい（x = y）ので、②の x を y に置きかえられます。すると y = f(y) となります。これが選択肢エです。

数値でイメージしましょう。もし f(x)=(x+2)÷2 のような手続きだと、繰り返すうちに y は 2 に近づいて止まります。そのとき f(2)=(2+2)÷2=2 となり、確かに「y に f を入れても y のまま」＝ f(y)=y が成り立っています。

なぜ他が違うのか：

• ア f(a)=y の a は最初の1回目に使う初期値（①）だけの値です。何度も繰り返して落ち着いた後の関係とは無関係なので誤り。
• イ f(y)=0 は「答えが必ず0になる」という決めつけで、この手続きにそんな条件はありません。
• ウ f(y)=a も、落ち着いた後の値が初期値 a に戻る理由がなく誤り。

速解法：「値が変わらなくなった」＝「もう1回入れても同じ」という意味。②の y=f(x) で x=y とみなして f(y)=y、と機械的に導けます。

正解：ア

2分探索は、真ん中を1回調べるたびに「探す範囲」がちょうど半分に減っていく探索法です。だから「n個を何回半分にすれば1個になるか」を数えれば、それがおよその比較回数になります。

この「半分に減らせる回数」がまさに log₂n です。たとえば n=8 なら 8→4→2→1 で3回、log₂8＝3。n=16 なら 16→8→4→2→1 で4回、log₂16＝4。ぴったり合いますね。

ほかの選択肢がなぜダメか整理します。

• イ（(log₂n＋1)／2）…もっともらしい式ですが、2分探索の計算量はこんな形にはなりません。半分ずつ減る回数はそのまま log₂n です。
• ウ（n）…先頭から1個ずつ順に調べる「線形探索」の比較回数です。2分探索はこれよりずっと速いので不適切。
• エ（n²）…データ数の2乗。これはバブルソートなど「遅い整列」の計算量で、探索1回の回数としては大きすぎます。

速解法：「範囲が毎回半分になる＝log₂n」はセットで暗記。選択肢に log₂n があれば2分探索・木のたどり方の問題ではそれが本命です。

正解：エ

ハッシュ法の「衝突」を題材にした問題です。ハッシュ法とは、データを計算でしまう場所を決める方法のこと。今回のルールはとてもシンプルです。

• キーは小文字1文字（a〜z）
• その文字のASCIIコードを10進数で書いたときの、1の位の数字が、しまう場所の番号になる

衝突とは、違うキーなのにしまう場所が同じになってしまうことです。つまりこの問題は、「1の位が同じになるペアはどれ？」を探すだけです。

ASCIIコードの求め方

問題文に「アルファベット順に、連続した番号が割り当てられている」とあります。a が 97 であることだけ覚えておけば、あとは順に足していくだけです。

※「aから数えて何番目か」は、a=0, b=1, c=2, … と 0 から数えます。たとえば x はアルファベットの24文字目なので、0から数えると23。よって 97+23＝120 です。

選択肢を1つずつ確認

d も x も 0番の場所に入ろうとするので、これが衝突。よって エ が正解です。

速解法：コードを計算しなくても解ける

実は、97 を足し算する必要すらありません。ここがこの問題のうまいところです。

2つの文字の1の位が同じになるのは、2つのコードの差が10の倍数のときです。そしてコードはアルファベット順に1ずつ増えるので、コードの差＝アルファベット順の差。つまり、

「アルファベット順で10個ちょうど離れている（10、20個…離れている）ペアを探す」だけでよいのです。

• ア：a(1番目) と i(9番目) → 差は 8。✘
• イ：b(2番目) と r(18番目) → 差は 16。✘
• ウ：c(3番目) と l(12番目) → 差は 9。✘（あと1つで当たり、という「ひっかけ」です）
• エ：d(4番目) と x(24番目) → 差は 20 ＝ 10の倍数。✔

この解き方なら、指を折って数えるだけで10秒で終わります。

ここで間違えやすいポイント

• 「a は 1 番目だから 1」と勘違いしない。使うのはあくまでASCIIコードの1の位です。ただし速解法のように「差」だけを見るなら、1番目から数えても0番目から数えても差は変わらないので、どちらでも大丈夫です。
• ウの c と l（差9）は要注意。9と10は見た目が近く、数え間違えると当たりに見えてしまいます。c を3番目、l を12番目としっかり確認しましょう。
• ハッシュ表の大きさが10で、1の位（0〜9）がちょうど0番〜9番に対応します。「表からはみ出す番号は出ないか？」も本来の確認ポイントですが、1の位は必ず0〜9なので問題ありません。

なお、衝突が起きたときは、次の空いている場所を探す方法や、同じ場所にリストでつなげる方法（チェイン法）で対処します。あわせて押さえておきましょう。

正解：エ

この問題は「整列法の名前」と「その説明」がわざと入れ替えられていて、正しく対応している1つを選ぶ形です。1つずつ「名前と中身が合っているか」を確かめます。

エだけ「ヒープソート」という名前と「木（ヒープ）を作って端の最大・最小を取り出す」という中身がぴったり合っています。だから正解はエです。

ア・イ・ウは、名前は違うのに中身がぐるっとローテーションで入れ替わっているのがポイント。中身自体は正しい整列法の説明なので、つい「合っている」と錯覚しやすいワナです。

速解法：まず各選択肢の「中身」だけ読んで本当の名前を当て（間隔→シェル／隣→バブル／基準値で振り分け→クイック／木→ヒープ）、名乗っている名前と一致する1つを探す。単語対応さえ覚えていれば一瞬で解けます。