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

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng nhanh hơn g một cách nghiêm ngặt
2. Bf tăng chậm hơn g một cách nghiêm ngặt
3. Cf luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới
4. Df tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp nổi bọt
2. BQuicksort
3. CSắp xếp trộn
4. DSắp xếp chèn

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

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

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích
2. BChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động bắt đầu sớm nhất
4. DChọn hoạt động ngắn nhất trước

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, nhưng chỉ khi n nhỏ hơn 100
3. CĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
4. DKhông, vì n³ nhỏ hơn n² khi n lớn

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

1. ANP có nghĩa là "không đa thức"
2. BMọi bài toán trong P cũng thuộc NP
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

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ACả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
2. BBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
3. CBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
4. DBài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