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

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

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

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

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

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

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BThuật toán Kruskal
3. CTìm kiếm theo chiều sâu
4. DThuật toán Dijkstra

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

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

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. ACó, nhưng chỉ với mảng ngắn hơn 100
2. BKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào
3. CCó, nên cận dưới là sai
4. DKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh

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

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