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 của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V²)

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

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

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

1. Af tăng chậm hơn g một cách nghiêm ngặt
2. Bf 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
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 nhanh hơn g một cách nghiêm ngặt

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
2. BChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
3. CChi phí kỳ vọng trên các đầu vào ngẫu nhiên
4. DChi phí của một thuật toán trên đầu vào tốt nhất

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 1,000
2. BKhoảng 500,000
3. CKhoảng 100
4. DKhoảng 20

Vì sao tra cứu trung bình trong bảng băm là O(1) nhưng trường hợp xấu nhất là O(n)?

1. ACác khóa phải được sắp xếp trước
2. BMảng có truy cập O(n)
3. CHàm băm chậm
4. DNhiều khóa có thể va chạm vào cùng một ngăn

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

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