Chủ đề 5. Bài 15. Thuật toán tìm kiếm nhị phân

Mời các em cùng Bumbii tham khảo hướng dẫn giải các bài tập bài 15 thuật toán tìm kiếm nhị phân trang 52 sách bài tập tin học lớp 7, NXB Kết nối tri thức với cuộc sống

CHỦ ĐỀ 5. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH. BÀI 15. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

Câu 15.1

Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp nào?

A. Tìm một phần tử trong danh sách bất kì.

B. Tìm một phần tử trong danh sách đã được sắp xếp.

Đáp án: B.

Khi danh sách đã được sắp xếp, em không cần tìm từ đầu mà so sánh ngay giá trị cần tìm với giá trị của vị trí ở giữa danh sách.

Câu 15.2

Điều gì xảy ra khi thuật toán tìm kiếm nhị phân không tìm thấy giá trị cần tìm trong danh sách?

A. Tiếp tục tìm kiếm và không bao giờ kết thúc.

B. Thông báo “Tìm thấy” và tìm tiếp xem còn phần tử nào khác nữa không.

C. Thông báo “Tìm thấy” và kết thúc.

D. Thông báo “Không tìm thấy” và kết thúc.

Đáp án: D.

Câu 15.3

Chọn câu diễn đạt đúng hoạt động của thuật toán tìm kiếm nhị phân:

A. Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

B. Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

C. Tìm trên danh sách bất kì, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

D. Tìm trên danh sách bất kì, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.

Đáp án: B.

Câu 15.4

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”, “Vï”]?

A. 1.             B. 2.             C. 3.             D. 4.

Đáp án: C.

Xác định vị trí giữa của vùng tìm kiếm trong danh sách.

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.

Lưu ý: “nửa trước” và “nửa sau” vùng tìm kiếm không bao gồm phần tử giữa.

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 3, có giá trị là “Ly”.

So sánh “Mai” và “Ly”, vì “M” đứng sau “L” trong bảng chữ cái nên bỏ đi nửa trước danh sách.

Bước 2: Xét vị trí ở giữa của vùng nửa sau của dãy là vị trí số 5.

So sánh “Mai” và “Phong”, vì “M” đứng trước “P” trong bảng chữ cái nên bỏ đi nửa sau danh sách.

Bước 3: Xét vị trí ở giữa của vùng nửa trước của dãy là vị trí số 4.

So sánh “Mai” và “Mai”, vì hai giá trị bằng nhau nên thuật toán kết thúc.

Sau 3 bước, bằng thuật toán tìm kiếm nhị phân đã tìm thấy “Mai” trong danh sách.

Câu 15.5

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.

Đáp án: C.

Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 3, có giá trị là 7.

So sánh 7 và 15, vì 15 > 7 nên bỏ đi nửa trước danh sách.

Bước 2: Xét vị trí ở giữa của dãy, đó là vị trí số 5, có giá trị là 12.

So sánh 12 và 15, vì 15 > 12 nên bỏ đi nửa trước danh sách.

Bước 3: Xét vị trí ở giữa của dãy, đó là vị trí số 6, có giá trị là 25.

So sánh 25 và 15, vì 15 < 25 và chỉ còn 1 phần tử trong danh sách nên đã hết phần tử tìm kiếm.

Bước 4: Vùng tìm kiếm không còn phần tử nào nên kết luận không tìm thấy và thuật toán kết thúc.

Câu 15.6

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.

Đáp án: C.

Câu 15.7

Hãy ghép mỗi nội dung ở cột A với những nội dung phù hợp ở cột B để xác định đầu vào và đầu ra của thuật toán tìm kiếm nhị phân.

Đáp án: 1 – c; 1 – d; 2 – a; 2 – b.

Câu 15.8

Em hãy điền các cụm từ: giá trị cần tìm xuất hiện ở vị trí giữa, nửa sau, “Không tìm thấy”, nửa trước vào chỗ chẫm (…) được đánh số trong các câu sau để được mô tả chính xác về thuật toán tìm kiếm nhị phân.

Bước 1. Nếu vùng tìm kiếm không có phần tử nào thì kết luận ………….(1)………… và thuật toán kết thúc.

Bước 2. Xác định vị trí giữa vùng tìm kiếm. Vị trí này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa.

Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận …………………………………..(2)……………………………….. và thuật toán kết thúc.

Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn …………….(3)……………… của dãy.

Ngược lại (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa) thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn ……………(4)………………. của dãy.

Bước 5. Lặp lại từ Bước 1 đến Bước 5 cho đến vùng tìm kiếm không khi còn phần tử nào (Bước 1) hoặc tìm thấy giá trị cần tìm (Bước 3).

Đáp án: (1) – “Không tìm thấy”; (2) – giá trị cần tìm xuất hiện ở vị trí giữa; (3) – nửa trước; (4) – nửa sau.

Câu 15.9

Cho bảng điểm môn Tin học của học sinh tổ một như sau:

a) Em hãy sắp xếp lại danh sách theo thứ tự tăng dần của Điểm.

b) Em hãy liệt kê các bước lặp thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học. Hãy cho biết tên học sinh đó.

Đáp án:

a) Danh sách học sinh sắp xếp theo thứ tự tăng dần của Điểm:

b) Các bước thực hiện thuật toán tìm kiếm nhị phân để tìm học sinh được điểm 9,5 môn Tin học.

Vùng tìm kiếm là dãy số:

• Bước 1: Chọn phần tử ở giữa, đó là 8,5. So sánh ta có 9,5 > 8,5, do đó vùng tìm kiếm thu hẹp chỉ còn nửa sau của danh sách.
• Bước 2: Chọn phần tử ở giữa, đó là 9,5. So sánh ta có 9,5 = 9,5, tìm thấy giá trị cần tìm nên thuật toán dừng lại.

Câu 15.10

Thực hành: Em hãy tìm kiếm thông tin trên Internet để lập bảng danh sách khoảng 10 cuốn sách mà em yêu thích và đơn giá của mỗi cuốn sách.

Sau đó thực hiện thuật toán tìm kiếm nhị phân để tìm cuốn sách mà em thích nhất trong danh sách vừa tìm được và cho biết đơn giá của cuốn sách đó.

Đáp án: Hướng dẫn:

• Bước 1. Tìm kiếm thông tin trên Internet, lập bảng danh sách 10 cuốn sách và đơn giá của mỗi cuốn sách.
• Bước 2. Sắp xếp tên sách theo thứ tự của bảng chữ cái.
• Bước 3. Chỉ ra tên một cuốn sách mà em thích nhất.
• Bước 4. Liệt kê các bước thực hiện thuật toán tìm kiếm nhị phân để tìm tên cuốn sách mà em thích nhất trong danh sách ở Bước 2.
• Bước 5. Ghi ra đơn giá của cuốn sách tìm thấy ở Bước 4.

__________***__________

Xem các bài giải khác tại link https://bumbii.com/giai-sach-bai-tap-tin-hoc-lop-7-nxb-ket-noi-tri-thuc-voi-cuoc-song/

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

Tuyết Nguyễn

Không bao giờ từ bỏ hy vọng. Cố gắng mỗi ngày.