Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó xử lý đúng một phần tử mỗi giây thời gian chạy
2. BNó luôn mất đúng một giây
3. CThời gian chạy của nó không tăng theo kích thước đầu vào
4. DNó chỉ có thể chạy một lần

Thuật toán vét cạn là gì?

1. AThuật toán chạy trên nhiều bộ xử lý
2. BThuật toán thử mọi lời giải ứng viên có thể
3. CThuật toán đoán một đáp án ngẫu nhiên
4. DThuật toán luôn dùng đệ quy

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΩ (Big Omega)
2. Bo (little o)
3. CΘ (Big Theta)
4. DO (Big O)

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 4 đồng; tối ưu là 3
2. BTham lam dùng 3 đồng; tối ưu là 3
3. CTham lam dùng 3 đồng; tối ưu là 2
4. DTham lam dùng 2 đồng; tối ưu là 2

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ACơ số chỉ quan trọng với n nhỏ
2. BCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
3. CLogarit luôn được làm tròn thành số nguyên
4. DMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng n / 2
2. BKhoảng log₂ n
3. CKhoảng √n
4. DKhoảng n

Thuật toán Bellman–Ford phát hiện chu trình trọng số âm có thể đến được từ nguồn bằng cách nào?

1. ANó đếm các chu trình bằng tìm kiếm theo chiều sâu
2. BNó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách
3. CSau V − 1 vòng, nó kiểm tra xem có cạnh nào vẫn có thể được nới lỏng không
4. DNó kiểm tra xem có cạnh nào có trọng số âm không

Một bài toán là NP-đầy đủ nếu nó:

1. AThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
2. BNằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng
3. CKhông thể giải được
4. DGiải được trong thời gian đa thức