Đề bài
Cho đoạn mã giả sau:
| 1 | def TimKiem $\left( {{\rm{A}},{\rm{K}}} \right):$ |
|---|---|
| 2 | Xuất phát phạm vi tìm kiếm là dãy ban đầu |
| 3 | Lặp khi vẫn còn phạm vi tìm kiếm |
| 4 | Xác định phần tử $A\left[ {{\rm{\;m}}} \right]$ ở giữa phạm vi tìm kiếm |
| 5 | if ${\rm{K}} = = {\rm{A}}\left[ {\rm{m}} \right]:$ |
| 6 | Thông báo tìm thấy K ở vị trí m và kết thúc |
| 7 | elif $K < A\left[ m \right]$ |
| 8 | Phạm vi tìm kiếm nằm ở nưa trái của dãy |
| 9 | else: |
| 10 | Phạm vi tìm kiếm nằm ơ nưa phải của dãy |
Một số bạn học sinh đã có các nhận xét về thuật toán trên như sau:
Trong mỗi ý a), b), c), d) , thí sinh chọn đúng hoặc sai.
Lời giải chi tiết
-
Đây là thuật toán tìm kiếm nhị phân.
Giải thích: Thuật toán tìm kiếm nhị phân hoạt động trên dữ liệu đã sắp xếp, sử dụng phương pháp chia đôi để tìm kiếm phần tử cần tìm. Đoạn mã giả cho thấy rằng nó chia phạm vi tìm kiếm làm đôi mỗi lần, điều này là đặc trưng của tìm kiếm nhị phân. Do đó, mệnh đề này đúng.
-
Thuật toán thực hiện duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K.
Giải thích: "Duyệt lần lượt các phần tử" là đặc trưng của tìm kiếm tuyến tính (linear search), trái ngược với tìm kiếm nhị phân. Thuật toán không duyệt qua từng phần tử một mà thay vào đó là chia đôi vùng tìm kiếm mỗi lần. Do đó, mệnh đề này sai.
-
Để có được hàm trong Python từ đoạn mã giả trên, cần chuyển các dòng lệnh 2,3,4,6,8 và 10 sang ngôn ngữ Python.
Giải thích: Để chuyển đoạn mã giả sang Python, ta cần chuyển tất cả các lệnh trong đoạn mã giả thành lệnh Python, không chỉ riêng các dòng 2, 3, 4, 6, 8, và 10. Các lệnh ở các dòng khác cũng cần chuyển đổi để hoàn thiện chương trình. Do đó, mệnh đề này sai.
-
Với bộ dữ liệu A=[2,3,5,7,9,11],K=9, thuật toán sẽ kết thúc sau 2 vòng lặp.
- Vòng 1: Khoảng giữa của dãy \(A\) là \(5\), nên bỏ nửa trái \([2,3,5]\).
- Vòng 2: Khoảng giữa của dãy \([7,9,11]\) là \(9\), trùng với \(K\).
Như vậy, thuật toán kết thúc sau 2 lần lặp. Do đó, mệnh đề này đúng.
Chú ý khi giải
- Nắm vững khái niệm về các thuật toán tìm kiếm nhị phân và tuyến tính để có thể phân biệt được chúng dựa trên cách thức hoạt động.
- Hiểu rõ từng bước trong mã giả và cách triển khai chúng bằng các ngôn ngữ lập trình cụ thể, ví dụ Python.
- Khi kiểm tra một thuật toán cụ thể, nên thử với các ví dụ cụ thể để hình dung rõ hơn về các bước thực hiện.
- Tìm kiếm nhị phân yêu cầu mảng đầu vào phải được sắp xếp trước.