基本情報技術者試験 科目B対策問題

（１）バブルソートの実装

以下の疑似言語で記述されたバブルソートのアルゴリズムを実行した際、配列 a の各要素の値が、各ループの終了後にどのように変化するかをトレースしてください。入力配列 a は以下の通りです。

a = [5, 2, 8, 1, 9, 4]

アルゴリズム バブルソート(a)
入力: 整数配列 a[1...n] (n は配列の要素数)
出力: 昇順にソートされた整数配列 a

for i = 1 to n-1 do
  for j = 1 to n-i do
    if a[j] > a[j+1] then
      a[j] と a[j+1] を交換する
    end if
  end for
end for

以下の表に、各ループの終了後の a の値を示してください。 i と j はループ変数です。 交換 の列は、そのループで要素の交換が行われたかどうかを示してください。

（２）クイックソートの実装

以下の疑似コードは、クイックソートアルゴリズムの一部です。空欄(1)～(5)に当てはまる適切な選択肢を選んでください。 ピボットは配列の先頭要素とします。

アルゴリズム クイックソート(a, left, right)
入力: 整数配列 a, 開始インデックス left, 終了インデックス right
出力: a[left...right] が昇順にソートされた配列 a

もし left >= right ならば 終了する

pivot = a[left]
i = left + 1
j = right

while i <= j do
  while i <= right かつ a[i] <= pivot do
    i = i + (1)
  end while
  while j >= left + 1 かつ a[j] >= pivot do
    j = j + (2)
  end while
  もし i < j ならば
    a[i] と a[j] を交換する
  end if
end while

a[left] と a[j] を交換する

クイックソート(a, left, j + (3))
クイックソート(a, j + (4), right)

(1) a) -1 b) 1 c) 0 d) 2

(2) a) 1 b) -1 c) 0 d) 2

(3) a) 0 b) 1 c) -1 d) 2

(4) a) 0 b) 1 c) -1 d) 2

(5) このアルゴリズムの最悪計算量は？ a) O(n log n) b) O(n) c) O(n^2) d) O(log n)

（３）二分探索のアルゴリズム

以下の疑似言語で記述された二分探索アルゴリズムを用いて、ソート済みの配列 a から値 target を検索します。 各ステップでの left, mid, right の値と、比較結果をトレースしてください。入力配列 a と検索対象 target は以下の通りです。

a = [2, 5, 7, 11, 13, 17, 19, 23, 29, 31]
target = 17

アルゴリズム 二分探索(a, target)
入力: 昇順にソートされた整数配列 a, 検索対象の整数 target
出力: target が a に存在する場合はそのインデックス、存在しない場合は -1

left = 0
right = a.length - 1

while left <= right do
  mid = (left + right) / 2
  if a[mid] == target then
    return mid
  else if a[mid] < target then
    left = mid + 1
  else
    right = mid - 1
  end if
end while

return -1

以下の表に、各ステップでの left, mid, right の値、a[mid] の値、比較結果、そして処理内容をまとめてください。

（４）線形探索のアルゴリズム

以下の疑似言語で記述された線形探索アルゴリズムを用いて、配列 a から値 target を検索します。 各ステップでの i の値と、比較結果をトレースしてください。 見つかった場合はそのインデックス、見つからない場合は -1 を返すものとします。入力配列 a と検索対象 target は以下の通りです。

a = [5, 2, 8, 1, 9, 4]
target = 9

アルゴリズム 線形探索(a, target)
入力: 整数配列 a, 検索対象の整数 target
出力: target が a に存在する場合はそのインデックス、存在しない場合は -1

for i = 0 to a.length - 1 do
  if a[i] == target then
    return i
  end if
end for

return -1

以下の表に、各ステップでの i の値、a[i] の値、比較結果 (a[i] と target)、そして処理内容をまとめてください。

（５）ハッシュ表探索法のアルゴリズムの実装

以下の疑似コードは、ハッシュ表を用いた探索アルゴリズムの一部です。ハッシュ表はサイズ10で、衝突処理にはチェーン法を用います。ハッシュ関数は h(key) = key mod 10 です。空欄(1)～(3)に当てはまる適切な選択肢を選んでください。

アルゴリズム ハッシュ表探索(hash_table, key)
入力: ハッシュ表 hash_table, 検索キー key
出力: key に対応する値、key が存在しない場合は null

