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

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AThời gian cho một đầu vào có độ dài trung bình
2. BThời gian trên loại máy tính phổ biến nhất
3. CThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n
4. DGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất

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

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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B12
3. C10
4. D512

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 Kruskal
3. CThuật toán Dijkstra
4. DTìm kiếm theo chiều sâu

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

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

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 + E) log V)
3. CO(V³)
4. DO(V × E)