見出し画像
Photo by osushilove666

基本情報技術者試験　科目B練習問題

たかい

基本情報技術者試験科目Bのサンプル問題をClaudeに渡して、生成しています。解答は一番下にあります。


一次元配列①

次のプログラム中の[   ]に入れる正しい答えを、選択肢の中から選んでください。
ここで、配列の要素番号は1から始まるものとします。

関数 reverseArray は、整数型の配列を引数として受け取り、
その配列の要素を逆順に並べ替えた新しい配列を返す関数です。

○整数型の配列: reverseArray(整数型の配列: arr)
  整数型: n ← arrの要素数
  整数型の配列: result ← {n個の未定義の値}
  整数型: i
  
  for (i を 1 から n まで 1 ずつ増やす)
    result[i] ← [   ]
  endfor
  
  return result

選択肢：
a) arr[n - i + 1]
b) arr[n + i - 1]
c) arr[n - i]
d) arr[i]

一次元配列②

整数型配列 A[5]とB[5]が以下のように初期化されているとします：

A ← {1, 2, 3, 4, 5}
B ← {10, 20, 30, 40, 50}

以下の疑似コードを実行した後の配列Aの内容を答えてください。

A[2] ← B[4]
B[3] ← A[5]
A ← B
A[1] ← 100

選択肢：
a) {100, 20, 30, 40, 50}
b) {100, 40, 30, 40, 5}
c) {1, 40, 3, 4, 5}
d) {100, 20, 5, 40, 50}

一次元配列③

以下の疑似コードは、配列内の要素を特定の条件に基づいて並び替えるプログラムです。
このプログラムを最後まで実行したとき、配列 numbers の最終的な内容を答えてください。

整数型の配列: numbers[6] ← {3, 1, 4, 1, 5, 9}
整数型: i, j, temp

for (i ← 1 to 5)
    for (j ← i + 1 to 6)
        if (numbers[i] mod 2 = 0 and numbers[j] mod 2 ≠ 0) then
            temp ← numbers[i]
            numbers[i] ← numbers[j]
            numbers[j] ← temp
        elseif (numbers[i] mod 2 = numbers[j] mod 2 and numbers[i] > numbers[j]) then
            temp ← numbers[i]
            numbers[i] ← numbers[j]
            numbers[j] ← temp
        endif
    endfor
endfor

選択肢：
a) {1, 1, 3, 4, 5, 9}
b) {1, 1, 3, 5, 9, 4}
c) {3, 1, 4, 5, 9, 1}
d) {4, 1, 1, 3, 5, 9}

二次元配列①

次のプログラムは、n × n の二次元整数配列を90度時計回りに回転させるものです。
プログラム中の [   ] に入れる正しい答えを、選択肢の中から選んでください。
ここで、配列の要素番号は1から始まるものとします。

○整数型の二次元配列: rotateImage(整数型の二次元配列: image)
  整数型: n ← imageの行数
  整数型の二次元配列: result ← {n行n列の0}
  整数型: i, j
  
  for (i を 1 から n まで 1 ずつ増やす)
    for (j を 1 から n まで 1 ずつ増やす)
      result[j][n - i + 1] ← [   ]
    endfor
  endfor
  
  return result

選択肢：
a) image[i][j]
b) image[j][i]
c) image[n - j + 1][i]
d) image[i][n - j + 1]

二次元配列②

整数型二次元配列 A[3][3]とB[3][3]が以下のように初期化されているとします：

A ← {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
B ← {{10, 20, 30}, {40, 50, 60}, {70, 80, 90}}

以下の疑似コードを実行した後の配列Aの内容を答えてください。

A[2][2] ← B[1][3]
B[3] ← A[1]
A ← B
A[1][1] ← 100

選択肢：
a) {{100, 20, 30}, {40, 50, 60}, {70, 80, 90}}
b) {{100, 2, 3}, {4, 30, 6}, {7, 8, 9}}
c) {{100, 20, 30}, {40, 50, 60}, {1, 2, 3}}
d) {{1, 2, 3}, {4, 30, 6}, {7, 8, 9}}

ユークリッド互除法

ユークリッド互除法を用いて2つの正の整数の最大公約数を求める関数gcdがあります。
以下の疑似コードで関数gcdが定義されています。

○整数型: gcd(整数型: a, 整数型: b)
    整数型: r
    while (b ≠ 0)
        r ← a mod b
        a ← b
        b ← r
    endwhile
    return a

gcd(48, 180)を実行したときの戻り値を求めてください。

選択肢：
a) 6
b) 12
c) 18
d) 24

閏年の判定

ある年が閏年かどうかを判定する関数 isLeapYear を考えます。
以下の疑似コードの空欄に入る適切な条件式を選んでください。

○真偽値型: isLeapYear(整数型: year)
    if ([   ])
        return true
    elseif (year mod 100 = 0)
        return false
    elseif (year mod 4 = 0)
        return true
    else
        return false
    endif

この関数は、引数として与えられた年が閏年であればtrue、そうでなければfalseを返します。

選択肢：
a) year / 4 = 0
b) year / 100 = 0
c) year mod 400 = 0
d) year > 0

関数と再帰①

次の疑似コードは、与えられた正の整数nに対して、1からnまでの整数の和を計算する再帰関数sumを定義しています。
空欄に入る適切な式を選んでください。

○整数型: sum(整数型: n)
    if (n = 1) then
        return 1
    else
        return [   ]
    endif

整数型: result ← sum(5)

結果として、resultの値は15になります。

選択肢：
a) n + sum(n + 1)
b) n + sum(n - 1)
c) n * sum(n - 1)
d) n - sum(n - 1)

