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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BChia để trị
3. CLựa chọn tham lam
4. DVét cạn

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn là O(n log n) trong trường hợp xấu nhất
2. BCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
3. CSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
4. DSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 2 đồng; tối ưu là 2
2. BTham lam dùng 3 đồng; tối ưu là 3
3. CTham lam dùng 4 đồng; tối ưu là 3
4. DTham lam dùng 3 đồng; tối ưu là 2

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), khoảng n^1,585

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

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