探索・整列
関数 find は、昇順に整列された整数型の配列 data から target を2分探索で探し、見つかればその要素番号を、見つからなければ -1 を返す。プログラム中の〔 a 〕に入れる正しい答えはどれか。ここで、配列の要素番号は1から始まる。
○整数型: find(整数型の配列: data, 整数型: target)
整数型: low ← 1
整数型: high ← dataの要素数
整数型: mid
while (low ≦ high)
mid ← (low + high) ÷ 2 の商
if (data[mid] = target)
return mid
elseif (data[mid] < target)
〔 a 〕
else
high ← mid - 1
endif
endwhile
return -1
- low ← mid
- high ← mid + 1
- low ← mid + 1
- low ← mid - 1
正解: c
data[mid] < target のときは、target は mid より右にしかないので、範囲の下端を mid + 1 にする。data = {2, 5, 8, 12, 16, 23, 38}、target = 23 では、mid が 4→6 と変わり、6を返す。 誤りの選択肢 a:low と high が隣り合うと mid が low のまま変わらず、探す値が data[high] にあるときや見つからないときに繰返しが終わらない。 b:target が data[mid] より大きいのに、探す範囲の上端を動かしている。範囲は右半分に移す必要がある。 d:探す範囲が左に広がり、すでに調べた data[mid] 以下の要素を何度も調べる。範囲が狭まらず、繰返しが終わらないことがある。
再帰
関数 power を power(2, 10) として呼び出したとき、power が呼び出される回数はどれか。ここで、最初の呼出しも1回と数える。
○整数型: power(整数型: x, 整数型: n)
整数型: h
if (n = 0)
return 1
endif
h ← power(x, n ÷ 2 の商)
if (n mod 2 = 0)
return h × h
endif
return h × h × x
- 5
- 10
- 4
- 11
正解: a
呼出しは power(2, 10)→power(2, 5)→power(2, 2)→power(2, 1)→power(2, 0) の順に行われ、n は10、5、2、1、0と半分(商)になるので5回である。戻り値は h × h(n が偶数)または h × h × x(n が奇数)で組み立てられ、power(2, 10) は1024を返す。n を1ずつ減らす方法より呼出し回数が少ない。 誤りの選択肢 b:x を1回掛けるごとに呼び出すと考えている。呼出しのたびに n は半分(商)になる。 c:n = 0 の呼出しを数えていない。n が0になる呼出しも1を返すために実行される。 d:n を1ずつ減らしながら0まで呼び出すと考えている。
文字列処理
手続 rle は、文字型の配列 s の中で同じ文字が続く部分ごとに、その文字と続く個数を出力するつもりで作った。rle({"x", "x", "y", "z", "z", "z"}) として呼び出したときの出力として正しいものはどれか。ここで、配列の要素番号は1から始まる。
○rle(文字型の配列: s)
整数型: i
整数型: cnt ← 1
for (i を 2 から sの要素数 まで 1 ずつ増やす)
if (s[i] = s[i - 1])
cnt ← cnt + 1
else
s[i - 1]を出力する
cntを出力する
cnt ← 1
endif
endfor
- “x”,2,“y”,1,“z”,3
- “x”,2,“y”,1
- “x”,1,“y”,0,“z”,2
- “x”,“y”,“z”
正解: b
出力は、s[i] が直前の文字と違うときに、直前のまとまりについて行われる。i = 3 で“x”と2、i = 4 で“y”と1を出力し、その後の“z”は最後まで続くので出力されない。cnt は 1→2→1→1→2→3 と変わる。最後のまとまりを出力するには、繰返しの後に s[sの要素数] と cnt を出力する処理が必要である。 誤りの選択肢 a:最後のまとまりも出力されると考えている。出力するのは次の文字が違うときだけなので、末尾の“z”の3個は出力されない。 c:cnt を数え直すときの初期値を0と考えている。新しいまとまりは、その1文字目で cnt ← 1 から始まる。 d:文字だけが出力されると考えている。文字の直後に cnt も出力する。
スタック・キュー
手続 schedule は、要素番号を番号とする処理の残り時間 t を受け取り、q 単位時間ずつ順番に処理を進めて、処理が終わった番号を順に出力する。q 単位時間で終わらない処理は、残り時間から q を引いて待ち行列の末尾に並び直す。クラス Queue はキューを表す。Queue() は空のキューを生成し、メソッド enqueue(x) は x を末尾に格納し、dequeue() は先頭の要素を取り出して返し、size() は格納されている要素の個数を返す。schedule({3, 1, 4}, 2) として呼び出したときの出力はどれか。ここで、配列の要素番号は1から始まる。
○schedule(整数型の配列: t, 整数型: q)
Queue: wait ← Queue()
整数型: i, p
for (i を 1 から tの要素数 まで 1 ずつ増やす)
wait.enqueue(i)
endfor
while (wait.size() > 0)
p ← wait.dequeue()
if (t[p] ≦ q)
pを出力する
else
t[p] ← t[p] - q
wait.enqueue(p)
endif
endwhile
- 1,2,3
- 2,1,3
- 3,2,1
- 2,3,1
正解: b
最初の待ち行列は1、2、3。1は残り3なので1になって末尾へ、2は残り1なのでここで終わる。3は残り4なので2になって末尾へ、1は残り1で終わり、最後に3が残り2で終わる。p は 1、2、3、1、3 の順に取り出され、出力は 2、1、3 となる。 誤りの選択肢 a:残り時間に関係なく、先に並んだ順に処理が終わると考えている。終わらない処理は末尾に並び直す。 c:キューではなくスタックとして、最後に格納した番号から取り出している。 d:要素番号の大きいほうから待ち行列に並べたと考えている。for は1から順に enqueue する。
リスト構造
クラス ListElement は単方向リストの要素を表し、メンバ変数 val(整数型)に要素の値を、next(ListElement 型)に次の要素の参照を格納する。次の要素がないとき next は未定義である。ListElement(v) は、val が v で next が未定義の要素を生成する。手続 insertAfter は、単方向リストの要素 p の直後に、値が v の新しい要素を挿入する。プログラム中の〔 a 〕と〔 b 〕に入れる正しい答えの組合せはどれか。
○insertAfter(ListElement: p, 整数型: v)
ListElement: e ← ListElement(v)
〔 a 〕
〔 b 〕
- a:p.next ← e b:e.next ← p.next
- a:e.next ← p b:p.next ← e
- a:e.next ← p.next b:p.next ← e
- a:p.next ← e.next b:e.next ← p
正解: c
先に新しい要素 e の next に元の p の次の要素の参照を入れ、その後で p.next を e に書き換える。順序を逆にすると、p の次の要素への参照が失われる。値が1、2、3のリストで insertAfter(listHead, 7) を呼び出すと、リストは1、7、2、3の順になる。 誤りの選択肢 a:先に p.next を e に書き換えるので、e.next ← p.next で e が自分自身を指し、元の p の次の要素への参照が失われる。 b:e の次を p にしているので、p と e が互いを指す循環ができ、元の p の次の要素への参照が失われる。 d:e.next はまだ未定義なので p.next が未定義になり、p より後ろの要素がリストから外れる。
木・グラフ
配列 t で表した2分探索木から値 x を探し、見つかればその要素番号を、見つからなければ0を返す。要素番号 k の節の左の子は 2 × k、右の子は 2 × k + 1 にあり、値が0の要素には節がない。左の子孫の値は節の値より小さく、右の子孫の値は大きい。プログラム中の〔 a 〕と〔 b 〕に入れる正しい答えの組合せはどれか。ここで、配列の要素番号は1から始まる。
大域: 整数型の配列: t ← {8, 3, 10, 1, 6, 0, 14}
○整数型: findPos(整数型: x)
整数型: k ← 1
while (k ≦ tの要素数)
if (t[k] = 0)
return 0
endif
if (t[k] = x)
return k
elseif (x < t[k])
〔 a 〕
else
〔 b 〕
endif
endwhile
return 0
- a:k ← 2 × k + 1 b:k ← 2 × k
- a:k ← 2 × k b:k ← 2 × k + 1
- a:k ← k + 1 b:k ← k + 2
- a:k ← 2 × k - 1 b:k ← 2 × k
正解: b
x が節の値より小さければ左の子 2 × k へ、大きければ右の子 2 × k + 1 へ進む。findPos(6) では k が 1→2→5 と進み、t[5] = 6 なので5を返す。 誤りの選択肢 a:左右を逆にしている。x が節の値より小さいときは、小さい値が入っている左の子へ進む。 c:配列の隣の要素へ進んでいるので、木の親子関係をたどれない。 d:左の子の要素番号を 2 × k - 1 としている。左の子は 2 × k、右の子は 2 × k + 1 である。
計算量
関数 pairs を pairs(n) として呼び出したとき、αの行が実行される回数を n で表したものはどれか。ここで、n は1以上とする。
○整数型: pairs(整数型: n)
整数型: i, j, cnt ← 0
for (i を 1 から n まで 1 ずつ増やす)
for (j を 1 から i - 1 まで 1 ずつ増やす)
cnt ← cnt + 1 /*** α ***/
endfor
endfor
return cnt
- n × (n + 1) ÷ 2
- n × n
- n × (n - 1) ÷ 2
- (n - 1) × (n - 1)
正解: c
i = 1 のとき内側は0回(終了値が開始値より小さいので実行しない)、i = 2 で1回、…、i = n で n - 1 回実行される。合計は 0 + 1 + … + (n - 1) = n × (n - 1) ÷ 2 である。n = 5 では10回になる。 誤りの選択肢 a:内側の繰返しが i 回実行されると考えている。j は i - 1 までなので i - 1 回である。 b:内側の繰返しが毎回 n 回実行されると考えている。内側の回数は i によって変わる。 d:外側の繰返しを n - 1 回、内側を毎回 n - 1 回と考えている。
オブジェクト指向
クラス Item は商品を表し、メンバ変数 price(単価、整数型)と qty(数量、整数型)をもつ。Item(p, q) は price が p、qty が q のインスタンスを生成する。次のプログラムは、数量が5以上の商品を1割引きにして合計金額を求める。出力される値はどれか。ここで、配列の要素番号は1から始まる。
Itemの配列: cart ← {Item(300, 2), Item(120, 5),
Item(800, 1)}
整数型: i, total ← 0
for (i を 1 から cartの要素数 まで 1 ずつ増やす)
if (cart[i].qty ≧ 5)
total ← total + (cart[i].price × cart[i].qty × 9 ÷ 10 の商)
else
total ← total + cart[i].price × cart[i].qty
endif
endfor
totalを出力する
- 2000
- 1220
- 1940
- 1800
正解: c
1番目は 300 × 2 = 600、2番目は数量が5なので 120 × 5 × 9 ÷ 10 の商 = 540、3番目は 800 × 1 = 800 である。total は 0→600→1140→1940 と変わり、1940が出力される。 誤りの選択肢 a:割引をしていない合計である。2番目の商品は数量が5なので、600円の1割引きで540円になる。 b:数量を掛けずに単価だけを足している。 d:数量に関係なく、すべての商品を1割引きにしている。
パスワード方針
A社は会員制のWebサイトを運営しており、会員のパスワードをデータベースに保存している。データベースの内容が万一漏えいしても、元のパスワードを最も割り出されにくい保存方法はどれか。
- すべての会員に共通の鍵でパスワードを暗号化して保存する。
- 会員ごとに異なるソルトを付け、パスワード用の遅いハッシュ関数で求めた値を保存する。
- ソルトを付けずに、計算の速い一般的なハッシュ関数で求めたハッシュ値をそのまま保存する。
- パスワードを Base64 で符号化した文字列を保存する。
正解: b
パスワードは元に戻せないハッシュ値で保存する。会員ごとに異なるソルトを付ければ同じパスワードでも値が変わり、事前に計算した表が使えない。計算に時間のかかるパスワード用のハッシュ関数を使えば、総当たりで試す速さも落とせる。 誤りの選択肢 a:鍵が漏えいすると、すべてのパスワードが復号されてしまう。 c:同じパスワードは同じハッシュ値になり、事前に計算した表や高速な総当たりで割り出されやすい。 d:符号化は暗号化ではなく、誰でも元の文字列に戻せる。
脆弱性管理
A社のWebサイトで使っているオープンソースのライブラリに、外部から任意のコードを実行される深刻な脆弱性が公表され、すでに悪用が確認されている。修正版も公開された。A社の情報システム部が最初に行うべきこととして、最も適切なものはどれか。
- 3か月後の定期保守まで待ち、そのときにまとめてライブラリを更新する。
- 自社のどのシステムが該当するバージョンを使っているかを調べ、修正版の適用か回避策を急いで計画する。
- 脆弱性の詳しい攻撃方法が分かるまで、対応を見送る。
- Webサイトへのアクセスログを削除して、攻撃の記録が外部に残らないようにする。
正解: b
脆弱性情報を受け取ったら、まず自社のシステムが影響を受けるかを、使っている製品とバージョンから確かめる。悪用が確認されている深刻な脆弱性なので、修正版の適用か、すぐに適用できない場合の回避策を優先して計画する。ログは、すでに攻撃を受けていないかの確認に使う。 誤りの選択肢 a:悪用が確認されている深刻な脆弱性を、3か月も残すことになる。 c:修正版が公開され悪用も確認されているので、詳しい情報を待つ理由はない。 d:ログは被害の有無を調べるために必要で、削除すると調査ができなくなる。