Category:
[KNTT] Trắc nghiệm Tin học 7 bài 15 Thuật toán tìm kiếm nhị phân
Tags:
Bộ đề 1
21. Giả sử mảng đã sắp xếp: [1, 3, 5, 7, 9, 11, 13]. Tìm kiếm giá trị 8. Bước nào sau đây là sai trong quá trình tìm kiếm nhị phân?
Theo phân tích phổ biến, sau khi tìm ở [9, 11, 13], phần tử giữa là 11. Do 8 < 11, ta tìm tiếp ở [9]. Phần tử giữa là 9. Do 8 < 9, ta tìm tiếp ở phạm vi trống trước 9. Do đó, 8 không có trong mảng. Lựa chọn 4 mô tả kết quả cuối cùng, không phải là một bước tìm kiếm sai. Tuy nhiên, nếu xét về bước tiếp theo sau khi tìm 11, phạm vi bên trái là [9]. Phần tử giữa là 9. 8 < 9, phạm vi tiếp theo là trống. Do đó, bước 4 là kết luận, không phải là một bước tìm kiếm sai. Tuy nhiên, nếu phân tích kỹ, sau khi so sánh với 7 (phần tử giữa của [1,3,5,7,9,11,13]), ta tìm tiếp ở [9,11,13]. Phần tử giữa là 11. Vì 8 < 11, ta tìm tiếp ở [9]. Phần tử giữa là 9. Vì 8 < 9, ta tìm tiếp ở phạm vi trống trước 9. Kết luận: 8 không có trong mảng. Lựa chọn 4 mô tả kết luận, không phải là một bước sai. Tuy nhiên, nếu xét các bước thực hiện, bước 3 là đúng. Bước 4 là kết quả. Câu hỏi có thể hơi gây nhầm lẫn. Tuy nhiên, nếu xét về một bước sai, thì không có bước nào sai trong các bước 1, 2, 3. Lựa chọn 4 là kết quả cuối cùng. Nếu ta buộc phải chọn một bước sai, thì có thể hiểu là việc kết thúc ngay sau khi tìm 11 và so sánh với 8 là sai nếu vẫn còn khả năng tìm kiếm. Tuy nhiên, theo quy trình chuẩn, bước tiếp theo sau 11 là so sánh với 9. Sau đó là so sánh với phạm vi trống. Do đó, bước 4 là kết quả cuối cùng. Nếu hiểu câu hỏi là bước nào sai, thì 1, 2, 3 là đúng. Vậy 4 là đáp án hợp lý nhất vì nó là kết luận, không phải là một bước tìm kiếm. Tuy nhiên, theo quy trình, phạm vi tìm kiếm tiếp theo sau khi 8 < 11 là [9]. Sau đó, 8 < 9, phạm vi tìm kiếm tiếp theo là trống. Vậy 8 không có trong mảng. Kết luận Lý giải: Phạm vi tìm kiếm tiếp theo là trống rỗng, 8 không có trong mảng.
