Giải VTH Tin 7 Bài 15. Thuật toán tìm kiếm nhị phân có đáp án
-
108 lượt thi
-
10 câu hỏi
-
30 phút
Danh sách câu hỏi
Câu 1:
Xem đáp án
Gợi ý: Vị trí giữa của vùng tìm kiếm bằng phần nguyên của (vị trí đầu + vị trí cuối) /2.
Em hãy điền vào chỗ chấm trong gợi ý ở Bước 1 sau đây các bước sau thực hiện tương tự.
Trả lời:
Bước 1. Vị trí giữa của vùng tìm kiếm là 5. So sánh “Hòa” và “Mai”. Vì H đứng trước M trong bảng chữ cái nên vùng tìm kiếm là nửa trước của dãy (từ vị trí 1 đến vị trí 4).
Bước 2. Vị trí giữa của vùng tìm kiếm là 2. So sánh “Hòa” và “Bình”. Vì H đứng sau B trong bảng chữ cái nên vùng tìm kiếm là nửa sau của dãy (từ vị trí 3 đến vị trí 4).
Bước 3. Vị trí giữa của vùng tìm kiếm là 3. So sánh ta thấy giá trị ở vị trí giữa đúng là “Hòa” là giá trị cần tìm. Thuật toán kết thúc.
Câu 2:
Xem đáp án
Gợi ý: Sắp xếp và tìm kiếm có mối liên hệ mật thiết với nhau. Khi danh sách được sắp xếp, việc tìm kiếm sẽ được thực hiện nhanh chóng. Trong thư viện, các cuốn sách được sắp xếp theo lĩnh vực, trong mỗi lĩnh vực, sách lại được sắp xếp theo thứ tự theo chữ cái tên của tác giả hoặc tên sách. Việc này giúp cho người thủ thư dễ dàng tìm thấy cuốn sách mà em muốn mượn. Dựa vào ví dụ này không có thể nêu thêm các ví dụ khác trong thực tế.
Trả lời:
Ví dụ: Việc tra từ điển tiếng anh. Trong từ điển, các từ tiếng anh được sắp xếp theo một trật tự bảng chữ cái. Việc làm này sẽ thuận lợi cho việc tra từ điển tiếng anh một cách dễ dàng.
Câu 3:
Cho danh sách tên các nước sau đây:
Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greendland, Germany
Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.
Xem đáp án
Gợi ý: Thuật toán tìm kiếm nhị phân thực hiện trên danh sách đã được sắp xếp. Do đó trước tiên cần sắp xếp danh sách theo thứ tự bảng chữ cái. Sau đó thực hiện thuật toán tìm kiếm nhị phân tên nước Iceland trong danh sách đã sắp xếp.
Trả lời:
Sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái: Albania, Bolivia, Canada, Germany, Greendland, Iceland, Portugal, Scotland, Vietnam
Câu 4:
Xem đáp án
Gợi ý: Thuật toán tìm kiếm nhị phân thực hiện trên danh sách đã được sắp xếp. Do đó trước tiên cần sắp xếp danh sách theo thứ tự bảng chữ cái. Sau đó thực hiện thuật toán tìm kiếm nhị phân tên nước Iceland trong danh sách đã sắp xếp.
Trả lời:
Các bước tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân:
Bước 1: Vị trí ở giữa của vùng tìm kiếm là 5 _Greenland. So sánh “Iceland” và “Greenland”. Vì I đứng sau G trong bảng chữ cái nên vùng tìm kiếm là nửa sau của dãy.
Bước 2: Vị trí ở giữa của vùng tìm kiếm là 7 _Portugal. So sánh “Iceland” và “Portugal”. Vì I đứng trước P trong bảng chữ cái nên vùng tìm kiếm là nửa đầu của dãy.
Bước 3: Vì nửa trước của dãy chỉ còn một tên, đó là vị trí số 6_ Iceland. So sánh thấy “Iceland” trùng với “Iceland”, tìm thấy tên nước cần tìm nên thuật toán dừng lại.
Câu 5:
Xem đáp án
Gợi ý: Thuật toán tìm kiếm nhị phân thực hiện trên danh sách đã được sắp xếp. Do đó trước tiên cần sắp xếp danh sách theo thứ tự bảng chữ cái. Sau đó thực hiện thuật toán tìm kiếm nhị phân tên nước Iceland trong danh sách đã sắp xếp.
Trả lời:
Số bước thực hiện tìm kiếm ở Câu 14.3 của Bài 14 là: 6 bước.
Số bước thực hiện tìm kiếm ở câu b là: 3 bước
So sánh: Số bước thực hiện tìm kiếm ở phần b ít hơn so với số bước thực hiện tìm kiếm ở Câu 14.3 phần Luyện tập của bài 14.
Câu 6:
Xem đáp án
Gợi ý: Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm trên danh sách đã được sắp xếp. Một số ví dụ về danh sách như sau: danh sách học sinh trong lớp, danh mục sách trong thư viện, danh mục hàng hóa, danh mục thiết bị,… Trước tiên em lập danh sách và sắp xếp danh sách. Sau đó xác định giá trị cần tìm. Cuối cùng thực hiện thuật toán tìm kiếm nhị phân để tìm giá trị trong danh sách đã được sắp xếp.
Trả lời:
Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:
Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:
Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5
Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3
Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.
Câu 7:
Xem đáp án
Gợi ý: Các từ trong từ điển thường được sắp xếp theo bảng chữ cái với danh sách đã được sắp xếp em nên tìm kiếm bằng thuật toán tìm kiếm nào để hiệu quả và nhanh chóng?
Trả lời:
Em tìm một từ tiếng Anh trong quyển từ điển bằng cách chia đổi quyển từ điển, tìm một từ bất kì ở giữa quyển từ điển và so sánh với từ cần tìm. Nếu tìm thấy từ đó thì sẽ kết thúc việc tìm kiếm. Nếu chưa em lại tiếp tục chia quyển từ điển theo nửa thích hợp, đến khi nào tìm được từ cần tìm thì kết thúc. Em dùng cách này vì nhanh chóng và thuận tiện hơn là tìm kiếm từng từ trong bảng chữ cái.
Câu 8:
Đ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.
Xem đáp án
Gợi ý: Thuật toán tìm kiếm nhị phân chừng nào chưa tìm thấy và chưa tìm hết thì còn tiền tiếp.
Trả lời:
Đáp án đúng là: D
Thuật toán tìm kiếm nhị phân chừng nào chưa tìm thấy và chưa tìm hết thì còn tiền tiếp.
Câu 9:
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
Xem đáp án
Gợi ý: Em thực hiện các bước tìm kiếm theo thuật toán tìm kiếm nhị phân để tìm ra câu trả lời.
Trả lời:
Đáp án đúng là: B
Bước 1: Vị trí giữa của vùng tìm kiếm là Myanmar, So sánh Thailand và Myanmar, → vùng tìm kiếm là nửa sau của dãy.
Bước 2: Vị trí giữa của vùng tìm kiếm là Thailand, so sánh Thailand và Thailand → trùng nhau nên kết thúc việc tìm kiếm.
Câu 10:
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
Xem đáp án
Gợi ý: Thông báo không tìm thấy số 10 khi thuật toán đã tìm hết danh sách. Em thực hiện các bước tìm kiếm theo thuật toán tìm kiếm nhị phân để tìm ra câu trả lời.
Trả lời:
Đáp án đúng là: B
Bước 1: Vị trí giữa của vùng tìm kiếm là 8, So sánh 10 và 8 → vùng tìm kiếm là nửa sau của dãy.
Bước 2: vị trí giữa của vùng tìm kiếm là 14, so sánh 14 và 10 → vùng tìm kiếm là nửa đầu của dãy.
Bước 3. Trong dãy còn số 11, so sánh 11 khác 10 → Không tìm thấy số 10 → Kết thúc.