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 dưới của tốc độ tăng?

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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BChia để trị
3. CLựa chọn tham lam
4. DVét cạn

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

1. ATuyến tính
2. BLogarit
3. CĐa thức
4. DHàm mũ

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 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
2. BChọn hoạt động ngắn nhất trước
3. CChọ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
4. DChọn hoạt động bắt đầu sớm nhất

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

1. ANó 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
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ó xóa cạnh đắt nhất cho đến khi không còn chu trình

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

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

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó luôn giải được trong O(V + E)
2. BNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
3. CNó là NP-khó
4. DNó bất khả quyết định

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. A3-SAT, trong đó mỗi mệnh đề có đúng ba literal
2. BSAT tổng quát trên các công thức dạng chuẩn tắc hội
3. CThỏa mãn mạch
4. D2-SAT, trong đó mỗi mệnh đề có tối đa hai literal