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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A8 giây
2. B2 giây
3. C1 giây
4. D4 giây

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

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó tự động trả về 0
2. BNó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
3. CNó chạy trong thời gian O(1)
4. DTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toà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. AThuật toán Dijkstra
2. BBắt buộc phải dùng Bellman–Ford trong mọi trường hợp
3. CThuật toán Kruskal
4. DTìm kiếm theo chiều sâu

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
2. BĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
3. CMột thứ tự tô-pô trong O(V²)
4. DMột cây khung nhỏ nhất trong O(E log V)

Phát biểu nào về P và NP là đúng?

1. ACác bài toán NP không thể được kiểm chứng nhanh
2. BMọi bài toán trong P cũng thuộc NP
3. CĐã được chứng minh rằng P ≠ NP
4. DNP có nghĩa là "không đa thức"

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. A2ⁿ tăng nhanh hơn n!
2. Bn! tăng nhanh hơn 2ⁿ
3. CChúng tăng với cùng tốc độ
4. Dn! là O(n²)