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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

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

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

log₂ 1024 bằng bao nhiêu?

1. A12
2. B10
3. C512
4. D32

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

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. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BThuật toán Dijkstra
3. CTìm kiếm theo chiều sâu
4. DThuật toán Kruskal

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
2. BViệc chọn chỉ có thể thực hiện trong O(n²)
3. CQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

1. AO(n³)
2. BO(n² 2ⁿ)
3. CO(2^n²)
4. DO(n!)