重要度：B 論点：アルゴリズムとプログラミング
問21：空のスタックに対して、A、Bの順にデータを格納した後に1個取り出し、続いてCを格納してから2個取り出した。データが取り出された順序はどれか。
- A：B、C、A
- B：A、B、C
- C：C、B、A
- D：B、A、C
【第21問：正解と解説】
正解：A
・A
正解。スタックは後入れ先出しであり、最初の取り出しでは後から入れたB、次の取り出しでは直前に入れたC、最後にAが取り出される。
・B
A、B、Cの順に取り出されるのは、先入れ先出しのキューを使った場合である。
・C
C、B、Aは、3個を続けて格納してからまとめて取り出した場合の順序である。
・D
B、A、Cの順にはならない。2回目の取り出しの時点で最も上にあるのはCである。
重要度：B 論点：アルゴリズムとプログラミング
問22：先に格納したデータから順に取り出される、先入れ先出しのデータ構造はどれか。
- A：スタック
- B：2分木
- C：ハッシュ表
- D：キュー
【第22問：正解と解説】
正解：D
・A
スタックは後から格納したデータから取り出される、後入れ先出しのデータ構造である。
・B
2分木は要素を階層的に格納する構造であり、取り出し順序を定めるものではない。
・C
ハッシュ表はキーから計算した位置にデータを格納する構造であり、格納順に取り出す構造ではない。
・D
正解。キューは先に格納したデータから順に取り出される構造であり、印刷待ちの管理や処理の順番待ちなどに使われる。
重要度：A 論点：アルゴリズムとプログラミング
問23：キーの値の順に整列された1,000件のデータから、2分探索法で目的のデータを探すときの最大比較回数はおよそ何回か。
- A：10
- B：32
- C：500
- D：1000
【第23問：正解と解説】
正解：A
・A
正解。2分探索は1回の比較で探索範囲が半分になるため、最大比較回数は2を底とする1,000の対数でおよそ10回である。
・B
32は1,000の平方根に近い値であり、2分探索の比較回数の見積りとしては誤りである。
・C
500は線形探索を行った場合の平均比較回数に相当する値である。
・D
1000は線形探索を行った場合の最悪の比較回数である。
重要度：B 論点：アルゴリズムとプログラミング
問24：2分探索法を適用するために、探索対象のデータが満たしていなければならない条件はどれか。
- A：データの件数が2のべき乗になっていること
- B：データがキーの値の順に整列されていること
- C：全てのデータが連結リストに格納されていること
- D：データの中に同じキーの値が存在しないこと
【第24問：正解と解説】
正解：B
・A
件数が2のべき乗である必要はなく、任意の件数に適用できる。
・B
正解。2分探索は中央の値との大小比較によって探索範囲を半分に絞り込む方法であるため、データがキーの値の順に整列されていることが前提となる。
・C
連結リストでは中央の要素へ直接アクセスできないため、2分探索にはむしろ不向きである。
・D
同じキーの値が存在しても探索自体は行える。整列されていることが必須の条件である。
重要度：B 論点：アルゴリズムとプログラミング
問25：配列［5，2，4，1］に対して、左端から隣り合う二つの要素を比較し、左の値が右の値より大きければ交換する操作を右端まで1回だけ行った。操作後の配列はどれか。
- A：［1，2，4，5］
- B：［2，4，1，5］
- C：［2，5，1，4］
- D：［5，2，1，4］
【第25問：正解と解説】
正解：B
・A
［1，2，4，5］は全体を最後まで整列した結果であり、左から右への走査を1回だけ行った結果ではない。
・B
正解。最初に5と2を比較して［2，5，4，1］、次に5と4を比較して［2，4，5，1］、最後に5と1を比較して［2，4，1，5］となる。
・C
［2，5，1，4］は、隣接要素の比較と交換を右端まで順番に続けていない。
・D
［5，2，1，4］は、最初の5と2の逆順を解消していない。
コメント