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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AĐộ dài mảng phải là lũy thừa của hai
2. BMảng chỉ được chứa số dương
3. CMảng không được có quá 1000 phần tử
4. DMảng phải được sắp xếp

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới
2. Bf tăng nhanh hơn g một cách nghiêm ngặt
3. Cf tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
4. Df tăng chậm hơn g một cách nghiêm ngặt

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

Quy hoạch động hữu ích khi một bài toán có:

1. AHoàn toàn không có bài toán con, nên có thể giải trong một bước
2. BCác bài toán con chồng lặp và cấu trúc con tối ưu
3. CChỉ các đầu vào ngẫu nhiên
4. DMột vòng lặp duy nhất

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

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

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

Phát biểu nào về ký hiệu little-o là đúng?

1. An² = o(n)
2. Bn = o(n²), nhưng n không phải o(n)
3. C2n = o(n), vì 2n tăng chậm
4. Dn = o(n), vì mọi hàm đều là little-o của chính nó

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n² log n)