データ構造とアルゴリズム（科目B）

次のプログラムは、配列2本で表した単方向リストの要素数を数えて返す。プログラム中の【a】に入れる式はどれか。ここで、次[p] が 0 のときノード p がリストの終わりであることを表す。

整数型の配列: 値 ← {30, 10, 20}整数型の配列: 次 ← {0, 3, 1}整数型: 先頭 ← 2 ○整数型: 個数()  整数型: cnt ← 0  整数型: p ← 先頭  while (p ≠ 0)    cnt ← cnt + 1    p ← 【a】  endwhile  return cnt

1. 次[p]
2. p + 1
3. 値[p]
4. 次[cnt]

次の関数 f は何をするものか。ここで、値[p] はノード p の値、次[p] は p の次のノードの添字で、次[p] が 0 のときリストの終わりを表す。リストは空でないものとする。

○整数型: f(整数型の配列: 値, 整数型の配列: 次, 整数型: 先頭)  整数型: p ← 先頭  整数型: m ← 値[先頭]  while (次[p] ≠ 0)    p ← 次[p]    if (値[p] > m)      m ← 値[p]    endif  endwhile  return m

1. リストの末尾のノードの値を返す
2. リストに格納されている値の最大値を返す
3. リストに格納されている値の合計を返す
4. リストの要素数を返す

次のプログラムは、値が w の未使用ノード q を、添字 p のノードの直後につないでリストに加える。プログラム中の【a】に入れるものはどれか。ここで、次[p] が 0 のときリストの終わりを表す。

整数型の配列: 値 ← {10, 20, 30, 0}整数型の配列: 次 ← {2, 0, 0, 0}整数型: 先頭 ← 1 ○挿入(整数型: p, 整数型: q, 整数型: w)  /* 値が w のノード q を、ノード p の直後につなぐ */  値[q] ← w  【a】  次[p] ← q ○主処理()  挿入(1, 3, 15)  /* このあとリストは 10 → 15 → 20 の順になる */

1. 次[q] ← 0
2. 次[p] ← 次[q]
3. 次[q] ← 次[p]
4. 次[q] ← p

次の関数 削除(1) を実行した後の配列 次 の内容はどれか。ここで、次[p] が 0 のときリストの終わりを表す。

整数型の配列: 次 ← {3, 0, 4, 2} ○整数型の配列: 削除(整数型: p)  /* 添字 p のノードの直後のノードをリストから外す */  整数型: q  q ← 次[p]  if (q ≠ 0)    次[p] ← 次[q]    次[q] ← 0  endif  return 次

1. {3, 0, 0, 2}
2. {4, 0, 0, 2}
3. {4, 0, 4, 2}
4. {2, 0, 0, 4}

次のプログラムで、主処理 の戻り値はどれか。ここで、次[p] が 0 のときリストの終わりを表す。

○整数型: 探す(整数型の配列: 値, 整数型の配列: 次, 整数型: 先頭, 整数型: k)  整数型: p ← 先頭  整数型: c ← 0  while (p ≠ 0)    c ← c + 1    if (値[p] = k)      return c    endif    p ← 次[p]  endwhile  return -1 ○整数型: 主処理()  整数型の配列: 値 ← {40, 10, 30, 20}  整数型の配列: 次 ← {4, 3, 1, 0}  return 探す(値, 次, 2, 40)

1. 1
2. 3
3. 4
4. -1

次のスタックに対し、push(3)、push(7)、pop()、push(5)、push(9)、pop()、pop() をこの順で呼び出す。3回の pop() の戻り値を、呼び出した順に並べたものはどれか。

整数型の配列: st ← {0, 0, 0, 0, 0}整数型: sp ← 0 ○push(整数型: x)  sp ← sp + 1  st[sp] ← x ○整数型: pop()  整数型: v ← st[sp]  sp ← sp - 1  return v

