Đáp án:

 

Giải thích các bước giải:

 Câu 1.1:

Với thuật toán tìm kiếm nhị phân, khi nào thì tìm kiếm nhanh nhất, cần ít phép so sánh nhất? Vì sao?

-Tìm kiếm nhanh nhất khi phần tử cần tìm nằm ngay chính giữa danh sách ngay từ lần so sánh đầu tiên.

-Lý do: Vì thuật toán tìm kiếm nhị phân chia danh sách thành hai nửa sau mỗi lần so sánh, nếu phần tử cần tìm nằm ngay giữa danh sách, ta sẽ tìm thấy nó ngay trong lần kiểm tra đầu tiên, chỉ mất 1 phép so sánh.

Câu 1.2:

Với thuật toán tìm kiếm tuần tự, khi nào thì tìm kiếm nhanh nhất, cần ít bước nhất? Vì sao?

-Tìm kiếm nhanh nhất khi phần tử cần tìm nằm ở vị trí đầu tiên trong danh sách.

-Lý do: Tìm kiếm tuần tự kiểm tra từng phần tử từ đầu đến cuối, nên nếu phần tử cần tìm nằm ngay đầu danh sách, ta chỉ cần 1 lần so sánh để tìm thấy nó.

Câu 1.3:

Với thuật toán tìm kiếm nhị phân, khi nào thì việc tìm kiếm sẽ chậm nhất, cần nhiều phép so sánh nhất? Vì sao?

-Tìm kiếm chậm nhất khi phần tử cần tìm nằm ở đầu hoặc cuối danh sách, hoặc không tồn tại trong danh sách.

-Lý do: Trong trường hợp xấu nhất, thuật toán phải liên tục chia đôi danh sách cho đến khi chỉ còn 1 phần tử cuối cùng cần so sánh. Số lần so sánh tối đa sẽ là log₂(n) + 1 với n là số phần tử trong danh sách.

Câu 1.4:

Với thuật toán tìm kiếm tuần tự, khi nào thì việc tìm kiếm sẽ chậm nhất, cần nhiều phép so sánh nhất? Vì sao?

-Tìm kiếm chậm nhất khi phần tử cần tìm nằm ở cuối danh sách hoặc không tồn tại trong danh sách.

-Lý do: Vì thuật toán tìm kiếm tuần tự kiểm tra từng phần tử từ đầu đến cuối, nếu phần tử cần tìm nằm ở vị trí cuối hoặc không có trong danh sách, ta phải duyệt toàn bộ n phần tử để chắc chắn rằng nó không tồn tại. Số phép so sánh tối đa là n.