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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

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

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

Sắp xếp chọn hoạt động như thế nào?

1. ANó chia mảng làm đôi rồi trộn lại
2. BNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
3. CNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
4. DNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyể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. AHằng số
2. BTuyến tính
3. CHàm mũ
4. DLogarit

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

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

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó xóa cạnh đắt nhất cho đến khi không còn chu trình
2. BNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây
3. CNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
4. DNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS

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. ASAT tổng quát trên các công thức dạng chuẩn tắc hội
2. B2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
3. C3-SAT, trong đó mỗi mệnh đề có đúng ba literal
4. DThỏa mãn mạch

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. BQuickselect 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
3. CViệc chọn chỉ có thể thực hiện trong O(n²)
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp