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

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

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

Thời gian chạy nào sau đây là đa thức?

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

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

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

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

1. AO(E log V)
2. BO(V³ × E)
3. CO(V × E)
4. DO(V + E)

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

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AVì nó chỉ hoạt động khi W = 0
2. BVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
3. CW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
4. DVì n luôn nhỏ

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Dijkstra
2. BThuật toán Prim bắt đầu từ một nút
3. CFloyd–Warshall
4. DThuật toán Kruskal