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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. AHằng số
2. BBậc hai
3. CLogarit
4. DTuyến tính

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

1. AO(nⁿ)
2. BO(2ⁿ)
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²)

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó 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
2. BNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
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ó xóa cạnh đắt nhất cho đến khi không còn chu trình

Một thuật toán tham lam:

1. AChỉ dùng đệ quy
2. BĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
3. CThử mọi lời giải có thể
4. DLuôn cho lời giải tối ưu

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

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
2. BMỗi phép so sánh mất thời gian logarit
3. CMọi phần tử phải được so sánh ít nhất một lần
4. DTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
2. BCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O
3. CCó, vì cả hai đều là hàm mũ
4. DKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn