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 trong trường hợp xấu nhất của sắp xếp chèn là gì?

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

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

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

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

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. ALogarit
2. BTuyến tính
3. CHằng số
4. DHàm mũ

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

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

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

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

Định nghĩa nào của lớp NP là đúng?

1. ACác bài toán mà không thuật toán nào giải được
2. BCác bài toán không thể giải trong thời gian đa thức
3. CCác bài toán không phải đa thức
4. DCác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ

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ì nó chỉ hoạt động khi W = 0
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ì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào