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

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

1. AThuật toán thử mọi lời giải ứng viên có thể
2. BThuật toán chạy trên nhiều bộ xử lý
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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A1 giây
2. B4 giây
3. C2 giây
4. D8 giây

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

1. ALogarit
2. BTuyến tính
3. CHàm mũ
4. DĐa thức

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

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

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

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

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

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

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²)

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(log n) và không gian O(n)
2. BThời gian O(n) và không gian O(1)
3. CThời gian O(n) và không gian O(n)
4. DThời gian O(2ⁿ) và không gian O(1)