/codegym.vn/ - 151
Câu 2: Độ phức tạp tệ nhất của thuật toán tìm kiếm nhị phân là gì?
a) O(logn)
b) O(nlogn)
c) O(1)
d) O(n)
Câu 3: Với một mảng số nguyên đã được sắp xếp theo trật tự giảm dần thì thuật toán
tìm kiếm nào có hiệu quả nhất?
a) Thuật toán tìm kiếm tuyến tính
b) Thuật toán tìm kiếm nhị phân
Câu 4: Thuật toán tìm kiếm nào là tốt nhất cho một danh sách lớn
a) Tìm kiếm tuần tự
b) Sử dụng vòng lặp for-in
c) Tìm kiếm nhị phân
Câu 5: Trung bình, một thuật toán tìm kiếm tuần tự sẽ mất N / 2 số lần so sánh cho
một danh sách kích thước N.
a) Đúng
b) Sai
Câu 6: Điều sau đây được là đúng đối với thuật toán tìm kiếm nhị phân?
a) Có thể áp dụng với dữ liệu đã được sắp xếp theo trật tự tăng dần
b) Có thể áp dụng với dữ liệu đã được sắp xếp theo trật tự giảm dần
c) Có thể áp dụng với dữ liệu chưa được sắp xếp
Đáp án: Câu 1: d; Câu 2: a; Câu 3: b; Câu 4: c; Câu 5: a; Câu 6: a và b;
10. Tổng kết
● Tìm kiếm dữ liệu là một thao tác được thực hiện thường xuyên trong các ứng
dụng
● Thuật toán tìm kiếm tuyến tính hoạt động dựa trên cơ chế duyệt qua lần lượt
tất cả các phần tử
● Thuật toán tìm kiếm nhị phân hoạt động dựa trên cơ chế chia nhỏ tập dữ liệu
● Thuật toán tìm kiếm nhị phân chỉ có thể thực hiện được trên tập dữ liệu đã
được sắp xếp
● Độ phức tạp của thuật toán là một đại lượng để đo tính hiệu quả của một thuật
toán
● Độ phức tạp của thuật toán tìm kiếm nhị phân là nhỏ hơn so với độ phức tạp
của thuật toán tìm kiếm tuyến tính