Lý thuyết Tin học 7 Bài 2 (Cánh diều 2024): Tìm kiếm nhị phân

Nguyễn Mạnh Tài Ngày: 10-01-2024 Lớp 7

2.3 K

Với tóm tắt lý thuyết Tin học lớp 7 Bài 2: Tìm kiếm nhị phân sách Cánh diều hay, chi tiết cùng với bài tập trắc nghiệm chọn lọc có đáp án giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt môn Tin học7.

Tin học lớp 7 Bài 2: Tìm kiếm nhị phân

A. Lý thuyết Tin học 7 Bài 2: Tìm kiếm nhị phân

1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

Ý tưởng chia đôi dần để tìm một số trong một dãy số được minh họa bởi ví dụ sau đây:

Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã xếp thứ tự không giảm 6, 12, 18, 42, 44, 55, 67, 94. Bảng dưới minh họa từng bước chia đôi dần để tìm kiếm.

Lý thuyết Tin Học 7 Bài 2: Tìm kiếm nhị phân - Kết nối tri thức (ảnh 1)

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy: Vì x > a₄ nên nửa đầu dãy chắc chắn không chứa x = 44, sau đó cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a₅ đến a₈.

Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₅ đến a₈. Lấy a₆ là số có vị trí giữa dãy; Vì x < a₆ nên nửa sau dãy chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa đầu của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con chỉ còn một từ a₅.

Phạm vi tìm kiếm chỉ còn một số. Kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ năm.

2. Thuật toán tìm kiếm nhị phân

- Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp thứ tự.

- Ý tưởng: Chia đôi dần để giảm nhanh phạm vi tìm kiếm.

Lý thuyết Tin Học 7 Bài 2: Tìm kiếm nhị phân - Kết nối tri thức (ảnh 1)

Hình 2.1: Một mô tả của thuật toán tìm kiếm nhị phân

Khi bắt đầu thuật toán, phạm vi tìm kiếm là dãy đã cho ban đầu. Lấy phần tử đứng giữa dãy là a_m để so sánh với x. Nếu a_m = x thì kết thúc. Trái lại, sẽ có hai trường hợp:

- Nếu a_m < x thì chắc chắn không có x trong nửa đầu của dãy.

- Nếu x < a_m thì chắc chắn không có x trong nửa sau của dãy.

Lặp lại theo cách như thế cho đến khi hoặc tìm thấy hoặc độ dài dãy phạm vi tìm kiếm là bằng 0.

3. Phương pháp “chia để trị” với bài toán tìm kiếm

- Thuật toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó, cho đến đi nhận được kết quả.

B. Bài tập trắc nghiệm Tin học 7 Bài 2: Tìm kiếm nhị phân

Câu 1. Điều kiện để áp dụng thuật toán nhị phân là:

A. Không có điều kiện.

B. Dãy đã được sắp xếp tăng dần.

C. Dãy đã được sắp xếp giảm dần.

D. Cả C và B

Hướng dẫn giải

Đáp án đúng là: D

Điều kiện để áp dụng thuật toán nhị phân là: Dãy đã được sắp xếp tăng dần hoặc giảm dần.

Câu 2. Điều kiện lặp trong bài toán tìm kiếm nhị phân là:

A. Kết quả= tìm thấy.

B. Phạm vi tìm kiếm dài hơn 1 và kết quả=chưa tìm thấy.

C. Xét hết dãy số

D. Cả A và C đều đúng

Hướng dẫn giải

Đáp án đúng là: B

Điều kiện lặp trong bài toán tìm kiếm nhị phân là: Phạm vi tìm kiếm dài hơn 1 và kết quả=chưa tìm thấy.

Câu 3. Trong thuật toán tìm kiếm nhị phân, việc tìm kiếm sẽ dừng khi:

A. Đã tìm kiếm hết dãy.

B.Đã tìm thấy kết quả mong muốn hoặc phạm vi tìm kiếm chỉ còn 1 số.

C. Đã tìm hết nửa dãy đầu.

D. Đã tìm hết nửa dãy sau.

Hướng dẫn giải

Đáp án đúng là: B

Trong thuật toán tìm kiếm nhị phân, việc tìm kiếm sẽ dừng khi: Đã tìm thấy kết quả mong muốn hoặc phạm vi tìm kiếm chỉ còn 1 số.

Câu 4. Khẳng định nào sau đây là đúng khi nói về thuật toán tìm kiếm nhị phân?

A. Dãy không có thứ tự ta áp dụng thuật toán tìm kiếm nhị phân để: Không bỏ sót cho đến khi tìm thấy hoặc tìm hết dãy và không tìm thấy.

B. Điều kiện lặp trong bài toán tìm kiếm nhị phân là kết quả= tìm thấy.

C.Việc tìm kiếm nhị phân tìm đến phần tử cuối dãy khi tìm thấy kết quả mong muốn.

D. Chỉ có thể áp dụng thuật toán tìm kiếm nhị phân cho bài toán đã được sắp xếp.

Hướng dẫn giải

Đáp án đúng là: D

Chỉ có thể áp dụng thuật toán tìm kiếm nhị phân cho bài toán đã được sắp xếp.

Câu 5. Cho dãy số 2,4,6,8,9. Bài toán “Tìm vị trí của số 8 trong dãy”, có phạm vi tìm kiếm là:

A. Nửa dãy đầu.

B. Nửa dãy sau.

C. Tất cả dãy.

D. Không có phạm vi.

Hướng dẫn giải

Đáp án đúng là: B

Vì phần tử giữa là 6, mà 8>6 nên phạm vi tìm kiếm là ở nửa dãy sau.

Câu 6. Khẳng định nào sau đây là đúng khi nói về thuật toán tìm kiếm nhị phân?

A. Thuật toán tìm kiếm nhị phân áp dụng được cho dãy đã sắp xếp thứ tự và dãy không sắp xếp thứ tự .

B. Thuật toán tìm kiếm nhị phân áp dụng được cho mọi bài toán.

C. Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp xếp thứ tự.

D. Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy không sắp xếp thứ tự.

Hướng dẫn giải

Đáp án đúng là: C

Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp xếp thứ tự.

Câu 7. Tìm kiếm nhị phân là:

A. Tìm kiếm lần lượt từ đầu tới cuối dãy.

B. Tìm kiếm ở đầu dãy.

C. Tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại.

D. Tìm kiếm ở cuối dãy.

Hướng dẫn giải

Đáp án đúng là: C

Tìm kiếm nhị phân là:Tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại.

Câu 8. Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì:

A. Chỉ tìm kiếm trong nửa dãy còn lại.

B. Dãy đã được sắp xếp.

C.Cả A và B đều đúng.

D.Cả A và B đều sai.

Hướng dẫn giải

Đáp án đúng là: C

Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì: Dãy đã được sắp xếp và tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại.

Câu 9. Bài toán nào sau đây áp dụng được thuật toán tìm kiếm nhị phân:

A. Cho dãy 1,3,5,6. Tìm vị trí của số 5 trong dãy.

B. Cho dãy 1,5,3,6. Tìm vị trí của số 5 trong dãy.

C. Cho dãy 6,5,4,3,2,1. Hãy tìm xem số 3 có trong dãy này không.

D.Cả A và C

Hướng dẫn giải

Đáp án đúng là: D

Vì dãy đã được sắp xếp mới có thể áp dụng thuật toán tìm kiếm nhị phân.

Câu 10. Để tìm một số trong dãy đã được sắp xếp tăng dần, thuật toán tìm kiếm nhanh nhất là:

A. Tìm kiếm tuần tự.

B. Tìm kiếm nhị phân.

C. Cả A và B

D. Không có thuật toán nào.

Hướng dẫn giải

Đáp án đúng là: B

Để tìm một số trong dãy đã được sắp xếp tăng dần, thuật toán tìm kiếm nhanh nhất là:

Tìm kiếm nhị phân.

Câu 11. Cho dãy số 2,4,6,8,9. Bài toán “Tìm vị trí của số 8 trong dãy”, cho kết quả là:

A. 1

B. 2

C. 3

D. 4

Hướng dẫn giải

Đáp án đúng là: D

Vì số 8 đứng ở vị trí thứ 4 trong dãy

Câu 12. Cho dãy số 0,1,2,4,6,8,9. Bài toán “Tìm vị trí của số 8 trong dãy” có phần tử giữa là:

A. 4

B. 2

C. 6

D. 8

Hướng dẫn giải

Đáp án đúng là: A

Vì phần tử 4 đứng ở vị trí thứ 4 trong dãy có 7 phần tử.

Câu 13. Cho dãy số 0,1,2,4,6,8,9. Bài toán “Tìm số x=4 trong dãy” có số lần lặp là:

A. 0

B. 1

C. 2

D. 3

Hướng dẫn giải

Đáp án đúng là: B

Vì x=4 là phần tử giữa của phạm vi tìm kiếm.

Câu 14. Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa đầu của dãy:

A. Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm.

B. Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.

C. Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.

D. Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.

Hướng dẫn giải

Đáp án đúng là: B

Đối với dãy đã sắp xếp tăng dần, khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm thì phạm vi tìm kiếm nằm ở nửa đầu của dãy.

Câu 15. Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa sau của dãy:

A. Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm.

B. Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.

C. Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.

D. Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.

Hướng dẫn giải

Đáp án đúng là: A

Đối với dãy đã sắp xếp tăng dần, khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm thì phạm vi tìm kiếm nằm ở nửa sau của dãy.

Xem thêm các bài tóm tắt lý thuyết Tin học 7 Cánh diều hay, chi tiết khác:

Lý thuyết Tin học 7 Bài 1: Tìm kiếm tuần tự

Lý thuyết Tin học 7 Bài 2: Tìm kiếm nhị phân

Lý thuyết Tin học 7 Bài 3: Sắp xếp chọn

Lý thuyết Tin học 7 Bài 4: Sắp xếp nổi bọt

Lý thuyết Tin học 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp