Trắc nghiệm tin học 7 cánh diều CĐF Bài 2: Tìm kiếm nhị phân

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

1. NHẬN BIẾT (15 câu)

Câu 1: Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa sau của dãy:

A. Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm.

B. Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.

C. Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.

D. Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.

Câu 2: Ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn?

A. Dễ thực hiện và nhanh cho ra kết quả.

B. Cho kết quả chính xác hơn.

C. Cho kết quả cụ thể hơn.

D. Cho kết quả khái quát hơn.

Câu 3: Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa đầu của dãy:

A. Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm.

B. Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.

C. Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.

D. Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.

Câu 4: Khi bắt đầu thuật toán, phạm vi tìm kiếm là gì?

A. Dãy đã được tìm kiếm.

B. Dãy đã cho ban đầu đã được sắp xếp.

C. Dãy đã cho ban đầu chưa được sắp xếp.

D. Dãy số bình thường.

Câu 5: Điều kiện lặp của thuật toán tìm kiếm nhị phân là gì?

A. Chưa tìm thấy phần tử cần tìm.

B. Chưa hết danh sách.

C. Chưa tìm thấy phần tử cần tìm hoặc chưa hết danh sách.

D. Chưa tìm thấy phần tử cần tìm và chưa hết danh sách.

Câu 6: Điều kiện lặp trong bài toán tìm kiếm nhị phân là:

A. Kết quả tìm thấy.

B. Phạm vi tìm kiếm dài hơn 1 và kết quả chưa tìm thấy.

C. Xét hết dãy số.

D. Cả A và C đều đúng.

Câu 7: Thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm được gọi là gì?

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

B. Thuật toán tìm kiếm tuần tự.

C. Thuật toán liệt kê.

D. Các đáp án trên đều sai.

Câu 8: Để tìm một số trong dãy đã được sắp xếp tăng dần, thuật toán tìm kiếm nhanh nhất là:

A. Tìm kiếm tuần tự.

B. Tìm kiếm nhị phân.

C. Cả A và B.

D. Không có thuật toán nào

Câu 9: Tìm kiếm nhị phân là gì?

A. Tìm kiếm lần lượt từ đầu tới cuối dãy

B. Tìm kiếm ở đầu dãy

C. Tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phân tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại

D. Tìm kiếm ở cuối dãy

Câu 10: Thuật toán tìm kiếm nhị phân chỉ áp dụng cho dãy số như thế nào?

A. Dãy số đã sắp xếp thứ tự.

B. Dãy số chưa sắp xếp thứ tự.

C. Dãy số đã tìm kiếm.

D. Dãy số đã so sánh.

Câu 11:Tư tưởng của thuật toán tìm kiếm nhị phân là gì?

A. Tìm kiếm dựa vào cây tìm kiếm.

B. Tìm kiếm từ đầu đến cuối dãy.

C. Tại mỗi bước tiến hành so sánh X với phần tử giữa của dãy. Dựa vào bước so sánh này quyết định tìm kiếm ở nửa đầu hay ở nửa sau của danh sách.

D. So sánh X lần lượt với các phần tử a1, a2, …, an.

Câu 12: Trong thuật toán tìm kiếm nhị phân thì vùng tìm kiếm lúc ban đầu là gì?

A. Nửa đầu danh sách.

B. Nửa đầu danh sách.

C. Toàn bộ danh sách.

D. Đáp án khác.

Câu 13: Thuật toán tìm kiếm nhị phân thực hiện trên danh sách nào?

A. Đã được hoán đổi.

B. Đã được sắp xếp.

C. Đã được chỉnh sửa.

D. Cả A, B và C.

Câu 14: Thuật toán tìm kiếm nhị phân là gì?

A. Thực hiện tìm kiếm trên danh sách đã sắp xếp, bắt đầu từ vị trí ở giữa danh sách

B. Thực hiện tìm kiếm trên danh sách đã sắp xếp, bắt đầu từ vị trí ở đầu danh sách

C. Thực hiện tìm kiếm trên danh sách đã sắp xếp, bắt đầu từ vị trí ở cuối danh sách

D. Thực hiện tìm kiếm trên danh sách không sắp xếp, bắt đầu từ vị trí ở giữa danh sách

Câu 15: Sử dụng thuật toán tìm kiếm nhị phân sẽ phù hợp trong trường hợp nào dưới đây?

A. Tìm một số trong một danh sách.

B. Tìm một từ tiếng anh trong quyển từ điển.

C. Tìm tên một bài học trong quyển sách.

D. Tìm tên một nước trong danh sách.

2. THÔNG HIỂU (10 câu)

Câu 1: Trong các phát biểu sau, phát biểu nào sai?

A. 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.

B. 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.

C. 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ử.

D. Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự.

Câu 2: Bài toán nào sau đây áp dụng được thuật toán tìm kiếm nhị phân:

A. Cho dãy 1, 3, 5, 6. Tìm vị trí của số 5 trong dãy.

B. Cho dãy 1, 5, 3, 6. Tìm vị trí của số 5 trong dãy.

C. Cho dãy 6, 5, 4, 3, 2, 1. Hãy tìm xem số 3 có trong dãy này không.

D. Cả A và C.

Câu 3: Trong các câu sau, câu nào đúng?

A. Tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp xếp thứ tự tăng dần.

B. Tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp xếp thứ tự giảm dần.

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

D. Tìm kiếm nhị phân áp dụng được cho dãy bất kì.

Câu 4: Nhận định nào sau đây đúng nhất về thuật toán tìm kiếm nhị phân?

A. Chỉ áp dụng tìm kiếm nhị phân với dãy số tăng dần.

B. Có thể áp dụng tìm kiếm nhị phân với bất kì dãy số nào.

C. Không phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân. Vì tìm kiếm nhị phân chỉ áp dụng với dãy số đã được sắp xếp tăng dần hoặc giảm dần.

D. Chỉ áp dụng tìm kiếm nhị phân với dãy số giảm dần.

Câu 5: Biết rằng dãy số đã sắp thứ tự. Có thể áp dụng tìm kiếm nhị phân cho bài toán nào?

A. Tìm tất cả các số bằng x có trong dãy.

B. Tìm số đầu tiên bằng x.

C. Tìm số cuối cùng bằng x.

D. Tìm số bằng x trong dãy.

Câu 6: Phát biểu đúng nhất về “Thuật toán tìm kiếm nhị phân” (tìm x trong dãy số đã được sắp thứ tự không giảm)?

A. Là thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi để giảm nhanh phạm vi tìm kiếm.

B. Là thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia ba phần để giảm nhanh phạm vi tìm kiếm.

C. Là thuật toán tìm kiếm x trong dãy với ý tưởng chia đôi để giảm nhanh phạm vi tìm kiếm.

D. Là thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi để tăng nhanh phạm vi tìm kiếm.

Câu 7: Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì sao?

A. Chỉ tìm kiếm trong nửa dãy còn lại

B. Dãy đã được sắp xếp

C. Cả A và B đều đúng

D. Cả A và B đều sai

Câu 8: Tìm kiếm nhị phân và tìm kiếm tuần tự thì thuật toán nào nhanh hơn?

A. Tìm kiếm nhị phân

B. Tìm kiếm tuần tự

C. Cả 2 thuật toán đều nhanh như nhau

D. Không thuật toán nào nhanh

Câu 9: Thuật toán tìm kiếm nhị phân được sử dụng khi nào?

A. Chỉ đúng cho dãy đã sắp xếp tăng dần

B. Chỉ dùng cho dãy đã sắp xếp tăng hoặc giảm dần

C. Chỉ dùng cho dãy đã sắp xếp giảm dần

D. Chỉ dùng cho dãy chưa sắp xếp

Câu 10: Trong thuật toán tìm kiếm nhị phân, việc tìm kiếm sẽ dừng khi nào?

A. Đã tìm kiếm hết dãy

B. Đã tìm thấy kết quả mong muốn hoặc phạm vi tìm kiếm chỉ còn 1 số

C. Đã tìm hết nửa dãy đầu

D. Đã tìm hết nửa dãy sau

3. VẬN DỤNG (12 câu)

Câu 1: Lấy phần tử đứng giữa dãy để so sánh với x, nếu phần tử đó chính là x thì kết luận gì?

A. Chưa tìm thấy x và tiếp tục thuật toán.

B. Chưa tìm thấy x và kết thúc thuật toán.

C. Đã tìm thấy x và kết thúc thuật toán.

D. Đã tìm thấy x và tiếp tục thuật toán.

Câu 2: Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy Thailand trong danh sách tên các nước sau:

Brunei, Campodia, Laos, Myanmar, Singpore, Thailand, Vietnam

A. 1

B. 2

C. 3

D. 4

Câu 3: Cho dãy số 0, 1, 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy” có phần tử giữa là:

A. 4

B. 2

C. 6

D. 8

Câu 4: Cho dãy số 0, 1, 2, 4, 6, 8, 9. Bài toán “Tìm số x = 4 trong dãy” có số lần lặp là:

A. 0

B. 1

C. 2

D. 3

Câu 5: Cho dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy”, có phạm vi tìm kiếm là:

A. Nửa dãy đầu.

B. Nửa dãy sau.

C. Tất cả dãy.

D. Không có phạm vi.

Câu 6: Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy sắp xếp diễn biến từng bước tìm kiếm nhị phần để tìm kiếm x = 60 trong dãy trên.

Tìm x = 60:

1. Kết thúc thuật toán: Không tìm thấy x có trong dãy.

2. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x < a7 nên nửa sau dãy chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con một phần tử a7.

3. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy. Vì x > A6 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A7 đến A8.

4. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa dãy. Vì x > A4 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A5 đến A8.

A. 2 – 1 – 3 – 4.

B. 1 – 2 – 3 – 4.

C. 4 – 3 – 2 – 1.

D. 3 – 2 – 1 – 4.

Câu 7: Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu bước để thông báo không tìm thấy số 10 trong danh sách [2, 5, 8, 11, 14, 17] ?

A. 2                       

B. 3                       

C. 4                       

D. 5

Câu 8: Thực hiện thuật toán tìm kiếm nhị phân để tìm số 10 trong danh sách [2, 4 ,6, 8, 10, 12]. Đầu ra của thuật toán là?

A. Thông báo “Không tìm thấy”.

B. Thông báo “Tìm thấy”.

C. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 5 của danh sách.

D. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 6 của danh sách.

Câu 9: Cho dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy”, cho kết quả là:

A. 1

B. 2

C. 3

D. 4

Câu 10: Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy “Mai” trong danh sách [Hoa", "Lan”, ”Ly”, ”Mai”, ”Phong”, ”Vi”]?

A. 1.

B. 2.

C. 3.

D. 4.

Câu 11: Vị trí giữa của vùng tìm kiếm được tính như thế nào?

A. (Vị trí cuối + vị trí đầu)/2

B. (Vị trí cuối - vị trí đầu)/2

C. (Vị trí cuối - vị trí đầu - 1)/2

D. (Vị trí cuối + vị trí đầu -1)/2

Câu 12: Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu bước lặp để thông báo không tìm thấy số 15 trong danh sách [3, 5, 7, 11, 12, 25]?

A. 2.                    

B. 3.                    

C. 4.                    

D. 5.

4. VẬN DỤNG CAO (1 Câu)

Câu 1: Trong thuật toán tìm kiếm nhị phân, thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia nào?

A. (Số lượng thẻ của dãy +1) : 2.

B. Số lượng thẻ của dãy +1 : 2.

C. (Số lượng thẻ của dãy +1) : 3.

D. Số lượng thẻ của dãy : 2.