k7. Bài 13. Thuật toán tìm kiếm

Thuật toán tìm kiếm nhị phân áp dụng với bài toán tìm kiếm kiểu nào?

• Áp dụng được với mọi bài toán tìm kiếm.

• Áp dụng với dãy giá trị đã được sắp xếp.

•  Áp dụng được với dãy giá trị chưa được sắp xếp.

Lựa chọn phương án đúng

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự , ta thực hiện:

• Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

• So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

• Sắp xếp dãy số theo thức tự tăng dần.

• So sánh số cần tìm với số ở giữa dãy số.

 Tìm một từ tiếng Anh trong cuốn từ điển, em sẽ tìm kiếm theo cách nào nhanh nhất?

• Tìm kiếm tuần tự

• Tìm kiếm nhị phân

• không áp dụng được.

Chọn phát biểu sai?

• Thuật toán tìm kiếm nhị phân chỉ áp dụng với dãy gia trị đã được sắp xếp. 

• Thuật toán tìm kiếm tuần tự chỉ áp dụng với dãy gia trị đã được sắp xếp.

• Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

• Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

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

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

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

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

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

Thuật toán tìm kiếm tuần tự kết thúc khi:

• Tìm kiếm được vị trí số cần tìm.

• Thông báo không tìm thấy số cần tìm.

• Tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

Trong thuật toán tìm kiếm tuần tự để tìm một số trong dãy thẻ số, sau bước Lật thẻ thứ nhất thì ta sẽ thực hiện bước nào?

• Kiểm tra: Số thẻ có đúng là số cần tìm không?

• Kiểm tra: tất cả các thẻ số đã được lật?

• Đầu ra: thông báo vị trí tìm thấy.

•  Kết thúc.

Thuật toán tìm kiếm nhị phân thực hiện như thế nào?

• Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm lớn hơn.

• Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

• So sánh lần lượt phần tử cuối cùng của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

• So sánh lần lượt phần tử đầu của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

Cho dãy số: 47, 35, 36, 11, 36, 46, 36, 63, 36, 18, 24. Để tìm số 36 trong dãy số này bằng thuật toán tìm kiếm tuần tự, ta cần thực hiện bao nhiêu lần lặp? 

• 3 lần.

• 5 lần.

• 7 lần.

• 9 lần. 

Ưu điểm của thuật toán tìm kiếm nhị phân là:

• Thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp.

• Số lần lặp tương tự như thuật toán tìm kiếm tuần tự.

• Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.