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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ALời gọi dùng nhiều bộ nhớ nhất
2. BTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
3. CDòng đầu tiên của hàm
4. DTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy

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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó xử lý đúng một phần tử mỗi giây thời gian chạy
2. BNó luôn mất đúng một giây
3. CThời gian chạy của nó không tăng theo kích thước đầu vào
4. DNó chỉ có thể chạy một lần

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

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

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

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

1. AO(log n)
2. BO(n)
3. CO(n²)
4. DO(n log 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^{log₂ 3}), khoảng n^1,585
4. DΘ(n³)

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX thuộc P, và X quy dẫn về SAT
2. BX quy dẫn về một bài toán trong P, và X thuộc NP
3. CX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
4. DX không có thuật toán đa thức, và X quyết định được