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 xấu nhất của sắp xếp chèn là gì?

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

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. ALogarit
2. BĐa thức
3. CTuyến tính
4. DHàm mũ

log₂ 1024 bằng bao nhiêu?

1. A512
2. B10
3. C12
4. D32

Công thức truy hồi T(n) = 2T(n − 1) + O(1) có nghiệm là gì?

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

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
2. BNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
3. CNó xóa cạnh đắt nhất cho đến khi không còn chu trình
4. DNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CĐúng, nhưng chỉ khi n nhỏ hơn 100
4. DKhông, vì n³ nhỏ hơn n² khi n lớn

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó luôn giải được trong O(V + E)
2. BNó bất khả quyết định
3. CNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
4. DNó là NP-khó

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

1. AΘ(n log n)
2. BΘ(n log² n)
3. CΘ(n)
4. DΘ(n²)