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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A1 giây
2. B2 giây
3. C8 giây
4. D4 giây

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

1. Af 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
2. Bf tăng nhanh hơn g một cách nghiêm ngặt
3. Cf 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
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 tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

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

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó bất khả quyết định
2. BNó luôn giải được trong O(V + E)
3. CNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
4. DNó là NP-khó

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán có thể giải song song
2. BCác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
3. CCác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
4. DCác bài toán cần thời gian hàm mũ trên mọi máy tính