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

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

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

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó chỉ có thể chạy một lần
2. BNó xử lý đúng một phần tử mỗi giây thời gian chạy
3. CNó luôn mất đúng một giây
4. DThời gian chạy của nó không tăng theo kích thước đầu vào

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

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

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

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

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
2. BViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp
3. CViệc chọn chỉ có thể thực hiện trong O(n²)
4. DQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất

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ỗi phép so sánh mất thời gian logarit
2. BTì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
3. CMọi phần tử phải được so sánh ít nhất một lần
4. DMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n