関数と再帰②

フィボナッチ数列を計算する再帰関数 fib が以下のように定義されています：

○整数型: fib(整数型: n)
    if (n ≦ 2) then
        return 1
    else
        return fib(n - 1) + fib(n - 2)
    endif

以下の疑似コードの空欄に入る適切な式を選んでください。

整数型: result ← 0
整数型: i

for (i ← 1 to 4)
    result ← result + fib(i)
endfor

result ← result + [   ]

結果として、result の値は 12 になります。

選択肢：
a) fib(4)
b) fib(5)
c) fib(6)
d) fib(7)

素数判定法

エラトステネスの篩を用いて2から100までの素数を求めるプログラムを考えます。
以下の疑似コードの空欄に入る適切な式を選んでください。

整数型配列 isPrime[100]
整数型: i, j

for (i ← 1 to 100)
    isPrime[i] ← true
endfor

isPrime[1] ← false

for (i ← 2 to 10)  // 10は√100の整数部分
    if (isPrime[i]) then
        j ← [   ]
        while (j ≦ 100)
            isPrime[j] ← false
            j ← j + i
        endwhile
    endif
endfor

結果として、isPrime[i]がtrueである iの値が2から100までの素数となります。

選択肢：
a) i * 2
b) i * i
c) i + 1
d) i + 2

文字列操作

次の疑似コードは、与えられた文字列内の母音（a, e, i, o, u）の数を数え、
その他の文字を"*"に置き換える関数 processStringを定義しています。
空欄に入る適切な式を選んでください。

○整数型: processString(文字列型: str)
    整数型: vowelCount ← 0
    文字列型: result ← ""
    for (i ← 1 to str.length)
        if (str[i] = 'a' or str[i] = 'e' or str[i] = 'i' or str[i] = 'o' or str[i] = 'u') then
            vowelCount ← vowelCount + 1
            result ← result + [   ]
        else
            result ← result + "*"
        endif
    endfor
    str ← result
    return vowelCount

文字列型: text ← "hello"
整数型: count ← processString(text)

結果として、countの値は2になり、textは"*e**o"になります。

選択肢：
a) str[i]
b) "*"
c) ""
d) vowelCount

文字列探索

以下の疑似コードは、ブルートフォース法を用いて文字列Tの中から部分文字列Pを探す関数searchの一部です。
文字列の要素番号は1から始まるものとします。

○整数型: search(文字列型: T, 文字列型: P)
    整数型: n ← T の長さ
    整数型: m ← P の長さ
    整数型: i, j

    for (i ← 1 to n - m + 1)
        j ← 1
        while (j ≦ m and T[i + j - 1] = P[j])
            j ← j + 1
        endwhile
        if (j > m)
            return [   ]  // 部分文字列が見つかった位置を返す
        endif
    endfor
    
    return -1  // 部分文字列が見つからなかった場合

空欄に入る適切な式はどれですか。

選択肢：
a) i
b) i - 1
c) i + 1
d) j

文字列圧縮

次のプログラムは、連続する同じ文字をその文字と出現回数で置き換えることで文字列を圧縮するものです。
例えば、"aabcccccaaa" は "a2b1c5a3" に圧縮されます。
プログラム中の [   ] に入れる正しい答えを、選択肢の中から選んでください。
ここで、文字列の要素番号は1から始まり、文字列の連結には + 演算子を使用します。

○文字列: compressString(文字列: str)
  整数型: n ← strの長さ
  文字列: result ← ""
  整数型: count ← 1
  整数型: i

  for (i を 1 から n まで 1 ずつ増やす)
    if (i < n かつ str[i] = str[i + 1])
      count ← count + 1
    else
      result ← [   ]
      count ← 1
    endif
  endfor

  if (resultの長さ < n)
    return result
  else
    return str
  endif

選択肢：
a) result + str[i] + count
b) result + str[i] + 文字列に変換した(count)
c) result + count + str[i]
d) result + 文字列に変換した(count) + str[i]

大域変数①

次の疑似コードは、大域変数 totalと配列 numbersを使用して、特定の条件を満たす要素の合計を計算します。
空欄に入る適切な式を選んでください。

大域: 整数型: total ← 0
大域: 整数型の配列: numbers ← {3, 7, 1, 9, 4, 6, 8, 2, 5}

○addToTotal(整数型: value)
    total ← [   ]

○processNumbers()
    for (i ← 1 to numbers.length)
        if (numbers[i] > 5) then
            addToTotal(numbers[i])
        endif
    endfor

processNumbers() // 呼び出す関数

結果として、totalの値は30になります。

選択肢：
a) total + numbers[i]
b) total + value
c) value
d) numbers[i]

大域変数②

次の疑似コードは、大域変数 countと局所変数を使用しています。空欄に入る適切な式を選んでください。

大域: 整数型: count ← 0

○incrementCount(整数型: value)
    整数型: count ← 5
    count ← count + value

○processValue(整数型: num)
    if (num > 10) then
        incrementCount(num)
    else
        count ← count + 1
    endif

/* 呼び出す関数 */
processValue(15)
processValue(5)

結果として、大域変数 countの値は [   ] になります。

選択肢：
a) 1
b) 6
c) 20
d) 21

大域変数③

次の疑似コードは、大域変数 xと yを使用しています。空欄に入る適切な式を選んでください。

大域: 整数型: x ← 5
大域: 整数型: y ← 10

○swapIfGreater()
    if (x > y) then
        整数型: temp ← x
        x ← y
        y ← temp
    endif

○incrementBoth(整数型: value)
    x ← x + value
    y ← y + value

○processValues()
    swapIfGreater()
    incrementBoth(x)
    swapIfGreater()

processValues() // 呼び出す関数

結果として、大域変数yの値は[   ]になります。

選択肢：
a) 5
b) 10
c) 15
d) 20

多項式①

次の疑似コードは、ホーナー法を用いて多項式を評価する関数 evaluatePolynomialを実装しています。
多項式は係数の配列で表現され、配列のインデックスは項の次数を表します。
例えば、配列 [a0, a1, a2, a3] は多項式 a0 + a1*x + a2*x^2 + a3*x^3 を表します。

空欄に入る適切な式を選んでください。

○実数型: evaluatePolynomial(実数型の配列: coefficients, 実数型: x)
    実数型: result ← coefficients[coefficientsの要素数]
    整数型: i
    
    for (i ← coefficientsの要素数 - 1 to 1 step -1)
        result ← [   ]
    endfor
    
    return result

実数型の配列: coeff ← {2, -3, 1, 5}  // 2 + (-3)x + x^2 + 5x^3 の係数
実数型: value ← evaluatePolynomial(coeff, 2)

結果として、valueの値は40になります。

選択肢：
a) result * x + coefficients[i]
b) result + coefficients[i] * x^(i-1)
c) (result + coefficients[i]) * x
d) result * x^(i-1) + coefficients[i]

多項式②

次の疑似コードは、二つの多項式を加算する関数 addPolynomialsを実装しています。
多項式は係数の配列で表現され、配列のインデックスは項の次数を表します。
例えば、配列 [3, 0, 2] は多項式 3 + 0x + 2x^2 を表します。

空欄に入る適切な式を選んでください。

○整数型の配列: addPolynomials(整数型の配列: poly1, 整数型の配列: poly2)
    整数型: maxLength ← poly1の要素数 と poly2の要素数 の大きい方
    整数型の配列: result ← {maxLength個の0}
    整数型: i

    for (i ← 1 to maxLength)
        if (i <= poly1の要素数) then
            result[i] ← result[i] + poly1[i]
        endif
        if (i <= poly2の要素数) then
            result[i] ← [   ]
        endif
    endfor

    return result

整数型の配列: p1 ← {1, 2, 3}  // 1 + 2x + 3x^2
整数型の配列: p2 ← {4, 5, 6, 7}  // 4 + 5x + 6x^2 + 7x^3
整数型の配列: sum ← addPolynomials(p1, p2)

選択肢：
a) result[i] + poly2[i]
b) poly1[i] + poly2[i]
c) result[i] - poly2[i]
d) poly2[i]

スタック①

以下の疑似コードは、スタックを操作する関数を定義しています。
スタックの操作は以下のように定義されます：

- push(stack, 値): スタックの一番上に値を追加します。
- pop(stack): スタックの一番上の値を取り出して返し、その値をスタックから削除します。
              スタックが空の場合、-1を返します。

○整数型: operate(整数型の配列: commands)
    整数型の配列: stack ← {}  // 空のスタック
    整数型: result ← 0
    
    for (i ← 1 to commands の要素数)
        if (commands[i] > 0)
            push(stack, commands[i])
        else
            整数型: popped ← pop(stack)
            if (popped ≠ -1)
                result ← result + popped
            endif
        endif
    endfor
    
    return result

operate関数に以下の配列を渡したとき、返される値は[   ]となります。

commands ← {3, 5, 0, 2, 0, 0, 4, 0}

選択肢：
a) 7
b) 9
c) 11
d) 14

スタック②

以下の疑似コードは、文字列を部分的に反転する関数を定義しています。
スタックの操作は以下のように定義されます：

- push(stack, 値): スタックの一番上に値を追加します。
- pop(stack): スタックの一番上の値を取り出して返し、その値をスタックから削除します。
              スタックが空の場合、空文字列 "" を返します。
- isEmpty(stack): スタックが空の場合はtrue、そうでない場合はfalseを返します。

○文字列型: reverseSubstrings(文字列型: str)
    文字型の配列: stack ← {}  // 空のスタック
    文字列型: result ← ""
    
    for (i ← 1 to strの長さ)
        if (str[i] = '[')
            push(stack, '[')
        elseif (str[i] = ']' and not isEmpty(stack))
            文字列型: substring ← ""
            while (not isEmpty(stack) and stack[stackの長さ] ≠ '[')
                substring ← pop(stack) + substring
            endwhile
            if (not isEmpty(stack))
                pop(stack)  // '[' を取り除く
            endif
            for (j ← 1 to substringの長さ)
                push(stack, substring[j])
            endfor
        else
            push(stack, str[i])
        endif
    endfor
    
    while (not isEmpty(stack))
        result ← pop(stack) + result
    endwhile
    
    return result

reverseSubstrings関数に以下の文字列を渡したとき、返される値は[   ]となります。

str ← "ab[cd]ef"

選択肢：
a) "abcdef"
b) "abdcef"
c) "abfedc"
d) "fedcba"

スタック③

次のプログラムは、逆ポーランド表記法で表された数式を計算するものです。
スタックの操作は以下のように定義されます：

- push(stack, 値): スタックの一番上に値を追加します。
- pop(stack): スタックの一番上の値を取り出して返し、その値をスタックから削除します。
              スタックが空の場合、-1を返します。

プログラムを実行した後の大域変数 result の値として正しいものを、選択肢の中から選んでください。

大域: 実数型: result

