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

Đệ quy là gì?

1. AMột vòng lặp không bao giờ kết thúc
2. BMột hàm gọi chính nó trên các đầu vào nhỏ hơn
3. CMột phương pháp sắp xếp
4. DMột loại cấu trúc dữ liệu

Big O của 3n² + 5n + 2 là gì?

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

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích
2. BChọn hoạt động bắt đầu sớm nhất
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 4 đồng; tối ưu là 3
2. BTham lam dùng 2 đồng; tối ưu là 2
3. CTham lam dùng 3 đồng; tối ưu là 3
4. DTham lam dùng 3 đồng; tối ưu là 2

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị đầy đủ
2. BĐồ thị có trọng số âm
3. CĐồ thị có hướng không chu trình
4. DĐồ thị vô hướng

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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