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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng không được có quá 1000 phần tử
2. BMảng phải được sắp xếp
3. CĐộ dài mảng phải là lũy thừa của hai
4. DMảng chỉ được chứa số dương

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

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

Độ phức tạp không gian đo lường:

1. ADung lượng đĩa của tệp chương trình sau khi được biên dịch
2. BSố dòng mã
3. CLượng bộ nhớ một thuật toán cần khi đầu vào tăng
4. DKích thước vật lý của máy tính

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
2. BCây khung nhỏ nhất
3. CĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
4. DThứ tự tô-pô trong mọi đồ thị

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

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

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CĐúng, nhưng chỉ khi n nhỏ hơn 100
4. DKhông, vì n³ nhỏ hơn n² khi n lớn

Định lý Cook–Levin đã thiết lập điều gì?

1. AMọi bài toán NP đều giải được trong thời gian hàm mũ
2. BBài toán dừng là bất khả quyết định
3. CBài toán thỏa mãn Boole (SAT) là NP-đầy đủ
4. DP không bằng NP

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