○calculateRPN(文字列の配列: tokens)
    実数型の配列: stack ← {}  // 空の配列
    整数型: i
    実数型: a, b
    
    for (i を 1 から tokensの要素数 まで 1 ずつ増やす)
        if (tokens[i] = "+")
            b ← pop(stack)
            a ← pop(stack)
            push(stack, a + b)
        elseif (tokens[i] = "-")
            b ← pop(stack)
            a ← pop(stack)
            push(stack, a - b)
        elseif (tokens[i] = "*")
            b ← pop(stack)
            a ← pop(stack)
            push(stack, a * b)
        elseif (tokens[i] = "/")
            b ← pop(stack)
            a ← pop(stack)
            push(stack, a / b)
        else
            push(stack, tokens[i]を実数に変換した値)
        endif
    endfor
    
    result ← pop(stack)

○main()
    文字列の配列: expression ← {"5", "3", "+", "2", "*", "4", "-"}
    calculateRPN(expression)

選択肢：
a) 12
b) 14
c) 16
d) 18

キュー

以下の疑似コードは、文字列を特定のルールに従って変換する関数を定義しています。
キューの操作は以下のように定義されます：

- enqueue(queue, 値): キューの末尾に値を追加します。
- dequeue(queue): キューの先頭の値を取り出して返し、その値をキューから削除します。
                  キューが空の場合、空文字列 "" を返します。
- isEmpty(queue): キューが空の場合はtrue、そうでない場合はfalseを返します。

○文字列型: processString(文字列型: str)
    文字型の配列: queue ← {}  // 空のキュー
    文字列型: result ← ""
    
    for (i ← 1 to strの長さ)
        if (str[i] = '*')
            if (not isEmpty(queue))
                文字型: front ← dequeue(queue)
                enqueue(queue, front)
                result ← result + front
            endif
        elseif (str[i] = '!')
            if (not isEmpty(queue))
                dequeue(queue)
            endif
        else
            enqueue(queue, str[i])
        endif
    endfor
    
    return result

processString関数に以下の文字列を渡したとき、返される値は[   ]となります。

str ← "ab*c*!d*"

選択肢：
a) "abcd"
b) "abc"
c) "aba"
d) "abd"

ハッシュ法

以下のハッシュ表にデータを登録する関数 insertData があります。
ハッシュ表のサイズは10で、空きスロットには-1が格納されています。
衝突が発生した場合は線形探索法で対処します。
ここで、配列の要素番号は0から始まるものとします。

○整数型の配列: insertData(整数型の配列: hashTable, 整数型: key)
    整数型: hash ← key mod 10
    整数型: i ← 0
    
    while (i < 10)
        整数型: index ← (hash + i) mod 10
        if (hashTable[index] = -1) then
            hashTable[index] ← key
            return hashTable
        endif
        i ← i + 1
    endwhile
    
    return hashTable  // ハッシュ表が満杯の場合

初期状態のハッシュ表が以下の通りだとします：

hashTable ← {23, 45, -1, 67, -1, 12, 34, -1, 89, -1}

この状態から、insertData(hashTable, 78) を実行した後の
ハッシュ表の状態はどうなりますか。

選択肢：
a) {23, 45, -1, 67, -1, 12, 34, -1, 89, 78}
b) {23, 45, -1, 67, -1, 12, 34, -1, 78, -1}
c) {23, 45, -1, 67, 78, 12, 34, -1, 89, -1}
d) {23, 45, -1, 67, -1, 12, 34, 78, 89, -1}

バブルソート

次の疑似コードは、バブルソートアルゴリズムを用いて整数型配列を昇順にソートする関数 bubbleSortを実装しています。
空欄に入る適切な式を選んでください。

○bubbleSort(整数型の配列: arr)
    整数型: n ← arrの要素数
    整数型: i, j, temp
    for (i ← 1 to n - 1)
        for (j ← 1 to n - i)
            if ([   ]) then
                temp ← arr[j]
                arr[j] ← arr[j + 1]
                arr[j + 1] ← temp
            endif
        endfor
    endfor

整数型の配列: numbers ← {5, 2, 8, 12, 1, 6}
bubbleSort(numbers) // 呼び出す関数

結果として、numbers配列は {1, 2, 5, 6, 8, 12} となります。

選択肢：
a) arr[j] < arr[j + 1]
b) arr[j] > arr[j + 1]
c) arr[i] > arr[j]
d) arr[i] < arr[j]

選択ソート

次の疑似コードは、選択ソートアルゴリズムを用いて整数型配列を昇順にソートする関数 selectionSortを実装しています。
空欄に入る適切な式を選んでください。

○selectionSort(整数型の配列: arr)
    整数型: n ← arrの要素数
    整数型: i, j, minIndex, temp
    for (i ← 1 to n - 1)
        minIndex ← i
        for (j ← i + 1 to n)
            if ([   ]) then
                minIndex ← j
            endif
        endfor
        temp ← arr[i]
        arr[i] ← arr[minIndex]
        arr[minIndex] ← temp
    endfor

整数型の配列: numbers ← {64, 25, 12, 22, 11}
selectionSort(numbers) // 呼び出す関数

結果として、numbers配列は {11, 12, 22, 25, 64} となります。

選択肢：
a) arr[j] < arr[i]
b) arr[j] > arr[minIndex]
c) arr[j] < arr[minIndex]
d) arr[j] > arr[i]

挿入ソート

以下は挿入ソートのアルゴリズムを示した疑似コードです。

