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

正解：ア

やりたいのは「Xの文字列の後ろにYの文字列をつなげて、Zに入れる」こと。流れ図は前半ループ（ループ1）でXをコピー、後半ループ（ループ2）でYをコピーします。1文字ずつ配列に入れる点に注意します。

a（ループ1、k を 1 から m まで）＝Xをそのまま前へ

• Xの1文字目をZの1番目、2文字目をZの2番目…と入れるので Z(k) ← X(k)。

b（ループ2、k を 1 から n まで）＝Yを「Xの後ろ」へ

• Xはすでに Z の 1〜m 番目を使い切っています。だから Y の 1文字目は Z の m+1 番目から入れます。
• k 番目の Y の文字は Z の m+k 番目へ。つまり Z(m+k) ← Y(k)。

この組合せがア（a: Z(k)←X(k) ／ b: Z(m+k)←Y(k)）です。

なぜ他が違う？

• イ…b が Z(n+k)。ずらす量は「先に置いたXの長さ m」なのに、Yの長さ n でずらしていて場所がおかしい。
• ウ・エ…a で先に Y を入れている（Z(k)←Y(k)）。問題は「Xが前・Yが後ろ」なので順番が逆。

速解法：連結は「先に入れた列の長さ分だけ、後ろの列をずらす」。前が長さ m なので後ろは m+k、と押さえればアだけが残ります。

正解：イ

後置記法（逆ポーランド）は「計算する順に、2つの値のうしろに演算子を書く」ルールです。Y=(A+B)×(C−D÷E) をカッコと優先順位（÷×が先、＋−が後）に沿って、内側から部品ごとに変換します。

最後に Y= を後置にすると、例と同じく「値のうしろに = 」で YAB+CDE÷−×=。これはイです。

なぜ他が違う？

• ア（YAB+C−DE÷×=）…C−D÷E を「C−D」を先にした形。÷は−より先なので DE÷ を作ってから引く順が正しい。
• ウ（…EDC÷−…）…D÷E なのに E と D が逆で EDC÷ になっている。割られる数・割る数の順序が違う。
• エ（YBA+…CD−E÷…）…先頭が BA+（A＋Bの順が逆）で、右カッコも CD−E÷（引き算と割り算の順序が違う）。

速解法：「一番内側で最初に計算する部分（ここは D÷E）」を正しく DE÷ と書けるかで、多くの誤答をふるい落とせます。

正解：エ

「自分自身を呼び出せるプログラム」は再帰的（下線a、正しい）。再帰では、呼び出すたびに局所変数・仮引数・戻り番地をスタック（下線b、正しい）に積み、戻るときに取り出して元の状態に復元します。スタックは「あと入れ先出し＝LIFO」なので、最後に呼び出したものから順に戻します。ところが下線dは「FIFO（先入れ先出し）」となっており、ここが誤り。正しくはLIFO（Last In First Out）。よって「誤りの箇所 d／正しい字句 LIFO」の組合せ、エが正解。

なぜ他が違う？

• ア…a「再帰的」は正しい用語なので、これを直す必要はない（「再入可能」は別概念で、複数から同時に呼ばれても正しく動く性質のこと）。
• イ…b「スタック」は正しい。再帰の情報を積むのは待ち行列（キュー）ではなくスタック。
• ウ…c「仮引数」は正しい。呼び出しで保存するのは仮引数（と局所変数・戻り番地）で、「実引数」に直す必要はない。

速解法：再帰＝スタック＝LIFOの三点セット。「FIFO」と書いてあれば即そこが誤り、と反応できれば d を選べます。

正解：イ

キュー（queue）は日本語で「待ち行列」です。お店のレジに並ぶ行列と同じで、先に並んだ人が先に会計を済ませて出ていくという仕組みです。これを「先入れ先出し（FIFO：First In, First Out）」と呼びます。よって「最初に格納されたデータが最初に取り出される」と説明しているイが正解です。

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

• ア「最後に格納されたデータが最初に取り出される」＝後入れ先出し（LIFO）で、これはスタックの説明です。
• ウ「添字を用いて特定のデータを参照する」＝好きな位置に番号で直接アクセスできるのは配列の特徴です。
• エ「二つ以上のポインタを用いてデータの階層関係を表現する」＝親子で枝分かれする木構造の説明です。

速解法：「行列＝FIFO＝キュー」「山積み＝LIFO＝スタック」の2セットだけ覚えれば、この手の用語問題は即答できます。

正解：イ

2分探索木（にぶんたんさくぎ）のルールはただ1つです。

