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. ABậc hai
2. BTuyến tính
3. CHằng số
4. DLogarit

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

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

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A6 giây
2. B12 giây
3. C3 giây
4. D9 giây

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 1,000
2. BKhoảng 500,000
3. CKhoảng 20
4. DKhoảng 100

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của một thuật toán trên đầu vào tốt nhất
2. BChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
3. CChi phí kỳ vọng trên các đầu vào ngẫu nhiên
4. DChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. AKhông biến thể nào
2. BCái túi phân số, trong đó các món có thể bị chia nhỏ
3. CBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên
4. DCả hai biến thể

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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