09 過去問演習ー1（全分野 横断）

正解：エ

10進数を2進数にするには「2で割った余り＝その桁の2進数、商＝次に処理する数」を繰り返します。下位桁（1の位）から順に出るので NISHIN(1) から入れます。

だから1回のループでは、先に「今の余り」を桁に格納 → 次に j を半分にの順にします。

• a ： NISHIN(k) ← j mod 2（いまの余りを k 桁目へ）
• b ： j ← j div 2（j を次の桁のために半分に）

順序を逆（先に j を割る）にすると、格納する余りが1つ先の桁のものになってしまう。「余りを取ってから割る」が鉄則。

正解：イ（7）

PUSHは7回・POPは3回で正味＋4個ですが、最終的に5個あるので開始時にすでに1個あったとわかります。命令を順に追うと、最後まで残るのは 1・4・5・10番目のPUSH の値です。

最終スタックを下から並べると ［開始時の1個, 1番目PUSH, 4番目, 5番目, 10番目］。図の下から2番目＝1番目のPUSHの値＝7。

▼速解法：POPは常に一番上を取る。命令を1つずつ紙で追い、「どのPUSHの値が生き残るか」を印つけると速い。

正解：ウ（5）

キューは先入れ先出し（FIFO）。ENQは末尾に入れ、DEQは先頭から出します。左が先頭として1行ずつ追います。

入れた順にそのまま出るので、次に出るのは 5（ウ）。

正解：ウ（a, f）

元の並びは A → K → T（次ポインタでたどる）。A と K の間に G を入れると A → G → K → T になります。

値が変わるのは、挿入点の前の要素の「次」と後ろの要素の「前」の2本だけ：

• a：A の次ポインタ（K=300 → G=400 に変更）
• f：K の前ポインタ（A=100 → G=400 に変更）

T の前後、K の次、A の前は変わりません。G 自身の x・y は問われている a〜f に含まれません。→ a, f（ウ）。

要素の移動は一切不要。ポインタを付け替えるだけ、が連結リストの強み。

正解：ウ（abc−d*+）

Proc は「左の子 → 右の子 → 自分」の順に記号を出力します。これは後行順（後順）の走査です。

根 + から後順でたどると：

• 左部分木＝葉 a → 「a」
• 右部分木＝* の下：（− の下で b, c を出し「−」）→ その後 d → 最後に * → 「b c − d *」
• 最後に根 +

つなげて a b c − d * +（ウ）。これは式 a + ((b − c) × d) の後置記法（逆ポーランド）そのものです。

正解：イ（4回）

手順(2)は「前の2つの数で割った余りを求める」ステップ。余りが0になるまで繰り返します。175 と 77 でトレース：

手順(2)は 4回実行（イ）。最後に割った 7 が最大公約数です。

正解：ウ

k は「今、何番目を見ているか」。X = A(k) で一致した瞬間にループを抜けます（前から順に探す＝線形探索）。

• 1番目とN番目の2か所にある場合 → 先に見つかる1番目で抜けるので k=1（ウ）。
• 見つからない場合 → 最後まで探して k は N+1 になる（ア・イは誤り）。

▼速解法：線形探索は前から順。複数一致なら最初の位置で止まる。

正解：エ（ヒープソート）

名前と説明がわざと入れ替えられています。キーワードで見抜きます：

正しく説明できているのは エ ヒープソートだけ。ア＝シェル、イ＝バブル、ウ＝クイックの説明が別の名前に付いています。