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 trong trường hợp xấu nhất của sắp xếp chèn là gì?

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

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

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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

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. ATìm kiếm theo chiều sâu
2. BThuật toán Dijkstra
3. CBắt buộc phải dùng Bellman–Ford trong mọi trường hợp
4. DThuật toán Kruskal

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn log n)
4. DO(mn)

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. ABài toán có thể giải trong thời gian hằng số
2. BBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
3. CMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
4. DMọi bài toán con đều có cùng kích thước

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n log n)
2. BΘ(n^{log₂ 3}), khoảng n^1,585
3. CΘ(n³)
4. DΘ(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ó bất khả quyết định
2. BNó luôn giải được trong O(V + E)
3. CNó là NP-khó
4. DNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu