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

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó có thể được giải trong thời gian đa thức
2. BNó không có lời giải
3. CNó chỉ có thể được giải bằng cách thử mọi khả năng
4. DNó có thể được giải trong thời gian hằng số

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

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

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

1. AHàm mũ
2. BLogarit
3. CTuyến tính
4. DĐa thức

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

1. ACác bài toán con chồng lặp và cấu trúc con tối ưu
2. BChỉ các đầu vào ngẫu nhiên
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. DMột vòng lặp duy nhất

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

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

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

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

Cận nào là đúng cho log(n!)?

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

Phát biểu nào về P và NP là đúng?

1. AMọi bài toán trong P cũng thuộc NP
2. BNP có nghĩa là "không đa thức"
3. CCác bài toán NP không thể được kiểm chứng nhanh
4. DĐã được chứng minh rằng P ≠ NP