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 tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. ATuyến tính
2. BHằng số
3. CHàm mũ
4. DLogarit

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

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

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

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị đầy đủ
2. BĐồ thị vô hướng
3. CĐồ thị có trọng số âm
4. DĐồ thị có hướng không chu trình

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
2. BViệc chọn chỉ có thể thực hiện trong O(n²)
3. CQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp