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

Thuật toán vét cạn là gì?

1. AThuật toán đoán một đáp án ngẫu nhiên
2. BThuật toán luôn dùng đệ quy
3. CThuật toán thử mọi lời giải ứng viên có thể
4. DThuật toán chạy trên nhiều bộ xử lý

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

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

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

Quy hoạch động hữu ích khi một bài toán có:

1. AHoàn toàn không có bài toán con, nên có thể giải trong một bước
2. BChỉ các đầu vào ngẫu nhiên
3. CMột vòng lặp duy nhất
4. DCác bài toán con chồng lặp và cấu trúc con tối ưu

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(log n) và không gian O(n)
2. BThời gian O(n) và không gian O(n)
3. CThời gian O(n) và không gian O(1)
4. DThời gian O(2ⁿ) và không gian O(1)

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. ALuôn là một phủ đỉnh nhỏ nhất
2. BKhông rõ chất lượng so với tối ưu
3. CTối đa log n lần giá trị nhỏ nhất
4. DCó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất