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 chậm hơn g một cách nghiêm ngặt
2. Bf tăng nhanh 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

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AO (Big O)
2. Bo (little o)
3. CΩ (Big Omega)
4. DΘ (Big Theta)

Ba bước của một thuật toán chia để trị là gì?

1. AChia, trị, kết hợp
2. BĐọc, tính toán, ghi
3. CĐoán, kiểm tra, lặp lại
4. DSắp xếp, tìm kiếm, trả về

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

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

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

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó xóa cạnh đắt nhất cho đến khi không còn chu trình
2. BNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
3. CNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
4. DNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây

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. ABà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
2. BBà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
3. CBà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ũ
4. DCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
2. BX quy dẫn về một bài toán trong P, và X thuộc NP
3. CX không có thuật toán đa thức, và X quyết định được
4. DX thuộc P, và X quy dẫn về SAT