○insertionSort(整数型の配列: arr)
    整数型: n ← arrの要素数
    整数型: i, j, key

    for (i ← 2 to n)
        key ← arr[i]
        j ← i - 1
        
        while (j > 0 and arr[j] > key)
            arr[j + 1] ← arr[j]
            j ← j - 1
        endwhile
        
        arr[j + 1] ← key
    endfor

整数型配列 data[6] ← {5, 2, 4, 6, 1, 3} に対して insertionSort(data) を実行します。
外側のforループが3回目（i=4のとき）を終了した直後の配列の状態を答えてください。

選択肢：
a) {2, 4, 5, 6, 1, 3}
b) {2, 4, 5, 1, 6, 3}
c) {2, 4, 5, 6, 3, 1}
d) {2, 5, 4, 6, 1, 3}

マージソート

以下のプログラムは、整列済みの2つの配列を併合するものです。
プログラムを実行した際、αとβのwhileループがそれぞれ何回実行されるかを答えてください。
なお、配列の要素番号は1から始まるものとします。

大域: 整数型の配列: mergedArray

○merge(整数型の配列: arr1, 整数型の配列: arr2)
    整数型: i ← 1, j ← 1, k ← 1
    整数型: n1 ← arr1の要素数
    整数型: n2 ← arr2の要素数
    
    mergedArray ← {(n1 + n2)個の0}
    
    while (i ≦ n1 かつ j ≦ n2)
        if (arr1[i] ≦ arr2[j])
            mergedArray[k] ← arr1[i]
            i ← i + 1
        else
            mergedArray[k] ← arr2[j]
            j ← j + 1
        endif
        k ← k + 1
    endwhile
    
    while (i ≦ n1)  //α
        mergedArray[k] ← arr1[i]
        i ← i + 1
        k ← k + 1
    endwhile
    
    while (j ≦ n2)  //β
        mergedArray[k] ← arr2[j]
        j ← j + 1
        k ← k + 1
    endwhile

○main()
    整数型の配列: array1 ← {2, 4, 6, 8, 10}
    整数型の配列: array2 ← {1, 3, 5, 7, 9}
    
    merge(array1, array2)

選択肢：
a) α: 0回, β: 0回
b) α: 0回, β: 1回
c) α: 1回, β: 0回
d) α: 2回, β: 2回

クイックソート

以下はクイックソートのアルゴリズムを示した疑似コードです。

整数型配列 data[8] ← {5, 2, 9, 1, 7, 6, 3, 8} に対して quickSort(data, 1, 8) を実行します。
最初のpartition呼び出しが完了し、その結果で分割された左右の部分配列それぞれに対して
再帰的にquickSortが呼ばれた直後（つまり、最初のpartitionと、その結果による2回の
再帰呼び出しが完了した直後）の配列の状態を答えてください。

○quickSort(整数型の配列: arr, 整数型: low, 整数型: high)
    if (low < high)
        整数型: pi ← partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    endif

○整数型: partition(整数型の配列: arr, 整数型: low, 整数型: high)
    整数型: pivot ← arr[high]
    整数型: i ← low - 1
    整数型: j, temp

    for (j ← low to high - 1)
        if (arr[j] < pivot)
            i ← i + 1
            temp ← arr[i]
            arr[i] ← arr[j]
            arr[j] ← temp
        endif
    endfor

    temp ← arr[i + 1]
    arr[i + 1] ← arr[high]
    arr[high] ← temp

    return i + 1

選択肢：
a) {2, 1, 3, 5, 7, 6, 9, 8}
b) {1, 2, 3, 5, 7, 6, 8, 9}
c) {2, 1, 3, 5, 7, 6, 8, 9}
d) {1, 2, 3, 5, 9, 6, 7, 8}

二分探索

次の疑似コードは、昇順にソートされた整数型配列 dataから、指定された値 targetを二分探索するアルゴリズムです。
空欄に入る適切な式を選んでください。

○整数型: binarySearch(整数型の配列: data, 整数型: target)
    整数型: left ← 1
    整数型: right ← dataの要素数
    
    while (left ≦ right)
        整数型: mid ← (left + right) ÷ 2
        if (data[mid] = target) then
            return mid
        elseif (data[mid] < target) then
            left ← [   ]
        else
            right ← mid - 1
        endif
    endwhile
    
    return -1  // targetが見つからない場合

整数型の配列: sortedArray ← {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
整数型: result ← binarySearch(sortedArray, 13)

選択肢：
a) left + 1
b) mid - 1
c) mid + 1
d) right - 1

貪欲法

硬貨の金額の組み合わせで特定の金額を作る問題を考えます。
利用可能な硬貨の種類は {500円, 100円, 50円, 10円, 5円, 1円} です。
貪欲法を用いて、できるだけ少ない枚数の硬貨で目標金額を作ることを考えます。

以下の疑似コードは、この問題を貪欲法で解くアルゴリズムです。

○coinChange(整数型: target)
    整数型の配列: coins ← {500, 100, 50, 10, 5, 1}
    整数型: count ← 0
    整数型: i
    for (i ← 1 to coinsの要素数)
        while (target ≧ coins[i])
            target ← target - coins[i]
            count ← count + 1
        endwhile
    endfor
    return count

このアルゴリズムを使って、targetを728円としたときの
coinChange(target)の戻り値を求めてください。

選択肢：
a) 6
b) 7
c) 8
d) 9

状態遷移

文字列を受け付ける簡単な状態機械があります。この状態機械は以下の3つの状態を持ちます：

0: 初期状態
1: 'a'を受け付けた状態
2: 受理状態

状態遷移は以下の二次元配列transitionで定義されています。
transition[現在の状態][入力文字]で次の状態が決まります。
ここで、配列の要素番号は0から始まるものとします。

transition ← {{0, 1, 0},  // 状態0からの遷移
              {2, 1, 0},  // 状態1からの遷移
              {2, 2, 3}}  // 状態2からの遷移

入力文字は以下のように数値に変換されます：
'a': 0
'b': 1
'c': 2

以下の疑似コードで状態遷移を行う関数processStringが定義されています：

○整数型: processString(文字列型: input)
    整数型: state ← 0
    整数型: i
    for (i ← 1 to inputの長さ)
        文字型: ch ← input[i]
        整数型: charIndex
        if (ch = 'a') then
            charIndex ← 0
        elseif (ch = 'b') then
            charIndex ← 1
        else
            charIndex ← 2
        endif
        state ← transition[state][charIndex]
    endfor
    return state

processString("abba")を実行したときの戻り値はいくつになりますか。

選択肢：
a) 0
b) 1
c) 2
d) 3

単方向リスト①

単方向リストを操作する関数removeEvenを考えます。この関数は、リストから偶数の要素をすべて削除します。
クラスListElementは単方向リストの要素を表し、以下のメンバ変数を持ちます：

- val: 整数型 (要素の値)
- next: ListElement型 (次の要素への参照。次の要素がない場合は未定義)

関数removeEvenの疑似コードは以下の通りです：

○removeEven(ListElement: head)
    ListElement: prev ← 未定義の値
    ListElement: current ← head
    while (current が 未定義 ではない)
        if (current.val mod 2 = 0) then
            if (prev が 未定義) then
                head ← current.next
            else
                [   ]
            endif
            current ← current.next
        else
            prev ← current
            current ← current.next
        endif
    endwhile
    return head

空欄に入る適切な式を選んでください。

選択肢：
a) prev ← current.next
b) prev.next ← current
c) prev.next ← current.next
d) current ← prev.next

単方向リスト②

単方向リストを逆順にする関数reverseListを考えます。
クラスListElementは単方向リストの要素を表し、以下のメンバ変数を持ちます：

- val: 整数型 (要素の値)
- next: ListElement型 (次の要素への参照。次の要素がない場合は未定義)

関数reverseListの疑似コードは以下の通りです：

○reverseList(ListElement: head)
    ListElement: prev ← 未定義の値
    ListElement: current ← head
    ListElement: next

    while (current が 未定義 ではない)
        next ← current.next
        [   ]
        prev ← current
        current ← next
    endwhile

    return prev  // 新しいリストの先頭

空欄に入る適切な式を選んでください。

選択肢：
a) current.next ← prev
prev.next ← current

b) current.next ← prev
current ← prev

c) prev.next ← current
current.next ← next

d) current.next ← prev

双方向リスト①

双方向リストを操作する関数insertSortedを考えます。
この関数は、ソートされた双方向リストに新しい要素を適切な位置に挿入します。

クラスDoubleListElementは双方向リストの要素を表し、以下のメンバ変数を持ちます：
- val: 整数型 (要素の値)
- next: DoubleListElement型 (次の要素への参照。次の要素がない場合は未定義)
- prev: DoubleListElement型 (前の要素への参照。前の要素がない場合は未定義)

関数insertSortedの疑似コードは以下の通りです：

○insertSorted(DoubleListElement: head, 整数型: newValue)
    DoubleListElement: newNode ← 新しいDoubleListElement
    newNode.val ← newValue
    newNode.next ← 未定義の値
    newNode.prev ← 未定義の値

    if (head が 未定義) then
        return newNode
    endif

    if (newValue < head.val) then
        newNode.next ← head
        head.prev ← newNode
        return newNode
    endif

    DoubleListElement: current ← head
    while (current.next が 未定義 ではない and current.next.val < newValue)
        current ← current.next
    endwhile

    [   ]
    
    if (current.next が 未定義 ではない) then
        current.next.prev ← newNode
    endif

    return head

空欄に入る適切な式を選んでください。

選択肢：
a) newNode.next ← current.next
current.next ← newNode

b) newNode.prev ← current
current.next ← newNode

c) newNode.next ← current.next
newNode.prev ← current
current.next ← newNode

d) newNode.next ← current
newNode.prev ← current.prev
current.prev ← newNode

双方向リスト②

双方向リストの中央の要素を見つける関数findMiddleを考えます。
リストの要素数が偶数の場合は、二つの中央要素のうち後ろの要素を返します。

クラスDoubleListElementは双方向リストの要素を表し、以下のメンバ変数を持ちます：
- val: 整数型 (要素の値)
- next: DoubleListElement型 (次の要素への参照。次の要素がない場合は未定義)
- prev: DoubleListElement型 (前の要素への参照。前の要素がない場合は未定義)

関数findMiddleの疑似コードは以下の通りです：

○findMiddle(DoubleListElement: head, DoubleListElement: tail)
    DoubleListElement: front ← head
    DoubleListElement: back ← tail

    while (front ≠ back and front.next ≠ back)
        [   ]
    endwhile

    if (front.next = back) then
        return back
    else
        return front
    endif

空欄に入る適切な式を選んでください。

選択肢：
a) front ← front.next
back ← back.prev

b) front ← front.next
back ← back.next

c) front ← front.next.next
back ← back.prev

d) front ← front.next.next
back ← back.prev.prev

基数変換①

10進数を2進数に変換する関数 decimalToBinary があります。
以下の疑似コードで関数 decimalToBinary が定義されています。
ここで、配列の要素番号は1から始まるものとします。