1. 3, 7, 5
2. 7, 5, 9
3. 9, 5, 3
4. 7, 9, 5

次の関数は、配列 x の要素をスタックに積んでから取り出すことで、逆順に並べた配列を返す。プログラム中の【a】に入れる式はどれか。

○整数型の配列: 逆順(整数型の配列: x)  整数型の配列: st  整数型の配列: b  整数型: sp ← 0  整数型: i  for (i を 1 から xの要素数 まで 1 ずつ増やす)    sp ← sp + 1    st[sp] ← x[i]  endfor  for (i を 1 から xの要素数 まで 1 ずつ増やす)    b[i] ← 【a】    sp ← sp - 1  endfor  return b

1. st[i]
2. st[sp]
3. st[sp - 1]
4. st[xの要素数]

次のキューに対し、enqueue(5)、enqueue(1)、dequeue()、enqueue(8)、dequeue()、enqueue(3)、dequeue()、dequeue() をこの順で呼び出す。4回の dequeue() の戻り値を、呼び出した順に並べたものはどれか。

整数型の配列: que ← {0, 0, 0, 0, 0, 0}整数型: head ← 1整数型: tail ← 1 ○enqueue(整数型: x)  que[tail] ← x  tail ← tail + 1 ○整数型: dequeue()  整数型: v ← que[head]  head ← head + 1  return v

1. 5, 1, 8, 3
2. 1, 5, 3, 8
3. 5, 8, 1, 3
4. 3, 8, 1, 5

次のプログラムは、要素数 5 の配列を環状に使うキュー（リングバッファ）である。cnt は現在キューに入っている個数を表す。プログラム中の【a】に入れる式はどれか。

整数型: n ← 5整数型の配列: que ← {0, 0, 0, 0, 0}整数型: head ← 1整数型: cnt ← 0 ○enqueue(整数型: x)  整数型: t  if (cnt < n)    t ← 【a】    if (t > n)      t ← t - n    endif    que[t] ← x    cnt ← cnt + 1  endif ○整数型: dequeue()  整数型: v ← que[head]  head ← head + 1  if (head > n)    head ← 1  endif  cnt ← cnt - 1  return v

1. cnt + 1
2. head + cnt - 1
3. head + cnt
4. head + cnt + 1

次のプログラムで、主処理 の戻り値はどれか。

○整数型: 計算(整数型の配列: x)  整数型の配列: st  整数型: sp ← 0  整数型: c ← 0  整数型: i  for (i を 1 から xの要素数 まで 1 ずつ増やす)    if (x[i] > 0)      sp ← sp + 1      st[sp] ← x[i]    else      if (sp > 0)        c ← c × 2 + st[sp]        sp ← sp - 1      endif    endif  endfor  return c ○整数型: 主処理()  整数型の配列: y ← {3, 5, -1, 2, -1, -1, -1}  return 計算(y)

1. 10
2. 24
3. 27
4. 54

次の関数は、配列 x の中で値 k が最後に現れる位置（添字）を返す。k が一つも無いときは -1 を返す。プログラム中の【a】に入れるものはどれか。

○整数型: 最後の位置(整数型の配列: x, 整数型: k)  /* k が最後に現れる位置を返す。無ければ -1 を返す */  整数型: i  整数型: r ← -1  for (i を 1 から xの要素数 まで 1 ずつ増やす)    if (x[i] = k)      【a】    endif  endfor  return r

1. return i
2. r ← i
3. r ← x[i]
4. r ← r + 1

次の2分探索を、x が {2, 5, 8, 11, 14, 17, 21, 26}、k が 21 の状態で実行する。変数 mid に代入される値を代入された順に並べたものはどれか。

○整数型: 2分探索(整数型の配列: x, 整数型: k)  /* x は昇順に整列済み */  整数型: lo ← 1  整数型: hi ← xの要素数  整数型: mid  while (lo ≦ hi)    mid ← (lo + hi) ÷ 2 の商    if (x[mid] = k)      return mid    elseif (x[mid] < k)      lo ← mid + 1    else      hi ← mid - 1    endif  endwhile  return -1

