Câu hỏi về thuật toán tìm kiếm

Trong tìm kiểm tuần tự, nếu phần tử cần tìm không có trong danh sách, thuật toán sẽ thực hiện bao nhiêu lần duyệt?

• 1

• Bằng độ dài danh sách

• Một nửa độ dài danh sách

• Tùy thuộc vào vị trí phần tử cần tìm

Thuật toán tìm kiếm nhị phân có thể tìm kiếm trong danh sách có chứa giá trị trùng lặp không?

• Có

• Không

• Chỉ khi các giá trị trùng lặp nằm ở đâu danh sách

• Chỉ khi danh sách có số phần tử chẵn

Giả sử bạn có danh sách A = [3, 8, 12, 17, 25, 31, 42]. Khi tìm kiểm số 17 bằng thuật toán tìm kiếm nhị phân, số lần so sánh tối đa là bao nhiêu?

• 2

• 3

• 4

• 5

Điểm khác biệt chính giữa tìm kiếm tuần tự và tìm kiếm nhị phân là gì?

• Tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân

• Tìm kiếm nhị phân chỉ hoạt động trên danh sách đã sắp xếp

• Tìm kiếm tuần tự chỉ áp dụng cho số nguyên

• Tìm kiếm nhị phân cần nhiều bộ nhớ hơn

Độ phức tạp thời gian trung bình của thuật toán tìm kiểm tuần tự là gì?

• O (1)

• O(n)

• O(log n)

• O(n^2)

Độ phức tạp thời gian trung bình của thuật toán tìm kiểm nhị phân là gì?

• O (1)

• O(n)

• O(log n)

• O(n^2)

Tìm kiếm nhị phân hoạt động hiệu quả hơn tìm kiếm tuần tự trong trường hợp nào?

• Khi danh sách đã được sắp xếp

• Khi danh sách có ít phần tử

• Khi danh sách không được sắp xếp

• Khi danh sách chứa nhiều số âm

Nếu danh sách có 1024 phần tử, số lần so sánh tối đa trong thuật toán tìm kiểm nhị phân là bao nhiêu?

• 10

• 20

• 512

Trong tìm kiếm nhị phân, nếu giá trị cần tìm lớn hơn giá trị ở vị trí giữa danh sách, ta sẽ:

• Tìm kiếm ở nửa bên trái

• Tìm kiếm ở nửa bên phải

• Dừng tìm kiếm ngay lập tức

• Duyệt qua toàn bộ danh sách

Giá sử có danh sách A = [5, 8, 12, 15, 20, 25, 30]. Nếu tìm kiếm số 10 bằng thuật toán nhị phân, kết quả là gì?

• 2

• 3

• -1

• 4