○整数型の配列: decimalToBinary(整数型: n)
    整数型の配列: binary ← {}  // 空の配列
    整数型: i ← 1
    while (n > 0)
        binary[i] ← n mod 2
        n ← n ÷ 2  // 整数除算
        i ← i + 1
    endwhile
    return binary

decimalToBinary(44) を実行したときの戻り値の配列を
先頭の要素から順に並べたものは何になりますか。

選択肢：
a) {0, 0, 1, 0, 1, 1}
b) {0, 0, 1, 1, 0, 1}
c) {1, 0, 0, 0, 1, 1}
d) {1, 1, 0, 0, 0, 1}

基数変換②

16進数の文字列を10進数の整数に変換する関数 hexToDecimal があります。
以下の疑似コードで関数 hexToDecimal が定義されています。
ここで、文字列の要素番号は1から始まるものとします。

○整数型: hexToDecimal(文字列型: hex)
    整数型: decimal ← 0
    整数型: len ← hexの長さ
    整数型: i
    for (i ← 1 to len)
        文字型: ch ← hex[i]
        整数型: digit
        if ('0' ≦ ch and ch ≦ '9') then
            digit ← ch を整数に変換した値
        else
            digit ← (chを大文字に変換した文字 - 'A') + 10
        endif
        decimal ← decimal * 16 + digit
    endfor
    return decimal

hexToDecimal("2AF") を実行したときの戻り値はいくつになりますか。

選択肢：
a) 587
b) 671
c) 686
d) 687

ビット操作と論理演算

8ビット型の変数xとyがあり、以下のように初期化されているとします：

x ← 01001011
y ← 11000101

以下の疑似コードを実行した後のzの値を2進数で答えてください。
なお、演算子∧はビット単位の論理積、演算子∨はビット単位の論理和、
演算子>>は論理右シフト、演算子<<は論理左シフトを表します。

z ← (x ∧ (y >> 2)) ∨ ((x << 1) ∧ y)

結果として、zの値は[   ]となります。

選択肢：
a) 10000100
b) 10000101
c) 10001101
d) 11000101

パリティビットと誤り検出

8ビットのデータに対して偶数パリティビットを付加し、1バイトのデータを作成する関数を考えます。
その後、受信したデータにエラーがないかを確認する関数を作成します。
以下の疑似コードの空欄に入る適切な式を選んでください。

○整数型: addParity(整数型: data)  // dataは0から255までの値
    整数型: count ← 0
    整数型: i
    for (i ← 0 to 7)
        if ((data ÷ (2のi乗)) mod 2 = 1) then
            count ← count + 1
        endif
    endfor
    if ([   ]) then
        return data
    else
        return data + 256  // パリティビットを1に設定
    endif

○真偽値型: checkParity(整数型: receivedData)  // receivedDataは0から511までの値
    整数型: count ← 0
    整数型: i
    for (i ← 0 to 8)  // パリティビットを含めて9ビットをチェック
        if ((receivedData ÷ (2のi乗)) mod 2 = 1) then
            count ← count + 1
        endif
    endfor
    return (count mod 2 = 0)  // 偶数パリティなので、1の数が偶数ならtrue

addParity関数は8ビットのデータに偶数パリティビットを付加し、checkParity関数は受信したデータのパリティをチェックします。

選択肢：
a) count = 0
b) count mod 2 = 0
c) count > 4
d) count < 4

無向グラフの隣接行列

5頂点からなる無向グラフGがあります。グラフGの隣接行列Aが以下のように与えられています。

A ← {{0, 1, 0, 1, 1},
     {1, 0, 1, 1, 0},
     {0, 1, 0, 1, 1},
     {1, 1, 1, 0, 0},
     {1, 0, 1, 0, 0}}

以下の疑似コードを実行した後のcountの値を求めてください。
ここで、nは頂点数（この場合は5）です。

count ← 0
for (i ← 1 to n)
    for (j ← 1 to n)
        if (A[i][j] = 1 and i < j) then
            count ← count + 1
        endif
    endfor
endfor

選択肢：
a) 6
b) 7
c) 10
d) 14

グラフ走査

以下の無向グラフについて考えます。グラフは隣接リストで表現されています。
ここで、配列の要素番号は1から始まるものとします。

graph ← {{2, 3},    // 頂点1は頂点2と3に隣接
          {1, 4, 5}, // 頂点2は頂点1, 4, 5に隣接
          {1, 6},    // 頂点3は頂点1と6に隣接
          {2},       // 頂点4は頂点2に隣接
          {2},       // 頂点5は頂点2に隣接
          {3, 7},    // 頂点6は頂点3と7に隣接
          {6}}       // 頂点7は頂点6に隣接

このグラフに対して、ある頂点からの最短経路長を求める関数 shortestPath が
以下の疑似コードで定義されています：

○整数型の配列: shortestPath(整数型の配列の配列: graph, 整数型: start)
    整数型: n ← graphの要素数
    整数型の配列: distances ← {n個の-1}  // -1は未訪問を表す
    整数型の配列: queue ← {}
    
    distances[start] ← 0
    queueの末尾にstartを追加
    
    while (queueが空ではない)
        整数型: current ← queueの先頭要素
        queueの先頭要素を削除
        
        for (各 neighbor in graph[current])
            if (distances[neighbor] = -1) then
                distances[neighbor] ← distances[current] + 1
                queueの末尾にneighborを追加
            endif
        endfor
    endwhile
    
    return distances

shortestPath(graph, 1) を実行したときの戻り値の配列において、
頂点7までの最短経路長はいくつになりますか。

選択肢：
a) 2
b) 3
c) 4
d) 5

ゲーム木の探索

