← 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)

Cơ bản về tìm kiếm tuyến tính

Việc kiểm tra lần lượt từ đầu mảng các số nguyên để xem có phần tử nào trùng với giá trị chỉ định hay không được gọi là tìm kiếm tuyến tính. Đoạn giả mã dưới đây tìm giá trị target trong mảng data và trả về vị trí (chỉ số) tìm thấy, hoặc -1 nếu không tìm thấy.

○ kiểu số nguyên: search(mảng số nguyên: data, số nguyên: target)
  số nguyên: i
  for (i từ 0 đến (số phần tử của data) - 1, tăng dần 1)
    if (data[i] bằng target) then
      return i
    endif
  endfor
  return -1

Từ khóa

線形探索せんけいたんさくtìm kiếm tuyến tính 添字そえじchỉ số (index) 計算量けいさんりょうđộ phức tạp tính toán

Câu hỏi

1

Khi data = [5, 12, 8, 3, 12, 7] và target = 12, thủ tục này trả về giá trị nào?

Lựa chọn

  1. 1
  2. 2
  3. 4
  4. -1
Xem giải thích

Chỉ số mảng bắt đầu từ 0. data[0]=5 không khớp, nhưng data[1]=12 khớp, nên chỉ số 1 được trả về ngay (không kiểm tra số 12 thứ hai).

2

Khi data = [3, 9, 15] và target = 20, giá trị nào được trả về?

Lựa chọn

  1. 0
  2. 3
  3. -1
  4. Sẽ báo lỗi
Xem giải thích

Vì không có phần tử nào trong mảng khớp với target, vòng lặp kết thúc mà không return, sau đó -1 được trả về.

3

Độ phức tạp thời gian (order) trong trường hợp xấu nhất của thủ tục này là gì?

Lựa chọn

  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n^2)
Xem giải thích

Khi giá trị target ở cuối mảng hoặc không tồn tại, mọi phần tử đều phải được kiểm tra một lần, nên độ phức tạp là O(n).

Đă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