1. 4, 6, 8
2. 4, 5, 7
3. 4, 6, 7
4. 4, 7, 8

次の2分探索は、整列済みの配列 x から k を探し、見つかればその添字を、見つからなければ 0 を返す。プログラム中の【a】に入れるものはどれか。

○整数型: 2分探索(整数型の配列: x, 整数型: k)  /* x は昇順に整列済み */  整数型: lo ← 1  整数型: hi ← xの要素数  整数型: mid  while (lo ≦ hi)    mid ← (lo + hi) ÷ 2 の商    if (x[mid] = k)      return mid    elseif (x[mid] > k)      hi ← mid - 1    else      【a】    endif  endwhile  return 0

1. lo ← mid
2. lo ← hi
3. lo ← mid + 1
4. hi ← mid - 1

要素数が 1,000 の昇順に整列済みの配列に対して2分探索を行うとき、配列の要素と探索対象の値を比較する回数は最大で何回か。

1. 10
2. 9
3. 11
4. 500

次のバブルソートを x が {5, 3, 8, 1, 9, 2} の状態で実行する。外側のループ（変数 i）の1回目が終わった時点での配列 x の内容はどれか。

○整数型の配列: 整列(整数型の配列: x)  整数型: i, j, t  for (i を 1 から xの要素数 - 1 まで 1 ずつ増やす)    for (j を 1 から xの要素数 - i まで 1 ずつ増やす)      if (x[j] > x[j + 1])        t ← x[j]        x[j] ← x[j + 1]        x[j + 1] ← t      endif    endfor  endfor  return x

1. {3, 5, 1, 8, 2, 9}
2. {3, 5, 8, 1, 2, 9}
3. {1, 3, 5, 8, 2, 9}
4. {3, 5, 1, 2, 8, 9}

次のプログラムは、配列 x を降順（大きい順）に並べ替えて返す。プログラム中の【a】に入れる式はどれか。

○整数型の配列: 整列(整数型の配列: x)  /* x を降順に並べ替える */  整数型: i, j, t  for (i を 1 から xの要素数 - 1 まで 1 ずつ増やす)    for (j を 1 から xの要素数 - i まで 1 ずつ増やす)      if (【a】)        t ← x[j]        x[j] ← x[j + 1]        x[j + 1] ← t      endif    endfor  endfor  return x

1. x[j] > x[j + 1]
2. x[i] < x[i + 1]
3. x[j] < x[j - 1]
4. x[j] < x[j + 1]

次の選択ソートを x が {4, 1, 3, 5, 2} の状態で実行する。外側のループの変数 i が 2 の回を終えた時点での配列 x の内容はどれか。

○整数型の配列: 整列(整数型の配列: x)  整数型: i, j, m, t  for (i を 1 から xの要素数 - 1 まで 1 ずつ増やす)    m ← i    for (j を i + 1 から xの要素数 まで 1 ずつ増やす)      if (x[j] < x[m])        m ← j      endif    endfor    t ← x[i]    x[i] ← x[m]    x[m] ← t  endfor  return x

1. {1, 2, 3, 4, 5}
2. {1, 4, 3, 5, 2}
3. {1, 2, 3, 5, 4}
4. {1, 2, 4, 5, 3}

関数 最小位置(x, s) は、配列 x の添字 s 以降で最も小さい要素の添字を返す。この関数を使う選択ソートが正しく昇順に整列するために、プログラム中の【a】に入れる式はどれか。

○整数型: 最小位置(整数型の配列: x, 整数型: s)  /* x[s] 以降で最も小さい要素の添字を返す */  整数型: m ← s  整数型: j  for (j を s + 1 から xの要素数 まで 1 ずつ増やす)    if (【a】)      m ← j    endif  endfor  return m ○整数型の配列: 選択ソート(整数型の配列: x)  整数型: i, m, t  for (i を 1 から xの要素数 - 1 まで 1 ずつ増やす)    m ← 最小位置(x, i)    t ← x[i]    x[i] ← x[m]    x[m] ← t  endfor  return x

1. x[j] < x[m]
2. x[j] < x[s]
3. x[m] < x[j]
4. x[j] < x[j - 1]

次の挿入ソートを x が {6, 2, 9, 4, 7} の状態で実行する。外側のループの変数 i が 4 の回を終えた時点での配列 x の内容はどれか。

○整数型の配列: 挿入ソート(整数型の配列: x)  整数型: i, j, v  for (i を 2 から xの要素数 まで 1 ずつ増やす)    v ← x[i]    j ← i - 1    while (j ≧ 1 and x[j] > v)      x[j + 1] ← x[j]      j ← j - 1    endwhile    x[j + 1] ← v  endfor  return x

1. {2, 6, 9, 4, 7}
2. {2, 4, 6, 7, 9}
3. {2, 6, 4, 9, 7}
4. {2, 4, 6, 9, 7}

次の関数は、昇順に整列済みの二つの配列 p と q を併合して、昇順に整列した一つの配列を返す。プログラム中の【a】に入れる式はどれか。

○整数型の配列: 併合(整数型の配列: p, 整数型の配列: q)  /* p, q はともに昇順に整列済み */  整数型の配列: r  整数型: i ← 1  整数型: j ← 1  整数型: k  for (k を 1 から pの要素数 + qの要素数 まで 1 ずつ増やす)    if (j > qの要素数)      r[k] ← p[i]      i ← i + 1    elseif (i > pの要素数)      r[k] ← q[j]      j ← j + 1    elseif (p[i] ≦ q[j])      r[k] ← p[i]      【a】    else      r[k] ← q[j]      j ← j + 1    endif  endfor  return r

1. i ← i - 1
2. i ← j + 1
3. j ← j + 1
4. i ← i + 1

次のプログラムで 前順(1) を呼び出したとき、出力される順序はどれか。ここで、L[p] は節 p の左の子、R[p] は右の子の添字で、0 は子が無いことを表す。手続 出力 は引数の値を一つ出力する。

文字列型の配列: v ← {"A", "B", "C", "D", "E", "F", "G"}整数型の配列: L ← {2, 4, 6, 0, 0, 0, 0}整数型の配列: R ← {3, 5, 7, 0, 0, 0, 0} ○前順(整数型: p)  if (p ≠ 0)    出力(v[p])    前順(L[p])    前順(R[p])  endif

1. A B D E C F G
2. D B E A F C G
3. D E B F G C A
4. A B C D E F G

次のプログラムで 中順(1) を呼び出したとき、出力される順序はどれか。ここで、L[p] は節 p の左の子、R[p] は右の子の添字で、0 は子が無いことを表す。手続 出力 は引数の値を一つ出力する。

文字列型の配列: v ← {"P", "Q", "R", "S", "T"}整数型の配列: L ← {2, 4, 0, 0, 0}整数型の配列: R ← {3, 5, 0, 0, 0} ○中順(整数型: p)  if (p ≠ 0)    中順(L[p])    出力(v[p])    中順(R[p])  endif

1. P Q S T R
2. S Q T P R
3. S T Q R P
4. S Q T R P

次のプログラムで 後順(1) を呼び出すと D, E, B, C, A の順に出力される。プログラム中の【a】に入れるものはどれか。手続 出力 は引数の値を一つ出力する。

文字列型の配列: v ← {"A", "B", "C", "D", "E"}整数型の配列: L ← {2, 4, 0, 0, 0}整数型の配列: R ← {3, 5, 0, 0, 0} ○後順(整数型: p)  /* 節 p を根とする部分木を後順（帰りがけ順）で出力する */  if (p ≠ 0)    後順(L[p])    【a】    出力(v[p])  endif

1. 後順(p)
2. 後順(L[p])
3. 後順(R[p])
4. 出力(v[R[p]])

次のプログラムは階乗を再帰で求める。主処理 の戻り値が 120 になるように、プログラム中の【a】に入れる式はどれか。

○整数型: 階乗(整数型: n)  if (n ≦ 1)    return 1  else    return 【a】  endif ○整数型: 主処理()  整数型: k ← 5  return 階乗(k)

1. n × 階乗(n)
2. 階乗(n - 1)
3. (n - 1) × 階乗(n - 1)
4. n × 階乗(n - 1)

次のプログラムで 主処理 を1回実行したとき、関数 fib が呼び出される回数は合計で何回か。主処理 からの1回目の呼び出しも数えるものとする。

○整数型: fib(整数型: n)  /* fib(1) = 1, fib(2) = 1 とする */  if (n ≦ 2)    return 1  else    return fib(n - 1) + fib(n - 2)  endif ○整数型: 主処理()  return fib(6)

1. 8
2. 9
3. 15
4. 25

次の関数は、フィボナッチ数（fib(1) = 1, fib(2) = 1）を繰返しで求める。fib(7) が 13 を返すように、プログラム中の【a】に入れる式はどれか。

○整数型: fib(整数型: n)  /* fib(1) = 1, fib(2) = 1 とする */  整数型: p ← 1  整数型: q ← 1  整数型: t  整数型: i  if (n ≦ 2)    return 1  endif  for (i を 3 から n まで 1 ずつ増やす)    t ← p + q    【a】    q ← t  endfor  return q

1. p ← q
2. p ← t
3. q ← p
4. p ← p + q

次のプログラムで 主処理 を実行したとき、出力される順序はどれか。手続 出力 は引数の値を一つ出力する。

○f(整数型: n)  if (n > 0)    f(n - 1)    出力(n)    f(n - 1)  endif ○主処理()  /* 出力された値を左から順に並べたものを答える */  f(3)

1. 1 2 3 2 1
2. 1 2 1 3 1 2 1
3. 3 2 1 1 2 3
4. 1 1 2 1 1 2 3

次の関数 最大(x, lo, hi) は、配列 x の添字 lo から hi までの範囲の最大値を分割統治法で求める。プログラム中の【a】に入れる式はどれか。

○整数型: 最大(整数型の配列: x, 整数型: lo, 整数型: hi)  整数型: mid  整数型: p  整数型: q  if (lo = hi)    return x[lo]  endif  mid ← (lo + hi) ÷ 2 の商  p ← 最大(x, lo, mid)  q ← 【a】  if (p ≧ q)    return p  endif  return q

1. 最大(x, mid, hi)
2. 最大(x, mid + 1, hi)
3. 最大(x, mid, hi - 1)
4. 最大(x, lo, hi)

次の関数 g(m, n) は何を求めるものか。ここで m は正の整数、n は 0 以上の整数とする。

○整数型: g(整数型: m, 整数型: n)  if (n = 0)    return m  else    return g(n, m を n で割った余り)  endif ○主処理()  出力(g(1071, 462))  /* 21 が出力される */

1. m を n で割った商
2. m と n の最小公倍数
3. m と n のうち小さいほう
4. m と n の最大公約数

次のプログラムで h(1) の戻り値はどれか。ここで、L[p] は節 p の左の子、R[p] は右の子の添字で、0 は子が無いことを表す。

整数型の配列: L ← {2, 4, 0, 0, 6, 0, 0}整数型の配列: R ← {3, 5, 0, 0, 7, 0, 0} ○整数型: h(整数型: p)  整数型: s  整数型: t  if (p = 0)    return 0  endif  s ← h(L[p])  t ← h(R[p])  if (s ≧ t)    return s + 1  endif  return t + 1

1. 2
2. 3
3. 7
4. 4