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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Big O của 3n² + 5n + 2 là gì?

1. AO(n³)
2. BO(3n²)
3. CO(5n)
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. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BTìm kiếm theo chiều sâu
3. CThuật toán Dijkstra
4. DThuật toán Kruskal

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. AHằng số
2. BHàm mũ
3. CLogarit
4. DTuyến tính

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 quy dẫn về một bài toán trong P, và X thuộc NP
4. DX 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

Bài toán người bán hàng rong được phân loại thế nào?

1. ANó thuộc P vì thuật toán Dijkstra giải được nó bằng cách thăm mỗi thành phố một lần
2. BPhiên bản quyết định là NP-đầy đủ và phiên bản tối ưu hóa là NP-khó
3. CNó bất khả quyết định
4. DPhiên bản quyết định thuộc P nhưng phiên bản tối ưu hóa là NP-đầy đủ