09 過去問演習ー6（総仕上げ・残り全部）

正解：ウ

逆ポーランド表記法（後置表記法）は、演算子を2つの数の「後ろ」に書くルールです。ふだん A+B と書くところを AB+ と書きます。カッコがいらないのが最大の利点で、コンピュータが式を計算するときに使われます。

読み解くコツはスタック（積み上げ式のメモ）を使うことです。手順はたった2つ。

• 英字（A〜G）が出てきたら → そのままスタックに積む
• 演算子（＋ − ÷）が出てきたら → スタックから上2つを取り出し、「（下にあった方）演算子（上にあった方）」の順につないで、結果を1つの塊としてまた積む

順番を間違えやすいので注意です。取り出した2つのうち、後から積んだ方（上）が演算子の右側にきます。AB− は A−B であって B−A ではありません。

トレース表

与えられた式 EF−G÷CD−AB+÷+ を左から1文字ずつ処理します。

最後にスタックに残った1つの塊が答えの式です。これは選択肢ウとぴったり一致します。

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

• ア：一番外側の演算子が「−」になっている式です。しかし与えられた式の最後の文字は「+」。後置表記では最後の演算子＝一番最後に実行される＝一番外側の演算なので、外側が「−」の時点で不一致です。
• イ：これも外側が「+」なので手順13までは望みがありますが、中身が違います。イを後置に直すと AB+CD−÷G+EF−÷ のようになり、先頭の並び EF− すら合いません。与えられた式は「E F −」で始まるので、最初に計算されるのは E−F のはずですが、イでは E−F は最後の方にしか出てきません。
• エ：外側の演算子が「÷」になっています。与えられた式の最後は「+」なので不一致です。エを後置に直すと最後が「÷」で終わります。

速解法

4択なら全部トレースしなくても、次の2段構えでほぼ一撃です。

1. 最後の1文字を見る：与式の末尾は「+」。＝一番外側の演算は足し算。→ 外側が「−」のアと、外側が「÷」のエが即消える。
2. 先頭の3文字を見る：与式は EF− で始まる。＝最初のかたまりは (E−F)。残ったイとウのうち、(E−F) を先に作っているのはウだけ（イは (E−F) が最後に足される位置にある）。

「末尾の演算子＝一番外側」は逆ポーランドの問題でくり返し使える強力な武器なので、必ず覚えておきましょう。

正解：エ

今度は「ふつうの式（中置表記）」と「逆ポーランド表記法（後置表記）」の組合せが正しいものを選ぶ問題です。4つの表を1つずつ照合します。

ふつうの式を後置に直す手順は、カッコの内側から順に、演算子をそのかたまりの後ろへ回すだけです。

選択肢ごとの検証

エが正しいことの確認（途中式）

計算式 a+(b*(c−d)) を内側から変換します。

1. 一番内側の (c−d) → cd−
2. 次に b*(c−d)。b と cd− のかけ算なので、2つを並べて後ろに * → b cd− * ＝ bcd−*
3. 最後に a+(…)。a と bcd−* の足し算なので、後ろに + → a bcd−* + ＝ abcd−*+

示された abcd−*+ と完全一致します。

念のため逆方向（後置 → ふつうの式）でも検算しておきます。abcd−*+ をスタックでたどると…

示された計算式と同じになりました。

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

• ア と イ は、答えが入れ替わっています。 アの後置表記 abc*+d− は、b*c を先に作ってから a を足し、最後に d を引く並びなので、実はイの計算式 (a+(b*c))−d のものです。逆にイの後置表記 ab+c*d− は、a+b を先に作ってから c をかけ、最後に d を引くのでアの計算式 ((a+b)*c)−d のものです。ペアが交換されているだけの、ひっかけ選択肢です。
• ウ：計算式は「たし算のかたまり」と「ひき算のかたまり」をかけるので、正しくは ab+cd−*（末尾が *）。ところが示された後置表記は abc*d−+ で末尾が + ＝ 一番外側がかけ算ではなく足し算。この時点で不一致です（abc*d−+ をたどると a+((b*c)−d) という別の式になります）。

速解法

4つ全部を変換すると時間がかかります。「末尾の演算子＝一番外側の演算」だけを見て高速にふるいにかけましょう。

ウはこれで一瞬で消えます。残るア・イ・エは、次に「先頭の3文字」を見るのがコツです。

• アの後置 abc*… は「最初に b*c を作る」意味 → でもアの計算式は最初に a+b を作るはず → ×
• イの後置 ab+… は「最初に a+b を作る」意味 → でもイの計算式は最初に b*c を作るはず → ×
• エの後置 abcd−… は「最初に c−d を作る」意味 → エの計算式も一番内側は (c−d) → ○

つまり「末尾＝一番外側」「先頭のかたまり＝一番内側（最初に計算する所）」の2点チェックで、変換作業をほとんどせずに答えが出せます。この2つはセットで覚えてください。

正解：イ

問われているのは「再帰呼出し（さいきよびだし）」という言葉の意味です。答えは単純で、ある関数が、その処理の中で自分自身を呼び出すこと。これがそのまま述べられているのが選択肢イです。

イメージで理解する

• 合わせ鏡のように、関数の中にまた同じ関数が現れる仕組みです。
• 例：階乗 fact(n) を「n × fact(n−1)」と定義し、n = 1 になったら 1 を返して止める、という書き方。
• ポイントは必ず止まる条件（終了条件）があること。これが無いと呼び出しが永久に続き、メモリを使い果たして異常終了します。

他の選択肢が何の説明なのか（用語のすり替えを見抜く）

速解法

• 「再帰」の「帰」＝自分のところへ帰ってくる、と結び付けて覚えると迷いません。選択肢の中に「自分自身」という言葉があれば、まずそれが本命です。
• 「再〜」で始まる紛らわしい用語（再帰的・再入可能・再使用可能・再配置可能）は、試験で選択肢に混ぜられる定番。再帰＝自分を呼ぶ／再入＝複数から同時に呼ばれても正しく動く／再使用＝終わった後もそのまま再び使えると、ひとことで区別できるようにしておきましょう。
• 関連知識：再帰と相性がよいのはスタックです。呼び出すたびに戻り先や変数がスタックへ積まれ、終了条件に達すると順に取り出されて戻っていきます。「再帰＝スタックを使う」も頻出の組み合わせです。

正解：ウ

この問題は「ビット列の中でいちばん右にある1だけを残して、あとは全部0にする」という有名なテクニックを、穴埋めで確認するものです。手順1で B = A - 1、手順2で C = A XOR B を作り、手順3で A と C を何かの演算にかけて答えを得ます。

まず「1を引く」と何が起こるか

2進数から1を引くと、右端から見ていって最初に現れる1が0に変わり、それより右にあった0はすべて1に変わります（そこより左は変化しません）。筆算の繰り下がりを思い出すとイメージしやすいです。

次に XOR をとる

XOR（排他的論理和）は「2つのビットが違えば1、同じなら0」です。A と B は左の部分が完全に同じで、右の部分（最も右の1とそれ以下）だけが全部反転しています。だから XOR をとると、変化した部分だけが1になります。

C は「最も右の1の位置から下が全部1、それより上は0」というマスク（型抜きの型紙）になりました。

最後の手順3で欲しいもの

求める答えは 00001000。A のうち「最も右の1」だけを残したいので、C という型紙で A を切り抜くイメージです。「両方が1のところだけ1」＝論理積（AND）を使います。

期待どおり 00001000 になりました。よって a に入るのは論理積（AND）＝ウです。

なぜ他の選択肢ではダメか

