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

Thuật toán vét cạn là gì?

1. AThuật toán chạy trên nhiều bộ xử lý
2. BThuật toán luôn dùng đệ quy
3. CThuật toán thử mọi lời giải ứng viên có thể
4. DThuật toán đoán một đáp án ngẫu nhiê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. BChia, trị, kết hợp
3. CĐọc, tính toán, ghi
4. DĐoán, kiểm tra, lặp lại

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A2 giây
2. B4 giây
3. C1 giây
4. D8 giây

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(1)
2. BO(n²)
3. CO(n)
4. DO(log n)

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó chạy trong thời gian O(1)
2. BNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
3. CNó tự động trả về 0
4. DTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toà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. CMọi bài toán con đều có cùng kích thước
4. DBài toán có thể giải trong thời gian hằng số

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

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

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

1. AKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
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. DCó, vì cả hai đều là hàm mũ