← Level 3 · Đọc hiểu & Tình huống FE
Thuật toán & giả mã Tình huống đọc hiểu Độ khó: Nâng cao Thời gian dự kiến: Khoảng 5 phút Cấp độ phù hợp: FE Level 3 (môn B)

Truy vết thuật toán sắp xếp chọn (selection sort)

Liên tục chọn giá trị nhỏ nhất từ phần chưa sắp xếp rồi hoán đổi vào đúng vị trí được gọi là sắp xếp chọn (selection sort). Đoạn giả mã dưới đây sắp xếp mảng data theo thứ tự tăng dần.

○ mảng số nguyên: selectionSort(mảng số nguyên: data)
  số nguyên: i, j, minIndex, temp
  for (i từ 0 đến (số phần tử của data) - 2, tăng dần 1)
    minIndex ← i
    for (j từ i + 1 đến (số phần tử của data) - 1, tăng dần 1)
      if (data[j] nhỏ hơn data[minIndex]) then
        minIndex ← j
      endif
    endfor
    temp ← data[i]
    data[i] ← data[minIndex]
    data[minIndex] ← temp
  endfor
  return data

Giả sử mảng data = [4, 1, 3, 2].

Từ khóa

選択ソートせんたくそーとsắp xếp chọn 未整列部分みせいれつぶぶんphần chưa sắp xếp

Câu hỏi

1

Trạng thái của data sau khi vòng lặp ngoài đầu tiên (i=0) kết thúc là gì?

Lựa chọn

  1. [1, 4, 3, 2]
  2. [1, 2, 3, 4]
  3. [4, 1, 3, 2]
  4. [2, 1, 3, 4]
Xem giải thích

Giá trị nhỏ nhất trong data[1..3]=[1,3,2] là 1 tại j=1, nên data[0]=4 và data[1]=1 hoán đổi, cho ra [1,4,3,2].

2

Vòng lặp for ngoài (vòng lặp i) thực hiện bao nhiêu lần, với data có 4 phần tử?

Lựa chọn

  1. 2 lần
  2. 3 lần
  3. 4 lần
  4. 5 lần
Xem giải thích

i chạy từ 0 đến (số phần tử - 2) = 2, nên thực hiện 3 lần (i=0,1,2).

3

Đặc điểm nào mô tả đúng nhất về số lần hoán đổi của selection sort so với bubble sort?

Lựa chọn

  1. Selection sort luôn thực hiện đúng n-1 lần hoán đổi bất kể dữ liệu, còn số lần hoán đổi của bubble sort thay đổi tùy mức độ chưa sắp xếp
  2. Selection sort luôn thực hiện O(n^2) lần hoán đổi kể cả khi dữ liệu đã sắp xếp sẵn
  3. Bubble sort luôn hoán đổi ít lần hơn selection sort
  4. Selection sort không có bước hoán đổi nào
Xem giải thích

Selection sort thực hiện đúng một lần hoán đổi mỗi vòng lặp ngoài, cố định là n-1, còn bubble sort thay đổi số lần hoán đổi tùy theo thứ tự các phần tử liền kề.

Đăng nhập để lưu kết quả

Bạn có thể đọc miễn phí nội dung, câu hỏi và giải thích. Hãy đăng nhập để lưu kết quả và đưa vào hàng ôn tập cùng phân tích điểm yếu.

Đăng nhập để lưu