index = h(key) // ハッシュ関数

node = hash_table[index]
while node != (1) do
  if node.key == key then
    return node.value
  end if
  node = node.(2)
end while

return (3)

選択肢:

(1) a) null b) 0 c) key d) index

(2) a) key b) next c) value d) previous

(3) a) node b) key c) null d) index

（６）10進数の数値を2進数に変換するプログラム

以下の疑似言語で記述されたプログラムは、10進数の整数 decimal を2進数に変換し、その結果を文字列として返すものです。 decimal に 25 を入力した場合、プログラムの各ステップでの変数の値をトレースし、最終的な出力結果を答えてください。

アルゴリズム decimalToBinary(decimal)
入力: 10進数の整数 decimal
出力: 2進数の文字列 binary

binary = ""
while decimal > 0 do
  remainder = decimal mod 2
  binary = remainder + binary // 剰余を文字列の先頭に連結
  decimal = decimal / 2 // 整数除算
end while

return binary

以下の表に、各ステップでの decimal, remainder, binary の値をまとめます。 decimal / 2 は整数除算であることに注意してください。

（７）2進数の加算を行うアルゴリズム

以下の疑似コードは、2進数を文字列として受け取り、2進数の加算を行うアルゴリズムです。空欄(1)～(3)に当てはまる適切な式または値を記述してください。 このアルゴリズムは、繰り上がりを考慮した加算を行います。

アルゴリズム binaryAddition(a, b)
入力: 2進数の文字列 a, b (同じ桁数とする)
出力: 2進数の文字列 result

n = a.length  // aとbは同じ桁数なので、どちらを使ってもよい
result = ""
carry = 0

for i = n - 1 downto 0 do  // 下位桁から処理
  digit_a = a[i] - '0'  // 文字を数値に変換
  digit_b = b[i] - '0'  // 文字を数値に変換
  sum = digit_a + digit_b + carry

  if sum == 0 then
    result = "0" + result
    carry = 0
  else if sum == 1 then
    result = "1" + result
    carry = 0
  else if sum == 2 then
    result = "0" + result
    carry = (1)
  else // sum == 3
    result = "1" + result
    carry = (2)
  end if
end for

if carry == 1 then
  result = "1" + result
end if

return result

（８）クラスとオブジェクト

以下の疑似言語は、Dog というクラスと、そのオブジェクト myDog を定義しています。空欄 (1)～(3) に適切なコードを記述してください。

クラス Dog {
  属性:
    名前: 文字列
    年齢: 整数

  メソッド:
    コンストラクタ(名前, 年齢) {
      この.名前 = 名前
      この.年齢 = 年齢
    }

    吠える() {
      出力 "ワン！"
    }

    年齢を表示する() {
      出力 "年齢は " + この.年齢 + " 歳です。"
    }

    年齢を設定する(新しい年齢) {
      (1)
    }
}

// Dogクラスのオブジェクトを作成
myDog = 新しい Dog("ポチ", 3)

// メソッドを呼び出す
myDog.吠える()
myDog.年齢を表示する()

// 年齢を変更する
myDog.年齢を設定する(5)

// 変更後の年齢を表示する
myDog.年齢を表示する()

// (2)  Catクラスを作成してください。属性は名前と種類、メソッドは鳴き声「ニャー」を出すメソッドを含めてください。

クラス Cat {
  属性:
    名前: 文字列
    種類: 文字列

  メソッド:
    コンストラクタ(名前, 種類) {
      この.名前 = 名前
      この.種類 = 種類
    }

    鳴き声を出す() {
      出力 "ニャー！"
    }
}

（９）継承とポリモーフィズム

以下の疑似コードは、動物を表す Animal クラスとそのサブクラスである Dog クラスと Cat クラスを定義しています。 Animal クラスは抽象クラスであり、speak() メソッドは抽象メソッドとして定義されています。 Dog クラスと Cat クラスはそれぞれ speak() メソッドをオーバーライドしています。 Pet インターフェースは、pet() メソッドを定義しています。 Dog クラスと Cat クラスはそれぞれ Pet インターフェースを実装しています。 空欄 (1)～(3) に最も適切なコードを選択肢から選んでください。

インターフェース Pet {
  メソッド pet(): ヌル
}

抽象クラス Animal {
  属性:
    名前: 文字列

  メソッド:
    コンストラクタ(名前) {
      この.名前 = 名前
    }
    抽象メソッド speak(): ヌル
}

クラス Dog 継承 Animal 実装 Pet {
  メソッド:
    コンストラクタ(名前) {
      スーパークラスコンストラクタ(名前)
    }
    speak() {
      出力 この.名前 + "はワンワンと鳴きます。"
    }
    pet() {
      出力 この.名前 + "をなでなでします。"
    }
}

クラス Cat 継承 Animal 実装 Pet {
  メソッド:
    コンストラクタ(名前) {
      スーパークラスコンストラクタ(名前)
    }
    speak() {
      出力 この.名前 + "はニャーニャーと鳴きます。"
    }
    pet() {
      出力 この.名前 + "をなでなでします。"
    }
}

動物リスト = 新しい リスト()
動物リスト.追加(新しい Dog("ポチ"))
動物リスト.追加(新しい Cat("タマ"))

for 各 動物 in 動物リスト do
  動物.speak()
  (1) // Petインターフェースのpet()メソッドを呼び出す記述を選んでください。
end for

// (2) Animalクラスに、共通の属性「種類」を追加するための記述を選んでください。


// (3)  Birdクラスを追加してください。Animalクラスを継承し、speak()メソッドで鳴き声を表示します。Petインターフェースは実装しません。

選択肢 (1):

a) 動物.pet()
b) 動物.speak()
c) 動物.名前
d) エラーが発生する

選択肢 (2): (Animalクラスの修正)

a) 属性: 種類: 文字列
b) メソッド: 種類を設定する(種類): ヌル
c) 属性: 種類: 数値
d) 変更不要

選択肢 (3): (Birdクラスの追加)

a) クラス Bird 継承 Animal { メソッド: speak() { 出力 “鳥はチーチーと鳴きます。” } }
b) クラス Bird 継承 Pet { メソッド: speak() { 出力 “鳥はチーチーと鳴きます。” } }
c) クラス Bird 実装 Animal { メソッド: speak() { 出力 “鳥はチーチーと鳴きます。” } }
d) クラス Bird { メソッド: speak() { 出力 “鳥はチーチーと鳴きます。” } }

（１０）単方向リストの基本的な操作（挿入、削除、検索）

以下の疑似コードは、単方向リストを表現しています。Node はノードを表し、data はノードのデータ、next は次のノードへのポインタです。List はリストを表し、head はリストの先頭ノードへのポインタです。 空欄 (1) と (2) に最も適切なコードを選択肢から選んでください。

クラス Node {
  属性:
    data: 整数
    next: Node
  コンストラクタ(data) {
    この.data = data
    この.next = ヌル
  }
}

クラス List {
  属性:
    head: Node
  コンストラクタ() {
    この.head = ヌル
  }

  メソッド:
    先頭に追加(data):
      新しいノード = 新しい Node(data)
      新しいノード.next = (1)
      この.head = 新しいノード

    削除(data):
      もし (この.head == ヌル):
        戻り値 偽 // リストが空

      もし (この.head.data == data):
        この.head = この.head.next
        戻り値 真

      現在のノード = この.head
      前のノード = ヌル
      繰り返す (現在のノード != ヌル and 現在のノード.data != data):
        前のノード = 現在のノード
        現在のノード = 現在のノード.next

      もし (現在のノード == ヌル):
        戻り値 偽 // データが見つからない

      前のノード.next = (2) // 削除処理
      戻り値 真

    検索(data): // 検索機能は省略
      ...
}

選択肢 (1):

a) ヌル
b) この.head
c) 新しいノード
d) この.head.next

選択肢 (2):

a) ヌル
b) 現在のノード
c) 前のノード
d) 現在のノード.next

（１１）単方向リスト

単方向リストに関する以下の記述のうち、正しいものを全て選んでください。

a. メモリ効率が良い。ノードはデータと次のノードへのポインタのみを持つため、オーバーヘッドが少ない。

b. 任意のノードへのアクセスが高速である。インデックスを用いて直接アクセスできる。

c. ノードの挿入と削除が容易である。特定のノードの前後への挿入・削除は、ポインタの変更のみで済む。

d. リストの走査は一方向のみ可能である。逆方向への走査はできない。

e. ソート済みリストを維持することが容易である。挿入時に適切な位置にノードを挿入することで、ソートを維持できる。

f. メモリの断片化が起こりにくい。連続したメモリ領域を必要としないため。

（１２）双方向リスト

以下の疑似コードは、双方向リストのノードを表すNodeクラスです。空欄(1)と(2)に適切なコードを以下の選択肢から選んでください。

クラス Node {
  属性:
    data: 整数
    prev: Node  // 前のノードへのポインタ
    next: Node  // 次のノードへのポインタ

  コンストラクタ(data) {
    この.data = data
    この.prev = (1)
    この.next = (2)
  }
}

選択肢 (1):

a) この.next
b) ヌル
c) この.prev
d) data

選択肢 (2):

a) この.prev
b) ヌル
c) この.next
d) data

（１３）双方向リストの特定のノードを削除するアルゴリズム

以下の疑似コードは、双方向リストから特定のデータを持つノードを削除する関数です。Nodeクラスは問題文で定義されているものとします(前の問題と同じ)。空欄(1)～(3)に適切なコードを以下の選択肢から選んでください。 削除対象のノードが存在しない場合は、何もせず偽を返します。

関数 削除ノード(リスト, data):
  現在のノード = リスト.head
  繰り返す (現在のノード != ヌル):
    もし (現在のノード.data == data):
      もし (現在のノード == リスト.head):
        リスト.head = 現在のノード.next
        もし (リスト.head != ヌル):
          リスト.head.prev = (1)
      さもなければ:
        現在のノード.prev.next = (2)
        現在のノード.next.prev = (3)
      戻り値 真
    現在のノード = 現在のノード.next
  戻り値 偽

選択肢 (1), (2), (3):

a) ヌル
b) 現在のノード.prev
c) 現在のノード.next
d) リスト.head
e) 現在のノード

（１４）キュースタック操作

以下の疑似コードは、キューとスタックを用いたデータの処理を表しています。 キューqueueとスタックstackは、共に整数値を格納できるものとします。 enqueue(queue, x)はキューqueueに値xを追加し、dequeue(queue)はキューqueueの先頭要素を取り除き、その値を返します。push(stack, x)はスタックstackに値xを追加し、pop(stack)はスタックstackの一番上の要素を取り除き、その値を返します。 空のキューまたはスタックから要素を取り出そうとした場合はエラーとなります。

queue = 空のキュー
stack = 空のスタック

enqueue(queue, 10)
enqueue(queue, 20)
enqueue(queue, 30)

push(stack, dequeue(queue))
push(stack, 40)
push(stack, dequeue(queue))

enqueue(queue, pop(stack))
enqueue(queue, pop(stack))
enqueue(queue, 50)

x = dequeue(queue)
y = dequeue(queue)
z = dequeue(queue)

// x, y, z の値は？

選択肢:

a) x = 10, y = 20, z = 50
b) x = 20, y = 10, z = 50
c) x = 10, y = 40, z = 50
d) x = 20, y = 40, z = 50
e) x = 30, y = 20, z = 40

（１５）2つのベクトルのコサイン類似度を計算するプログラム

以下の疑似言語のプログラムは、2つのベクトル v1 と v2 のコサイン類似度を計算します。 v1 と v2 は、同じ次元数の数値ベクトルで、要素数は n とします。 プログラム実行後の similarity の値を求めてください。

関数 コサイン類似度(v1, v2, n):
  dot_product = 0
  magnitude_v1 = 0
  magnitude_v2 = 0

  // 内積の計算
  i = 0 から n-1 まで繰り返す:
    dot_product = dot_product + v1[i] * v2[i]

  // v1 の大きさの計算
  i = 0 から n-1 まで繰り返す:
    magnitude_v1 = magnitude_v1 + v1[i] * v1[i]
  magnitude_v1 = √magnitude_v1

  // v2 の大きさの計算
  i = 0 から n-1 まで繰り返す:
    magnitude_v2 = magnitude_v2 + v2[i] * v2[i]
  magnitude_v2 = √magnitude_v2

  // コサイン類似度の計算 (0除算対策あり)
  もし (magnitude_v1 * magnitude_v2 == 0):
    similarity = 0
  さもなければ:
    similarity = dot_product / (magnitude_v1 * magnitude_v2)

  戻り値 similarity

v1 = [1, 2, 3]
v2 = [4, 0, 2]
n = 3

similarity = コサイン類似度(v1, v2, n)

（１６）ニュートン法を用いて方程式の解を求めるアルゴリズム

以下の疑似言語プログラムは、ニュートン法を用いて方程式 f(x) = x² – 2 = 0 の解（√2）を求めるものです。 初期値 x₀ = 1.0、許容誤差 ε = 0.01 とします。 f'(x) は f(x) の導関数です。 プログラム実行後、変数 x の値は何になりますか？ また、ループは何度実行されますか？

関数 ニュートン法(f, f_dash, x0, epsilon):
  x = x0
  繰り返す:
    x_new = x - f(x) / f_dash(x)
    もし (abs(x_new - x) < epsilon):
      戻り値 x_new
    x = x_new

関数 f(x):
  戻り値 x*x - 2

関数 f_dash(x):
  戻り値 2*x

x0 = 1.0
epsilon = 0.01
x = ニュートン法(f, f_dash, x0, epsilon)
print x // xの値を出力
print ループ回数 // ループ回数を表示

（１７）ニューラルネットワークの基本構造

以下の説明は、単純な3層ニューラルネットワーク（入力層、隠れ層、出力層）を示しています。 各層の役割について、正しい記述を選択肢から選んでください。

入力層: 3つのノード（x1, x2, x3）を持つ。
隠れ層: 2つのノードを持つ。各ノードは入力層のノードからの重み付き和とバイアスを受け取る。活性化関数はシグモイド関数とする。
出力層: 1つのノードを持つ。隠れ層のノードからの重み付き和とバイアスを受け取る。活性化関数はシグモイド関数とする。

選択肢:

a) 入力層は、入力データを受け取り、特徴量を抽出する。隠れ層は、入力データの特徴量をさらに抽象化し、出力層は最終的な予測結果を出力する。

b) 入力層は、入力データを受け取り、重みとバイアスを調整する。隠れ層は、入力データの特徴量を抽出する。出力層は、最終的な予測結果を出力する。

c) 入力層は、入力データを受け取り、重みとバイアスを調整する。隠れ層は、最終的な予測結果を出力する。出力層は、入力データの特徴量を抽出する。

d) 入力層は、入力データの特徴量を抽出する。隠れ層は、入力データを受け取り、重みとバイアスを調整する。出力層は、最終的な予測結果を出力する。

（１８）シンプルなニューラルネットワークを用いた分類

以下の説明は、単純な2層ニューラルネットワーク（入力層、出力層）を用いて、手書き数字（0～9）の画像を分類する問題を解くためのモデルを示しています。
入力層のニューロン数は784個で、各ニューロンは画像のピクセル1つに対応します。
出力層のニューロン数は10個で、各ニューロンは数字0～9のいずれかに対応します。
活性化関数にはソフトマックス関数を使用します。
このモデルについて、正しい記述を選択肢から選んでください。

選択肢:

a) このモデルは、各ピクセルの値を重み付けして合計し、その結果を直接出力層に渡し、各数字の確率を出力する。

b) このモデルは、入力層から出力層への重み行列を用いて、入力画像の特徴を抽出し、各数字の確率を出力する。

c) このモデルは、入力画像を784次元のベクトルとして表現し、各ピクセルの値をそのまま出力層に入力する。

d) このモデルは、入力層のニューロン数を10個に減らすことで、計算量を削減できる。

（１９）標準偏差の計算

以下のデータセットの標準偏差を計算してください。小数点以下第2位を四捨五入すること。標準偏差は、データの散らばり具合を表す指標であり、以下の手順で計算されます。

1. 平均値の算出: データセットのすべての数値を合計し、データ数で割ることで平均値を求めます。
2. 分散の算出: 各データと平均値との差を二乗し、それらの合計をデータ数で割ることで分散を求めます。
3. 標準偏差の算出: 分散の平方根を求めることで標準偏差を求めます。

データセット: {10, 12, 15, 18, 20}

選択肢:

a) 3.69
b) 4.00
c) 4.58
d) 5.00

（２０）標準偏差がデータ分析において重要な理由

データ分析において、標準偏差が重要な指標である理由として、最も適切なものを以下の選択肢から選んでください。

選択肢:

a) データセットの最大値と最小値の差を直接的に示すため。

b) データセットの平均値からのデータのばらつき具合を定量的に示すため。

c) データセットの個々のデータ値を正確に表現するため。

d) データセットの中央値を正確に計算するため。