Title Bài tập luyện tập Bài 19 - Bài toán tìm kiếm.pdf ✅

D. return -1 Đáp án: A Giải thích: for khai báo i để duyệt. 8. Bước nào cần trong tìm kiếm nhị phân? (Remember) A. Tính mid = (left + right) // 2 B. Duyệt từ đầu dãy C. Xóa phần tử D. In toàn bộ dãy Đáp án: A Giải thích: Tính mid là bước chính. 9. Tại sao tìm kiếm nhị phân cần dãy sắp xếp? (Understand) A. Để xác định hướng thu hẹp phạm vi B. Để duyệt toàn bộ dãy C. Để tăng tốc độ nhập liệu D. Để xóa dữ liệu Đáp án: A Giải thích: Sắp xếp giúp so sánh với mid. 10. Để tìm K = 9 trong A = [1, 4, 7, 8, 3, 9, 10], tuần tự trả về gì? (Apply) A. 5 B. 6 C. -1 D. 0 Đáp án: A Giải thích: Duyệt đến A[5] = 9, trả về 5. 11. Bước nào cần trong LinearSearch? (Remember) A. return -1 nếu không tìm thấy B. Sắp xếp dãy trước C. Thu hẹp phạm vi D. Tính trung bình Đáp án: A Giải thích: Trả về -1 khi không tìm thấy. 12. Tìm kiếm từ đầu khác từ cuối ở điểm nào? (Analyze) A. Từ đầu duyệt 0 -> n-1, từ cuối n-1 -> 0 B. Từ cuối nhanh hơn từ đầu C. Từ đầu dùng 2 chỉ số D. Không có sự khác biệt Đáp án: A Giải thích: Thứ tự duyệt khác, kết quả giống nhau. 13. Lệnh nào khai báo biến trong BinarySearch? (Remember) A. left = 0; right = len(A) - 1 B. if A[mid] == K C. return mid D. print(A) Đáp án: A Giải thích: Khai báo phạm vi tìm kiếm. 14. Tại sao nhị phân nhanh hơn tuần tự? (Understand) A. Thu hẹp phạm vi, ít bước hơn B. Duyệt toàn bộ dãy C. Không cần sắp xếp D. Dùng 1 chỉ số Đáp án: A Giải thích: Thu hẹp giảm số phần tử duyệt. 15. Để tìm K = 9 trong A = [1, 3, 4, 7, 8, 9, 10], nhị phân trả về gì? (Apply) A. 5 B. 6

a) Tìm ảnh là tìm kiếm. b) Quan trọng vì xác định dữ liệu. c) Ảnh (Internet) khác học sinh (danh sách). d) Cần duyệt để tìm tệp. a) Tuần tự duyệt từng phần tử. b) Duyệt hết nên tìm được. c) Nhị phân nhanh hơn khi sắp xếp. d) Có thể sửa code để tìm tất cả. Phần 2: Thực hành (PR) - 3 điểm 1. Đánh giá miền dữ liệu: Đánh giá tầm quan trọng của việc xác định miền dữ liệu trong bài toán tìm kiếm, nêu ít nhất 2 lợi ích cụ thể. (1 điểm, Evaluate) Đáp án mẫu: Lợi ích: Xác định phạm vi tìm kiếm (ví dụ: Internet vs danh sách học sinh); chọn thuật toán phù hợp (tuần tự vs nhị phân). Đánh giá: Rất quan trọng để tối ưu hiệu quả tìm kiếm. 2. Sáng tạo tìm tất cả: Viết đoạn code Python tìm tất cả chỉ số của K = 9 trong A = [1, 9, 7, 9, 3], giải thích ngắn gọn. (1 điểm, Create) Đáp án mẫu: Code: Giải thích: Dùng list comprehension để tìm tất cả chỉ số i thỏa mãn A[i] = K. 3. Áp dụng nhị phân: Mô tả cách tìm K = 9 trong A = [1, 3, 4, 7, 8, 9, 10] bằng thuật toán nhị phân, nêu ít nhất 3 bước cụ thể. (1 điểm, Apply) Đáp án mẫu: Giải thích: Câu 2: Một học sinh chạy LinearSearch(A, 9) với A = [1, 9, 7]: a) LinearSearch duyệt lần lượt từng phần tử (Đúng, Remember). b) Nếu K tồn tại, tuần tự luôn tìm được (Đúng, Understand). c) BinarySearch nhanh hơn LinearSearch (Đúng, Remember). d) Có thể tìm tất cả chỉ số K = 9 (Đúng, Create). Đáp án: a) Đ; b) Đ; c) Đ; d) Đ Giải thích: python def find_all(A, K): return [i for i in range(len(A)) if A[i] == K] A = [1, 9, 7, 9, 3] print(find_all(A, 9)) # Kết quả: [1, 3] Thu gọn Bọc lại Sao chép