Bài 2. Tìm kiếm nhị phân trang 36 SBT Tin Học lớp 7 – Cánh Diều, mời các em tham khảo cùng Bumbii.
Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính. Bài 2. Tìm kiếm nhị phân.
Câu F7
Trong các câu sau, câu nào đúng?
1) Tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự tăng dần.
2) Tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự giảm dần.
3) Tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự.
4) Tìm kiếm nhị phân chỉ áp dụng được cho dãy bất kì.
Đáp án: phương án 3.
Tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự.
Câu F8
Trang 81 sách giáo khoa trình bày quá trình chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự không giảm. Để có thể áp dụng cho dãy số đã sắp thứ tự không tăng, cần sửa một vài chi tiết nhỏ. Em hãy nói rõ cần sửa đổi những chi tiết nào.
Đáp án:
Việc xác định phạm vi tìm kiếm ở bước tiếp theo cần sửa lại. Vì dãy số đã sắp thứ tự không tăng nên sẽ cần đảo ngược dấu lớn hơn thành dấu nhỏ hơn khi so sánh với x để chọn nửa dãy là phạm vi tìm kiếm tiếp theo.
Câu F9
Biết rằng dãy số đã sắp xếp thứ tự. Có thể áp dụng tìm kiếm nhị phân hay không cho bài toán:
1) Tìm tất cả các số bằng x có trong dãy.
2) Tìm số đầu tiên bằng x.
3) Tìm số cuối cùng bằng x.
Đáp án:
Nếu tìm thấy một số = x thì cũng không có đáp án cho cả ba trường hợp 1, 2, 3.
1) Không. Vì chỉ thấy một kết quả, không thấy hết “tất cả” các số bằng x có trong dãy.
2) Không. Vì kết quả tìm kiếm nhị phân có thể là bất kì số nào trong “tất cả” các số bằng x có trong dãy.
3) Không. Vì kết quả tìm kiếm nhị phân có thể là bất kì số nào trong “tất cả” các số bằng x có trong dãy.
Câu F10
Hãy chọn những câu đúng và nói rõ vì sao không chọn những câu còn lại:
1) Tìm kiếm nhị phân chia dãy làm hai nửa dài xấp xỉ bằng nhau và chỉ cần tìm kiếm trong một nửa dãy.
2) Tìm kiếm nhị phân chia dãy làm hai nửa dài đúng bằng nhau và chỉ cần tìm kiếm trong một nửa dãy.
3) Tìm kiếm nhị phân lặp lại việc chia đôi dãy cho đến khi dãy chỉ còn một phần tử.
4) Tìm kiếm nhị phân lặp lại việc chia đôi dãy cho đến khi tìm thấy.
5) Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự.
6) Tìm kiếm nhị phân áp dụng chiến lược “chia để trị”.
Đáp án:
1) Đúng.
2) Sai khi độ dài dãy là số lẻ.
3) Đúng.
4) Sai vì khi dãy không có số bằng x thì thuật toán không dừng được; khi dãy chỉ còn một phần tử thì không chia đôi nữa mà kiểm tra trực tiếp.
5) Đúng
6) Đúng.
Xem thêm các bài khác tại Giải sách bài tập tin học lớp 7 – NXB Cánh Diều
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
Không bao giờ từ bỏ hy vọng. Cố gắng mỗi ngày.