• ア（XOR）：00101000 XOR 00001111 = 00100111。これは B と同じ値で、1が複数残ってしまいます。
• イ（NAND）：AND の結果を反転するので 11110111。0だらけにしたいのに、逆に1だらけになります。
• エ（OR）：00101000 OR 00001111 = 00101111。1が増えるだけで、消したいビットが消えません。

速解法

• 選択肢が4つしかない論理演算の穴埋めなので、問題文の例（00101000 → 00001000）をそのまま4通り計算して合うものを選ぶのが最速です。手を動かせば30秒で決まります。
• 覚えておくと得な知識：「最も右の1だけを残す」は、2の補数を使えば A AND (-A) という1行で書けます。この問題の手順は、それと同じ結果を XOR とマスクで作っているだけです。
• マスクを使う演算の使い分けは頻出です。AND＝必要なビットだけ残す（他を0にする）／OR＝ビットを立てる／XOR＝ビットを反転する、とセットで暗記しておきましょう。

正解：ウ

左右2つの流れ図が、正の整数 M に対して同じ x を出すようにしたいという問題です。まず、それぞれが何を計算しているのかを読み取ります。

左の流れ図（ループ端を使った書き方）

x を1にしてから、n を「初期値 M、増分 −1、終値 1」で回して、毎回 x ← x × n をします。つまり n は M, M−1, …, 2, 1 と減っていき、x にはそれらが全部かけられます。結果は

x = M × (M−1) × … × 2 × 1、すなわち M の階乗（M!）です。かける順番は結果に影響しないので、要するに1からMまでの全部の掛け算だと思えばOKです。

右の流れ図（判断で終わりを決める書き方）

x を1、n を1にしてから、次の3つを繰り返します。

1. x ← x × n（今の n をかける）
2. n ← n + 1（n を1増やす）
3. 条件 a を判定し、Yes なら終了、No ならループの先頭に戻る

ここでの最大のポイントは、判定が「n を増やした後」に行われることです。「今かけ終わった数」と「今の n の値」が1ずれているので、そこを取り違えると答えが1つずれます。

トレース表で確かめる（M = 3 の場合、正解は 3! = 6）

表の右端を見ると、終わりたいのは n が 4 のときだけ、つまり n が M(=3) より大きくなった瞬間です。n が 2 や 3 のときは終わってはいけません。この「n = 4 のときだけ Yes、n = 2, 3 では No」をぴったり満たす条件が n > M ＝ウです。

なぜ他の選択肢が違うか（M = 3 で確認）

• ア（n < M）：1周目の後で n = 2 < 3 なので Yes となり、x = 1 のまま終了。答えが 6 になりません。そもそも「まだ続けたい」ときに終了する、意味が逆の条件です。
• イ（n > M−1）：n > 2、つまり n が 3 になった時点で Yes。2周目の後（x = 2、まだ3をかけていない）で止まってしまい、x = 2 = 2! となります。1つ手前で止まる典型的なひっかけです。
• エ（n > M+1）：n > 4、つまり n が 5 になるまで続きます。4周目で x = 6 × 4 = 24 まで進んでしまい、x = 4! になります。1回多く回るひっかけです。

ちなみに M = 1 でも確認できます。左は x = 1。右はウの条件なら、1周目で x = 1 × 1 = 1、n = 2 となり 2 > 1 で Yes → x = 1 で一致します。

速解法

• M に小さい具体値（2 か 3）を入れて実際に回すのが確実で速いです。文字のまま考えると必ず境界を間違えます。
• 「増やしてから判定」のループでは、判定時の n は、直前にかけた数より1大きいと覚えておく。最後にかけたい数が M なら、判定時の n は M+1 → 終了条件は「n が M を超えた」＝ n > M。
• 選択肢が境界違いで並んでいるとき（M−1, M, M+1）は、ほぼ確実に「1つずれ」を狙った出題です。最終周だけでなく、その1つ前の周でも No になるかを必ず確認しましょう。

正解：エ

①〜⑤の手続きを、まず日本語で読み解きます。

1. x に最初の値 a を入れる
2. y に f(x) の結果を入れる（今の x を関数に通す）
3. y を表示する
4. x に y を入れる（出てきた答えを、次の入力にする）
5. ②に戻る

つまりこれは、関数の出力をそのまま次の入力に入れ直すことを、②〜⑤で延々と繰り返す手続きです。電卓で「ある数にボタンを押す → 出た数にまた同じボタンを押す」を続けるのと同じイメージです。

値の流れを表で追う

x は「1つ前に表示された y」であり、y は「その x を f に通した値」です。この2つの関係だけを押さえれば十分です。

「y が変化しなくなった」を式にする

問題は、十分に繰り返した後で③に表示される y が変わらなくなった状態を考えています。y が変わらないということは、④で x ← y をしても x の値が前回と同じになり、その x から作られる次の y も同じ、という状態です。そこで、落ち着いた状態の値をあらためて y とすると、

• ④より、次の周で②に入る x は x = y（表示された値がそのまま入力になる）
• ②より、その x から y = f(x) が作られる

この2つの x を同じものとしてつなぐと、y = f(x) = f(y)。したがって f(y) = y ＝エが成り立ちます。

言い換えると、「f に通しても値が変わらない数」に行き着いた、ということです（このような値を不動点といいます）。もし f(y) が y と違う値なら、次の周で表示が変わってしまい「変化がなくなった」という前提に反します。

なぜ他の選択肢が違うか

• ア（f(a) = y）：f(a) は1周目に表示された値で、最初の1回きりの話です。収束した後の y と最初の値が一致する保証はありません（a がたまたま最初から不動点なら成り立ちますが、一般には成り立ちません）。
• イ（f(y) = 0）：この手続きのどこにも「0と比べる」「0になったら止める」という要素がありません。0はまったく無関係な数です。
• ウ（f(y) = a）：a は①で一度だけ使われる出発点で、②〜⑤のループには二度と登場しません。繰り返した後の値が、出発点に戻ってくる理由がありません。

速解法

• 「繰り返しても値が変わらなくなった」と来たら、反射的に f(y) = y（不動点）を疑う。この形の出題はほぼこれで決まります。
• ループの中で使われている変数は x と y だけ。a はループに入らないので、a を含む選択肢（ア・ウ）は「収束後の関係式」としては筋が悪い、と最初に切り捨てられます。
• 具体例で納得したい人は f(x) = (x + 2 ÷ x) ÷ 2（√2 を求める計算）で a = 1 から試すと、1 → 1.5 → 1.4166… → 1.41421… と落ち着き、その値は f に通しても変わりません。まさに f(y) = y の状態です。

正解：エ

「理想的なハッシュ法とはどういう検索のしくみか」を選ぶ、用語の意味を知っているかどうかの問題です。計算はいりません。

ハッシュ法とは何か（ここだけ覚えれば解ける）

ハッシュ法は、データそのものを計算式（ハッシュ関数）に通して数を出し、その数をしまう場所の住所（アドレス）として使う方法です。たとえば「学生番号を 100 で割った余りの番号のロッカーに入れる」と決めておけば、探すときも同じ計算をするだけで、そのロッカーを 1 回開ければ見つかります。

• 速い…先頭から 1 個ずつ見ていく（線形探索）必要がなく、計算 1 回で場所が分かる。データが何万件あっても、かかる時間はほぼ変わらない。
• スケーラビリティが高い…「データが増えても遅くなりにくい」という意味。ハッシュ法の最大の売りです。

選択肢 エ は「データを決まった計算で変換した値を、しまう場所の住所として使う、速くてデータが増えても強い検索方法」という内容で、上の説明とぴったり一致します。よって エ。

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

速解法

選択肢の中に「アドレス（格納アドレス）を求める・使う」という言葉があるかを真っ先に探してください。ハッシュ法の本質は「計算 → 住所」なので、この 2 語がそろっている選択肢がほぼ答えです。ア・イ・ウのように「同義語」「傾向・パターン」「オブジェクト」といった言葉が主役になっているものは、別の用語（シソーラス／データマイニング／オブジェクト指向）の説明だと判断して切り捨てられます。

正解：イ

まず用語の確認から。ハッシュ値とは、データ（ここでは3文字のキー）を決まった計算式にかけて出す「格納場所の番号」のことです。そして衝突（コリジョン）とは、別のキーなのにハッシュ値が同じになってしまうことを指します。つまりこの問題は、「SEP と同じ計算結果になるものを選べ」と言っているだけです。

計算式は「3文字それぞれのアルファベット順の番号（A=1, B=2, …, Z=26）を足し算し、その合計を 27 で割った余り」。それ以上でも以下でもありません。

まず基準となる SEP を計算する

• S = 19、E = 5、P = 16
• 合計 = 19 + 5 + 16 = 40
• 40 ÷ 27 = 1 余り 13 → SEP のハッシュ値は 13

選択肢を全部計算して比べる

SEP と同じ 13 になるのは FEB だけ。キーは違うのに置き場所が同じ 13 番になってしまう、まさに衝突です。よってイが正解。

なぜ他の選択肢が違うのか（どれも計算結果が 13 にならない、それだけです）

• ア APR：ハッシュ値 8。13 とは別の場所なので衝突しません。
• ウ JAN：ハッシュ値 25。合計が 27 未満なので割り算不要、そのまま 25。
• エ NOV：ハッシュ値 24。合計 51 は 27 を1回だけ引けるので 24。ここで「27 を2回引く」などと間違えないよう注意（51 − 54 はマイナスになるので引きすぎ）。

速解法

• 27 で割る前の「合計」だけで先に絞るのが速いです。合計が 40（SEP）と一致するか、40 と 27 差（＝13 または 67）になるものが答え。合計 13 の FEB が即座に該当します。
• アルファベットの番号は「A=1、E=5、J=10、O=15、T=20、Y=25」を覚えておくと、そこから数えて速く出せます（例：S は T=20 の1つ前で 19、P は O=15 の次で 16）。
• 余りの計算は割り算せず「27 を引けるだけ引く」でOK。合計が 27 未満ならそのまま答え。
• 試験でのコツ：問題文の表は全部使う必要はありません。選択肢に出てくる文字だけ拾えば十分です。

正解：ア

これも「ハッシュ法とはどんなアクセス方法か」を選ぶ用語問題です。前問（2020年 問18）とほぼ同じ知識で解けますが、選択肢がどれもファイルのアクセス方法で似ているぶん、区別する力が試されます。

考え方

ハッシュ法は「キー値（データを見分ける番号や名前）を関数（計算式）に入れて、しまってある場所の住所を計算で出す」方法です。ポイントは 2 つ。

• 関数（計算）を通すこと。
• その結果を格納アドレスとして使うこと。

選択肢 ア はまさに「関数を使ってキー値から格納アドレスを求めてアクセスする」という内容なので、そのまま正解です。よって ア。

なぜ他の選択肢が違うのか（似ている 3 つを見分ける）

特に ウ と エ は要注意です。ウは「表を引く」、エは「計算しない」。ハッシュ法は「表を引かずに、計算して住所を出す」——この一言で 3 つとも切れます。

速解法

1. 選択肢に「関数」という言葉があるか探す → ハッシュ法の説明には必ず入る。
2. その関数が「キー値 → 格納アドレス」の向きになっているか確認する。
3. 「次のレコードの住所」＝リスト、「対応表」＝索引、「キー値をそのまま」＝直接アクセス、と正体を言い当てて消す。

ハッシュ法・リスト・索引・直接アクセスの 4 点セットはこの形で繰り返し出題されるので、上の表ごと覚えてしまうのが最短です。