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

Ba bước của một thuật toán chia để trị là gì?

1. ASắp xếp, tìm kiếm, trả về
2. BĐoán, kiểm tra, lặp lại
3. CChia, trị, kết hợp
4. DĐọc, tính toán, ghi

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. A9 giây
2. B6 giây
3. C12 giây
4. D3 giây

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

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

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

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ACơ số chỉ quan trọng với n nhỏ
2. BMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
3. CLogarit luôn được làm tròn thành số nguyên
4. DCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng

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

1. AĐúng, nhưng chỉ khi n nhỏ hơn 100
2. BKhông, vì n³ nhỏ hơn n² khi n lớn
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ì Big O phải luôn cho tốc độ tăng chính xác của hàm

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AVì nó chỉ hoạt động khi W = 0
2. BVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
3. CVì n luôn nhỏ
4. DW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W

Phát biểu nào về P và NP là đúng?

1. ACác bài toán NP không thể được kiểm chứng nhanh
2. BĐã được chứng minh rằng P ≠ NP
3. CNP có nghĩa là "không đa thức"
4. DMọi bài toán trong P cũng thuộc NP