問1：整列済みの配列に対する二分探索（バイナリサーチ）で、要素数1,000個の中から目的の要素を探すときの最大比較回数として、最も適切なものはどれか。
【資料】データ数：1,000件（昇順に整列済み）／探索方式：二分探索。log2(1000)≒9.97である。参考として線形探索なら最大1,000回だが、本問は二分探索を問う。
- A：10回
- B：9回
- C：11回
- D：1,000回
【第1問：正解と解説】
正解：A
・A
【論点】二分探索は探索範囲を毎回半分に絞り込むため、最大比較回数はデータ数nに対しlog2 nの切り上げ（＝floor(log2 n)+1）程度となる。線形探索のnとの違いを区別する。【考え方】毎回範囲が半減するので、必要な比較回数は2を底とする対数のオーダーになる。対数値を切り捨てるか切り上げるかで1回分ずれる点、線形探索の回数と混同しない点に注意する。【選択肢解説】log2(1000)≒9.97を切り上げた10回が最大比較回数であり正しい。
・B
【選択肢解説】対数値を切り捨てて9回とした誤りで、範囲が1個になるまでの最終比較を数え落としている。
・C
【選択肢解説】比較回数を1回過大に見積もった誤りである。
・D
【選択肢解説】線形探索の最大回数1,000回であり、二分探索の回数ではないため誤り。
関連過去問：探索アルゴリズム（H25類似）
問2：データ数n＝8のとき、計算量がO(n^2)のアルゴリズムとO(n・log2 n)のアルゴリズムの演算回数の組み合わせとして、最も適切なものはどれか。
【資料】n＝8とする。log2 8＝3である。オーダーの係数は1として単純に見積もる。参考としてO(n)なら8回だが本問では用いない。
- A：O(n^2)：16回、O(n・log2 n)：8回
- B：O(n^2)：64回、O(n・log2 n)：8回
- C：O(n^2)：16回、O(n・log2 n)：24回
- D：O(n^2)：64回、O(n・log2 n)：24回
【第2問：正解と解説】
正解：D
・A
【論点】計算量オーダーに具体的なnを代入して演算回数の概算を比較する。n^2はnの2乗、n・log2 nはnにlog2 nを掛けた値になる。指数と対数の扱いを取り違えないことが要点となる。【考え方】n^2はnを2乗した値、n・log2 nはnとlog2 nの積で求める。log2 nの値の取り違えや、2乗すべきところを別の演算にすると値がずれる。【選択肢解説】n^2を16、n・log2 nを8と誤った組で、2乗計算と対数の掛け算を共に誤っている。
・B
【選択肢解説】n^2は正しいがn・log2 nを8とした誤りで、log2 8＝3の掛け算を落としている。
・C
【選択肢解説】n^2を16とした誤りで、8の2乗を誤っている。
・D
【選択肢解説】O(n^2)＝64回、O(n・log2 n)＝8×3＝24回となり正しい。
関連過去問：計算量（H27類似）
問3：スタック（LIFO）に対する一連の操作を行ったとき、最後に取り出される（popされる）値として、最も適切なものはどれか。
【資料】空のスタックに対し、push(1)、push(2)、push(3)、push(4)、pop、pop、push(5)、pop の順に操作する。スタックは後入れ先出しである。参考としてキュー（先入れ先出し）なら結果は異なるが、本問はスタックである。
- A：4
- B：5
- C：2
- D：1
【第3問：正解と解説】
正解：B
・A
【論点】スタックは後入れ先出し（LIFO）であり、最後にpushした要素が最初にpopされる。操作を順にたどり、キュー（FIFO）と取り違えないことが要点となる。【考え方】各操作でスタックの状態を順に更新して追う。popは最後に積んだ要素を取り出すため、途中のpushで積み直された要素が次のpop対象になる。先入れ先出しの動作と混同しない。【選択肢解説】2回目のpopで取り出される値であり、最後のpop結果ではないため誤り。
・B
【選択肢解説】push5の後にpopするため最後に取り出されるのは5であり正しい。
・C
【選択肢解説】キュー（FIFO）と取り違えた場合に出る値であり、スタックの結果ではないため誤り。
・D
【選択肢解説】最初にpushした値であり、LIFOでは最後まで残るため誤り。
関連過去問：スタックとキュー（H24類似）
問4：ハッシュ法（除算法）でデータを格納するとき、キー値125の格納先スロット番号として、最も適切なものはどれか。
【資料】ハッシュ表のサイズは13、ハッシュ関数は「キー値 mod 表サイズ」とする。スロット番号は0から始まる。参考として表サイズを10とすると別の値になるが、本問の表サイズは13である。
- A：5
- B：3
- C：8
- D：12
【第4問：正解と解説】
正解：C
・A
【論点】除算法のハッシュ関数は「キー値を表サイズで割った剰余」でスロット番号を求める。表サイズの取り違えや、剰余と商の混同に注意する。【考え方】格納先は、キー値を表サイズで割った余りで決まる。表サイズを誤ると別の値になるため、資料に示された正しい表サイズを用いることが要点となる。【選択肢解説】表サイズを別の値として計算した誤りで、13で割った剰余になっていない。
・B
【選択肢解説】剰余計算を誤った値であり、125÷13の余りと一致しない。
・C
【選択肢解説】125÷13の余りは8であり、スロット番号8となり正しい。
・D
【選択肢解説】商や別の演算と取り違えた誤りである。
関連過去問：ハッシュ法（H28類似）
問5：根を高さ0とする完全二分木で、高さ4までノードが完全に埋まっているときの最大ノード数として、最も適切なものはどれか。
【資料】根の高さを0とし、高さ4まで各レベルがノードで完全に埋まっているものとする。各レベルkのノード数は2^kである。参考として葉（高さ4）だけのノード数は別に数えるが、本問は全体のノード数を問う。
- A：16
- B：15
- C：32
- D：31
【第5問：正解と解説】
正解：D
・A
【論点】完全二分木では各レベルkのノード数が2^kとなり、高さhまでの総ノード数は2^(h+1)−1で求められる。最下段だけのノード数や、全体から1を引き忘れる誤りに注意する。【考え方】各レベルのノード数を合計するか、等比数列の和の公式を用いる。最下段の葉の数だけを答えたり、総和の式で1を引き忘れたりしないことが要点となる。【選択肢解説】最下段（高さ4）のノード数2^4＝16であり、全体のノード数ではないため誤り。
・B
【選択肢解説】総和から1を引き過ぎた、あるいは最下段−1とした誤りである。
・C
【選択肢解説】総和の式を2^(h+1)としつつ1を引き忘れに近い過大な値である。
・D
【選択肢解説】2^0＋2^1＋…＋2^4＝2^5−1＝31となり正しい。
関連過去問：木構造（H26類似）
コメント