• ある節から見て、左側にぶら下がる値はすべてその節より小さい
• 右側にぶら下がる値はすべてその節より大きい

大事なのは「すぐ下の子だけ」ではなく「その下にある全員」がこのルールを守らないといけない点です。ここが引っかけポイントになります。

各選択肢のチェック

正解イを1つずつ確認

1. 根 17 の左側にあるのは 14・10・16 → すべて 17 より小さい。○
2. 根 17 の右側にあるのは 19・18 → すべて 17 より大きい。○
3. 節 14：左の子 10 は 14 より小さい ○／右の子 16 は 14 より大きい ○
4. 節 19：左の子 18 は 19 より小さい ○（しかも 17 より大きいので、根から見た「右は全部17超」も守れている）

すべて満たすので、イが2分探索木です。

間違えやすいポイント（イの16と18に注目）

イの 16 は「根 17 の左」にありながら「節 14 の右」にあります。14 < 16 < 17 なので両方の条件を同時に満たしていて、これは正しい形です。同じく 18 は「根 17 の右（17より大）」かつ「19 の左（19より小）」で 17 < 18 < 19。この「はさまれた値」が正しく置けているかどうかが2分探索木の腕の見せどころです。エの 15・16 は、根 20 の右に置かれてしまったせいでこの「はさみ」に失敗しています。

速解法

• その1：中順（左→根→右）でなぞって、小さい順に並ぶかを見る。これが2分探索木の一番速い判定法です。イをなぞると 10 → 14 → 16 → 17 → 18 → 19 ときれいな昇順。アは 10 → 15 → 14 … で早々に順番が崩れ、ウは 15 → 16 → 14 …、エは 10 → 18 → 14 … で崩れます。昇順になっていないものは即アウトと切り捨てられます。
• その2：まず「兄弟の大小」だけ見る。親より左の子が小さく、右の子が大きいか。この時点でア（15の下の10と14）とウ（16の下の15と14）は落ちます。
• その3：残ったものだけ「根から見た全体」を確認。エは根 20 の右側に 20 未満の値が並んでいるので脱落。残ったイが正解、と3ステップで詰められます。

正解：イ

隣接行列は「i行j列が1ならノードiとjが線で結ばれている」ことを表します。無向グラフなので行列は対角線をはさんで左右対称です。ノード5個が「木」になる条件は、(1)全部がひとつながり（連結）で、(2)輪（サイクル）が無いこと。これは「辺の数がちょうど ノード数−1＝4本」と同じ意味です。1の個数は辺の2倍なので、木なら1が8個になります。各選択肢の辺を数えます。

イは辺が4本で、1が2と5に、2が3と4につながっており、5個のノードが輪を作らずひとつながりになっています。まさに木の形。よって正解はイ。

速解法：まず行列中の1の個数を数え、8個（＝辺4本）でない選択肢を切ります。ア・ウ・エは1が10個以上あり辺が多すぎるのですぐ除外でき、残ったイが木だと確認できます。

正解：ウ

「階乗」とは、その数から1までを全部かけ算した値のことです。たとえば 3! = 3×2×1 = 6 です。この問題は、その計算を「自分自身を呼び出す関数（再帰）」で書くときの穴埋めです。

階乗にはうまい性質があります。3! = 3 × (2×1) = 3 × 2! のように、「n の階乗 ＝ n × (n−1 の階乗)」と書けるのです。つまり F(n) = n × F(n−1) となります。これがそのまま選択肢ウです。

実際に F(3) を計算して確かめましょう。

下から順にかけ戻すと F(1)=1×1=1、F(2)=2×1=2、F(3)=3×2=6。ちゃんと 3!=6 になりました。

なぜ他が違うのか：

• ア n + F(n−1) は「かけ算」ではなく「足し算」になっているので、階乗になりません（これだと 3+2+1+… の合計になってしまう）。
• イ n−1 + F(n) は自分自身 F(n) をそのまま呼んでいるため、n が小さくならず永遠に止まりません（無限ループ）。
• エ (n−1) × F(n) も F(n) を呼び続けるので止まりません。再帰は「呼ぶたびに n を1ずつ減らして、いつか n=0 の出口にたどり着く」形でなければいけません。

速解法：再帰の穴埋めは「①n が1つ小さい F(n−1) を呼んでいるか」「②それと n を正しく組み合わせているか」の2点で見抜けます。階乗なら「n × F(n−1)」の形（かけ算）が正解の型です。

正解：ウ

ユークリッドの互除法は、大きい数 mod 小さい数（割った余り）を繰り返し、余りが0になったときの割る数が最大公約数になる方法です。流れ図が2つあり、それぞれ計算後にどの変数（m か n）に答えが入っているかを問われています。

実際に a=12, b=8（最大公約数は4）で両方をトレースしてみます。

方法1のトレース：先に r←m mod n を1回してからループに入ります。ループはr=0で終わります。

終了時、答え4は n に入っています（→ 方法1は n）。

方法2のトレース：ループの中で r←m mod n → m←n → n←r の順に動き、r=0で終わります。

終了時、答え4は m に入っています（→ 方法2は m）。よって「方法1＝n、方法2＝m」のウが正解です。

速解法：互除法は「更新の途中で n に余りを入れ、m に古い n を送る」動きをします。ループを抜けた瞬間、直前に0になった r をどこへ入れたかを見れば答えの位置が分かります。方法1はループを抜けたときn＝直前のnが残る形、方法2はmに答えが残る形になっている、と1回のトレースで確かめるのが確実です。

正解：ア

これは2分法（区間を半分ずつ狭めて解を追い込む方法）です。最初の区間は0から1まで（幅1）。手順(2)で区間の真ん中 x を計算し、手順(3)で「区間の右端 x1 と真ん中 x の差」が0.001より小さくなったら終わり。手順(4)で区間を左半分か右半分に更新し、また(2)へ戻ります。

ポイントは、真ん中xと右端x1の差＝区間の幅のちょうど半分だということ。区間の幅は1回ごとに半分になるので、(3)でチェックされる値は 0.5 → 0.25 → 0.125 … と半分ずつ小さくなります。何回目で0.001を下回るかを数えます。

10回目でようやく0.001を下回るので、(2)は10回実行され、答えはアです。

速解法：「幅1を半分にしていって0.001より小さくするには何回か」を考えると、2の10乗＝1024なので (1/2)の10乗 ≒ 0.000977 で初めて0.001を切ります。だから約10回、とすぐ見当がつきます。イ・ウ・エ（20・100・1000）は桁が大きすぎで、半分ずつ縮む2分法の速さ（十数回で十分細かくなる）とかけ離れています。

正解：ウ

2分探索は「まん中を見て、探す値より大きいか小さいかで左半分・右半分に絞る」を繰り返す方法です。これができるにはデータが小さい順（または大きい順）にきちんと並んでいることが絶対条件です。並んでいないと「まん中より右か左か」の判断ができません。

顧客番号をキーに2分探索したいので、顧客番号の昇順（小さい順）に並べて置いたデータ構造が適しています。これが選択肢ウです。

簡単な例で確認します。番号が [10, 20, 30, 40, 50] と昇順に並んでいて「30」を探すとき、まん中の30を見て一発で見つかります。「40」を探すなら、まん中30より大きいので右半分 [40,50] だけを見ればよく、半分ずつ候補を減らせます。

なぜ他が違うのか：

• ア ハッシュ値の位置に置く構造はハッシュ探索のための並べ方で、番号順にはなっていません。2分探索には向きません（ハッシュ探索なら1回で当てにいく別方式）。
• イ ランダム配置は並び順がバラバラなので、まん中を見ても左右どちらに絞ればよいか判断できず、2分探索が成立しません。
• エ 「セルのアドレス順」に置いてあっても、それが顧客番号の大小と一致していなければ意味がありません。番号の昇順に並んでいる保証がないので誤りです。

速解法：2分探索と聞いたら反射的に「整列（ソート）済みが前提」。選択肢の中で「番号順に並んでいる」と言っているものを選べば正解です。

正解：イ

ハッシュ法は「データそのものからハッシュ関数で場所（位置番号）を計算し、その場所にしまう」方法です。この問題のハッシュ関数は「5つの桁の数字を全部足して、13で割った余り」です。

格納したい数は 54321。各桁は 5, 4, 3, 2, 1 なので、まず足します。

• 5 + 4 + 3 + 2 + 1 = 15

次に、この15を13で割った余りを求めます。

• 15 ÷ 13 = 1 あまり 2 → 余りは 2

よって位置は 2。選択肢イが正解です。配列は位置0〜12（13個）用意されており、余りは必ず0〜12に収まるので、この範囲にきちんと入ります。

なぜ他が違うのか：桁の合計を取り違えたり、割る数を間違えると別の答えになります。

• ア（1）・ウ（7）・エ（11） は、合計15や「13で割る」を正しく計算すれば出てきません。たとえば合計を14や15以外にすると余りがずれます。落ち着いて 15 mod 13 = 2 を出しましょう。

