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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig Omega
2. BBig O
3. CBig Theta
4. DLittle omega

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n²
2. BKhoảng n
3. CKhoảng n / 2
4. DKhoảng log₂ n

log₂ 1024 bằng bao nhiêu?

1. A12
2. B32
3. C512
4. D10

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

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

Quy hoạch động hữu ích khi một bài toán có:

1. AChỉ các đầu vào ngẫu nhiên
2. BMột vòng lặp duy nhất
3. CHoàn toàn không có bài toán con, nên có thể giải trong một bước
4. DCác bài toán con chồng lặp và cấu trúc con tối ưu

Độ 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(2ⁿ)
3. CO(log n)
4. DO(n²)

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. ASAT tổng quát trên các công thức dạng chuẩn tắc hội
2. BThỏa mãn mạch
3. C2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
4. D3-SAT, trong đó mỗi mệnh đề có đúng ba literal

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

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