次の構造は、2人対戦ゲームにおける3手先までのゲーム木を表しています。
各ノードの数字はその状態の評価値を示し、値が大きいほどMAXプレイヤーに有利です。

A (MAX)
├── B (MIN)
│   ├── D (MAX): [1, 2, 3]
│   └── E (MAX): [4, 5, 6]
└── C (MIN)
    ├── F (MAX): [7, 8, 9]
    └── G (MAX): [2, 3, 4]

ゲーム木の各レベルのプレイヤーは以下の通りです：
レベル1 (A): MAXプレイヤー（評価値が最大となる手を選択）
レベル2 (B, C): MINプレイヤー（評価値が最小となる手を選択）
レベル3 (D, E, F, G): MAXプレイヤー（評価値が最大となる手を選択）
レベル4: 各状態の評価値（括弧内の数値）

ミニマックス法を用いて、ノードAの評価値を求めたとき、その値は[   ]となります。

選択肢：
a) 3
b) 4
c) 6
d) 9

ナップサック問題

以下のプログラムは、0-1ナップサック問題を動的計画法で解くものです。
n個のアイテムがあり、各アイテムには価値と重さが設定されています。
ナップサックの最大重量が与えられたとき、価値の合計が最大となるようにアイテムを選択します。
プログラムを実行した後の大域変数 maxValue の値として正しいものを選んでください。。
なお、このプログラムでは配列の要素番号は1から始まるものとします。

大域: 整数型: maxValue

○knapsack(整数型: W, 整数型の配列: weights, 整数型の配列: values, 整数型: n)
    整数型の二次元配列: dp ← {(n+1)行(W+1)列の0}
    整数型: i, w

    for (i を 1 から n まで 1 ずつ増やす)
        for (w を 1 から W まで 1 ずつ増やす)
            if (weights[i] ≦ w)
                dp[i][w] ← max(values[i] + dp[i-1][w-weights[i]], dp[i-1][w])
            else
                dp[i][w] ← dp[i-1][w]
            endif
        endfor
    endfor

    maxValue ← dp[n][W]

○整数型: max(整数型: a, 整数型: b)
    if (a > b)
        return a
    else
        return b
    endif

○main()
    整数型: W ← 10
    整数型の配列: weights ← {2, 3, 4, 5}
    整数型の配列: values ← {3, 4, 5, 6}
    整数型: n ← 4  // アイテムの数

    knapsack(W, weights, values, n)

選択肢：
a) 10
b) 11
c) 12
d) 13

繰り返し二乗法

以下のプログラムは、繰り返し二乗法を用いて a^n mod m を計算するものです。
プログラムを実行した際の出力として正しいものを選んでください。

大域: 整数型: result

○modPow(整数型: a, 整数型: n, 整数型: m)
    result ← 1
    a ← a mod m
    
    while (n > 0)
        if (n mod 2 = 1)
            result ← (result * a) mod m
        endif
        a ← (a * a) mod m
        n ← n ÷ 2
    endwhile

○main()
    整数型: base ← 7
    整数型: exponent ← 256
    整数型: modulus ← 13
    
    modPow(base, exponent, modulus)
    // result を出力

選択肢：
a) 3
b) 7
c) 9
d) 11

Diffie-Hellman鍵交換法

Diffie-Hellman鍵交換法において、AliceとBobが以下のパラメータを使用します：

p = 11 （素数）
g = 2 （原始根）
a = 3 （Aliceの秘密の整数）
b = 4 （Bobの秘密の整数）

以下の疑似コードを実行した後の変数sの値を求めてください。

○整数型: power(整数型: base, 整数型: exponent, 整数型: modulus)
    整数型: result ← 1
    while (exponent > 0)
        if (exponent mod 2 = 1)
            result ← (result * base) mod modulus
        endif
        base ← (base * base) mod modulus
        exponent ← exponent ÷ 2
    endwhile
    return result

整数型: A ← power(g, a, p)
整数型: B ← power(g, b, p)
整数型: s ← power(B, a, p)

結果として、共有秘密鍵sの値は[   ]となります。

選択肢：
a) 4
b) 5
c) 7
d) 9


答え

  1. 一次元配列①　a

  2. 一次元配列②　d

  3. 一次元配列③　b

  4. 二次元配列①　a

  5. 二次元配列②　c

  6. ユークリッド互除法　b

  7. 閏年の判定　c

  8. 関数と再帰①　b

  9. 関数と再帰②　b

  10. 素数判定法　b

  11. 文字列操作　a

  12. 文字列探索　a

  13. 文字列圧縮　b

  14. 大域変数①　b

  15. 大域変数②　a

  16. 大域変数③　c

  17. 多項式①　a

  18. 多項式②　a

  19. スタック①　d

  20. スタック②　b

  21. スタック③　a

  22. キュー　b

  23. ハッシュ法　a

  24. バブルソート　b

  25. 選択ソート　c

  26. 挿入ソート　a

  27. クイックソート　c

  28. 二分探索　c

  29. 貪欲法　d

  30. 状態遷移　c

  31. 単方向リスト①　c

  32. 単方向リスト②　d

  33. 双方向リスト①　c

  34. 双方向リスト②　a

  35. 基数変換①　b

  36. 基数変換②　d

  37. ビット操作と論理演算　b

  38. パリティビットと誤り検出　b

  39. 無向グラフの隣接行列　b

  40. グラフ走査　c

  41. ゲーム木の探索　b

  42. ナップサック問題　d

  43. 繰り返し二乗法　c

  44. Diffie-Hellman鍵交換法　a


この記事が気に入ったらサポートをしてみませんか？