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

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(1)

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

1. AO(log n)
2. BO(n²)
3. CO(n)
4. DO(1)

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ABậc hai
2. BHằng số
3. CLogarit
4. DTuyến tính

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. AThuật toán Dijkstra
2. BBắt buộc phải dùng Bellman–Ford trong mọi trường hợp
3. CTìm kiếm theo chiều sâu
4. DThuật toán Kruskal

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

1. AO(n²)
2. BO(n)
3. CO(n log n)
4. DO(log n)

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 3 đồng; tối ưu là 3
2. BTham lam dùng 2 đồng; tối ưu là 2
3. CTham lam dùng 3 đồng; tối ưu là 2
4. DTham lam dùng 4 đồng; tối ưu là 3

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
2. BVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
3. CVì n luôn nhỏ
4. DVì nó chỉ hoạt động khi W = 0

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n^{log₂ 3}), khoảng n^1,585
2. BΘ(n log n)
3. CΘ(n³)
4. DΘ(n²)