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

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

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

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, nhưng chỉ khi n nhỏ hơn 100
3. CĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
4. DKhông, vì n³ nhỏ hơn n² khi n lớn

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

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

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

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