速解法：ハッシュ法の位置計算は「①関数どおりに値を作る（ここでは桁の合計＝15）→ ②割り算の余りを取る（15÷13の余り＝2）」の2ステップだけ。余りは必ず0〜(割る数−1)の範囲に入ることも覚えておくと検算になります。

正解：イ

※ラベルは「スタック」となっていますが、画像の実際の内容はハッシュ表（ハッシュ関数と衝突）の問題です。以下は画像の内容に沿って解説します。

まず言葉の確認です。ハッシュ表は「データをしまう棚」で、棚には 0 番から n-1 番までの引き出しがあります（n が棚の大きさ）。キー x をどの引き出しに入れるかは、ハッシュ関数 h(x) = x mod n（x を n で割った余り）で決めます。

「衝突」とは、違うキーなのに同じ引き出しに行ってしまうことです。つまり、2つのキー a と b が衝突する条件は、式で書くと次のひとことに尽きます。

• h(a) = h(b)　すなわち　a mod n = b mod n（n で割った余りが等しい）

余りが等しい ⇔ 差が n の倍数

「余りが同じ」を、選択肢にあるような形に言いかえます。割り算を式にすると、商を p, q、共通の余りを r として

• a = n × p + r
• b = n × q + r

この2つを引き算すると、余り r どうしが打ち消し合って

• a - b = n × p - n × q = n × (p - q)

となり、a - b は n の倍数です。逆に a - b が n の倍数なら余りは必ず一致します。よって「衝突する ⇔ a-b が n の倍数」。これが選択肢イです。

具体例で確かめる（n = 10 の場合）

1行目は衝突していて a-b が 10 の倍数、2行目は衝突していないのに a+b のほうが 10 の倍数になっています。「差」で見ると当たり、「和」で見ると外れることが数字でも分かります。

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

• ア（a+b が n の倍数）…上の表の2行目が反例。23 と 27 は和が 50 で 10 の倍数ですが、引き出しは3番と7番で別々＝衝突していません。和が n の倍数になるのは「余りどうしを足すと n になる」ケース（3と7など）で、衝突（余りが同じ）とは別の話です。
• ウ（n が a+b の倍数）…「倍数」の向きが逆です。これは棚の大きさ n のほうがキーの和で割り切れる、という意味になり、たとえば a=1, b=1, n=10 でも成り立ちません。そもそも n はキーの値と無関係に決めた棚の大きさで、キーの和がそれを割り切るかどうかは衝突と何の関係もありません。
• エ（n が a-b の倍数）…これも向きが逆です。正しいのは「a-b が n で割り切れる」で、エは「n が a-b で割り切れる」。たとえば n=10、a=13, b=3 は衝突しますが（どちらも余り3）、a-b=10 に対して「10 が 10 の倍数」はたまたま成立するだけで、a=23, b=3（a-b=20）にすると「10 が 20 の倍数」は成り立ちません。衝突しているのに条件が崩れるので誤りです。

速解法

• 合言葉は「ハッシュの衝突＝余りが同じ＝差が n の倍数」。これだけ覚えていれば即答できます。
• 「A が B の倍数」は「A ÷ B が割り切れる」＝大きくなれる側が A。倍数の向きに迷ったら、a-b と n のどちらが割られる側かを考えます（割られるのはキーの差のほう）。
• 選択肢に「和」と「差」が並んでいたら、差が正解と反射的に判断してよい形の問題です。心配なら n=10 で 13 と 3 のような数を当てはめて1秒で検算しましょう。

正解：ウ

バブルソートは、いちばん基本的な整列法です。やることは1つだけ「隣どうしを比べて、順番が逆なら入れ替える」。これを何度も繰り返すと、大きい値が泡（バブル）のように端へ移動していって、最後には全体が並びます。ウがそのままこの説明になっています。

例：[3, 1, 2] を小さい順に並べるとき、まず3と1を比べて逆なので入れ替え [1, 3, 2]、次に3と2を比べて逆なので入れ替え [1, 2, 3]。隣を比べて入れ替えるだけで並びました。

ほかの選択肢は、別の整列法の説明になっています。名前を覚えるより「どんな動きか」で見分けるのがコツです。

速解法：「隣り合う」「入れ替える」という言葉が出たらバブルソート。逆に「間隔」＝シェル、「基準値で振り分け」＝クイック、「木（ヒープ）」＝ヒープ、と単語で即判定できます。