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

log₂ 1024 bằng bao nhiêu?

1. A12
2. B32
3. C512
4. D10

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

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

1. AO(n log n)
2. BO(2ⁿ)
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ó 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
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ó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS

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

1. AMộ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
2. BBài toán có thể giải trong thời gian hằng số
3. CMọi bài toán con đều có cùng kích thước
4. DBà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 đó

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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

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