Phiếu bài tập Thuật toán và độ phức tạp có đáp á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²)

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. AHàm mũ
2. BTuyến tính
3. CLogarit
4. DĐa thức

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

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

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. ABài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
2. BMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
3. CBài toán có thể giải trong thời gian hằng số
4. DMọi bài toán con đều có cùng kích thước

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. ACây khung nhỏ nhất
2. BĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
3. CThứ tự tô-pô trong mọi đồ thị
4. DĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm

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

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

Bài toán dừng cho thấy rằng:

1. AMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng
2. BMọi chương trình cuối cùng đều dừng
3. CNên tránh các vòng lặp
4. DKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không