Sách bài tập Tin học 7 Bài 15 (Kết nối tri thức): Thuật toán tìm kiếm nhị phân

Giải sách bài tập Tin học 7 Bài 15. Thuật toán tìm kiếm nhị phân

Câu 15.1 trang 52 SBT Tin học 7

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.

Trả lời:

Đáp án đúng là: B

Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp: Tìm một phần tử trong danh sách đã được sắp xếp.

Câu 15.2 trang 52 SBT Tin học 7:

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 kiếm 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.

Trả lời:

Đáp án đúng là: D

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 thì Thông báo “Không tìm thấy” và kết thúc.

Câu 15.3 trang 52 SBT Tin học 7:

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

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.

Trả lời:

Đáp án đúng là: B

Hoạt động của tìm kiếm nhị phân: 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âu 15.4 trang 53 SBT Tin học 7:

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

Trả lời:

Đáp án đúng là: C

Thuật toán tìm kiếm nhị phân cần 4 bước để tìm thấy Mai trong danh sách [“Hoa”, “Lan”, “Mai”, “Phong”, “Vy”].

Câu 15.5 trang 53 SBT Tin học 7:

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

Trả lời:

Đáp án đúng là:  C

Thuật toán tìm kiếm nhị phân cần thực hiện 4 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].

Câu 15.6 trang 53 SBT Tin học 7:

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.

Trả lời:

Đáp án đúng là: C

Khi thực hiện thuật tìm kiếm nhị phân để tìm số 10 trong danh sách [2, 4, 6, 8, 10, 12] thì: Đầu ra của thuật toán là: 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.

Câu 15.7 trang 53 SBT Tin học 7:

Trả lời:

1 – c, d

2 – a, b

Câu 15.8 trang 53 SBT Tin học 7:

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 5. Lặp lại 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).

Trả lời:

(1) “Không tìm thấy”

(2) giá trị cần tìm xuất hiện ở vịt trí giữa.

(3) nửa trước

(4) nửa sau

Câu 15.9 trang 54 SBT Tin học 7:

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 9,5 môn Tin học. Hãy cho biết tên học sinh đó.

Trả lời:

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

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

Vùng tìm kiếm là dãy số: 7,58,08,59,09,510

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.

Thông báo: Bạn Ngô Phương Thảo được điểm 9,5 môn Tin học.

Câu 15.10 trang 54 SBT Tin học 7:

Trả lời:

Hướng dẫn:

Bước 1. Tìm kiếm thông tin trên Internet, lập bảng danh sách khoảng 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.