問題プレビューID: e0025887基本情報技術者試験 2023年(令和5年度)公開問題 科目B

問 3
基本情報技術者試験 2023年(令和5年度)公開問題 科目B

次の記述中の [ ] に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。

次の手続 sort は,大域の整数型の配列 data の,引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで,first < last とする。手続 sort を sort(1, 5) として呼び出すと,/*** α ***/ の行を最初に実行したときの出力は “[ ]” となる。

〔プログラム〕

大域: 整数型の配列: data ← {2, 1, 3, 5, 4}

○sort(整数型: first, 整数型: last)
  整数型: pivot, i, j
  pivot ← data[(first + last) ÷ 2 の商]
  i ← first
  j ← last

  while (true)
    while (data[i] < pivot)
      i ← i + 1
    endwhile
    while (pivot < data[j])
      j ← j - 1
    endwhile
    if (i ≧ j)
      繰返し処理を終了する
    endif
    data[i] と data[j] の値を入れ替える
    i ← i + 1
    j ← j - 1
  endwhile
  data の全要素の値を要素番号の順に空白区切りで出力する  /*** α ***/
  if (first < i - 1)
    sort(first, i - 1)
  endif
  if (j + 1 < last)
    sort(j + 1, last)
  endif
解説

正解は「エ」です。 クイックソートの最初の分割プロセスを丁寧にトレースします。

初期状態:data = {2, 1, 3, 5, 4}, first = 1, last = 5

  • pivot = data[(1 + 5) ÷ 2 の商] = data[3] = 3
  • i ← 1, j ← 5 と設定。
  1. 最初の while(true) ループ:
    • while(data[i] < pivot): data[1]=2 < 3 (進む), data[2]=1 < 3 (進む), data[3]=3 < 3 (停止)。結果、i = 3。
    • while(pivot < data[j]): 3 < data[5]=4 (戻る), 3 < data[4]=5 (戻る), 3 < data[3]=3 (停止)。結果、j = 3。
    • if (i >= j): 3 >= 3 が成立するため、繰返し処理を終了する。
  2. /*** α ***/ の行を実行:
    • この時点で値の入れ替え(data[i] と data[j] の交換)は一度も行われていません。
    • したがって、初期状態と同じ "2 1 3 5 4" が出力されます。

関連問題

本文が同じ・似ている問題を表示しています