Câu hỏi tự luận Tin học 7 Bài 15: Thuật toán tìm kiếm nhị phân

Câu hỏi tự luận Tin học 7 bài 15

Câu hỏi tự luận Tin học 7 Bài 15: Thuật toán tìm kiếm nhị phân bao gồm hệ thống câu hỏi và đáp án chi tiết, được xây dựng theo 4 mức độ từ Nhận biết, Thông hiểu đến Vận dụng và Vận dụng cao. Tài liệu bám sát nội dung chương trình học, giúp học sinh củng cố kiến thức được học. Thông qua việc luyện tập với nhiều dạng câu hỏi, các em có thể nâng cao kỹ năng tư duy, khả năng phân tích và vận dụng kiến thức vào các tình huống thực tế. Mời các em tham khảo và tải về để ôn tập hiệu quả.

BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN (15 CÂU)

I. NHẬN BIẾT (2 CÂU)

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

Trả lời:

- Thuật toán tìm kiếm nhị phân là thuật toán thực hiện tìm trên danh sách đã được sắp xếp theo thứ tự từ nhỏ đến lớn. Bát đầu từ vị trí ở giữa danh sách.

- Tại mỗi bước lặp, so sánh giá trị cần tìm với giá trị của vị trí giữa danh sách, nếu bằng thì dừng lại, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách.

- Chừng nào chưa tìm thấy và vùng tìm kiếm còn phần tử thì còn tiếp tục.

Câu 2: Hãy mô tả thuật toán tìm kiếm nhị phân.

Trả lời:

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

Bước 2: Xác định vị trí giữa củ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 “giá trị cần tìm xuất hiện tại vị trí giữa” và 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 nửa trước 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 nửa sau của dãy.

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

II. THÔNG HIỂU (5 CÂU)

Câu 1: Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là gì?

Trả lời:

Sự khác nhau giữa thuật toán tìm kiếm tuần tự và thuật toán tìm kiếm nhị phân là: Thuật toán tuần tự sẽ không yêu cầu danh sách cần phải được sắp xếp nhưng thuật toán tìm kiếm nhị phân cần danh sách phải được sắp xếp thì mới có thể thực hiện được.

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

Trả lời:

Thuật toán tìm kiếm nhị phân được sử dụng trong trường hợp danh sách đã được sắp xếp và yêu cầu đi tìm một phần tử bất kì.

III, VẬN DỤNG (6 CÂU)

Câu 1: Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm.

Trả lời:

Trong thực tế trong quản lý học sinh, danh sách học sinh luôn được sắp xếp theo chữ cái đầu của tên để dễ tìm kiếm.

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 “Mai" trong danh sách ["Hoa”, ”Lan”, "Ly”, ”Mai”, ”Phong”, ”Vi]?

Trả lời:

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

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

Bước 2: Xét vị trí ở giữa của nửa sau danh sách, đó là vị trí số 5.

So sánh “Phong” và “Mai”. Vì “P” đứng sau “M” 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 dãy giữa sau danh sách, đó 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 đã tìm thấy “Mai” trong danh sách.

Câu 3: 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]?

..................

Mời các bạn xem tiếp trong file tải