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

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

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

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

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

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

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

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

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

1. AO(V³ × E)
2. BO(E log V)
3. CO(V + E)
4. DO(V × E)

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BThuật toán Dijkstra
3. CTìm kiếm theo chiều sâu
4. DThuật toán Kruskal

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 không có thuật toán đa thức, và X quyết định được
2. BX thuộc P, và X quy dẫn về SAT
3. CX 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
4. DX quy dẫn về một bài toán trong P, và X thuộc NP

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