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

Thời gian chạy nào sau đây là đa thức?

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

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

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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng không được có quá 1000 phần tử
2. BMảng phải được sắp xếp
3. CĐộ dài mảng phải là lũy thừa của hai
4. DMảng chỉ được chứa số dương

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. AHàm mũ
2. BLogarit
3. CHằng số
4. DTuyến tính

Một thuật toán tham lam:

1. ALuôn cho lời giải tối ưu
2. BĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
3. CThử mọi lời giải có thể
4. DChỉ dùng đệ quy

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

1. AO(E log V)
2. BO(V + E)
3. CO(V³ × E)
4. DO(V × E)

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³)
3. CΘ(n log n)
4. DΘ(n²)

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Kruskal
2. BThuật toán Prim bắt đầu từ một nút
3. CThuật toán Dijkstra
4. DFloyd–Warshall