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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

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

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Big O của 3n² + 5n + 2 là gì?

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

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

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

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AMột thứ tự tô-pô trong O(V²)
2. BĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
3. CMột cây khung nhỏ nhất trong O(E log V)
4. DĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. A3-SAT, trong đó mỗi mệnh đề có đúng ba literal
2. BThỏa mãn mạch
3. CSAT tổng quát trên các công thức dạng chuẩn tắc hội
4. D2-SAT, trong đó mỗi mệnh đề có tối đa hai literal

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. AKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
2. BCó, nên cận dưới là sai
3. CCó, nhưng chỉ với mảng ngắn hơn 100
4. DKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào