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

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A9 giây
2. B3 giây
3. C12 giây
4. D6 giây

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ABậc hai
2. BLogarit
3. CTuyến tính
4. DHằng số

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng n
2. BKhoảng log₂ n
3. CKhoảng √n
4. DKhoảng n / 2

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 Kruskal
2. BTìm kiếm theo chiều sâu
3. CThuật toán Dijkstra
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. ABài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
2. BBài toán có thể giải trong thời gian hằng số
3. CMọi bài toán con đều có cùng kích thước
4. DMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con

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 luôn nhỏ
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. CVì nó chỉ hoạt động khi W = 0
4. DW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(1) mỗi lần tăng
2. BO(n log n) mỗi lần tăng
3. CO(log n) mỗi lần tăng
4. DO(n) mỗi lần tăng