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

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

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

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(2ⁿ)
4. DO(n²)

Ba bước của một thuật toán chia để trị là gì?

1. AĐoán, kiểm tra, lặp lại
2. BĐọc, tính toán, ghi
3. CChia, trị, kết hợp
4. DSắp xếp, tìm kiếm, trả về

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
2. BCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
3. CSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
4. DSắp xếp chèn là O(n log n) trong trường hợp xấu nhất

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

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

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

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

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó luôn giải được trong O(V + E)
2. BNó là NP-khó
3. CNó bất khả quyết định
4. DNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu