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

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

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

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

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

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

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

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng n / 2
2. BKhoảng log₂ n
3. CKhoảng n
4. DKhoảng √n

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ì n luôn nhỏ
3. CVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
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é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₂ 3}), khoảng n^1,585
3. CΘ(n³)
4. DΘ(n log n)