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

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

1. AĐọc, tính toán, ghi
2. BĐoán, kiểm tra, lặp lại
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 trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian nó mất trên đầu vào nhỏ nhất
2. BThời gian tối đa nó mất trên mọi đầu vào kích thước n
3. CThời gian nó mất trên một máy tính chậm
4. DThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AĐúng, nhưng chỉ khi n nhỏ hơn 100
2. BKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
3. CĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
4. DKhông, vì n³ nhỏ hơn n² khi n lớn

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(2^m+n)
2. BO(mn log n)
3. CO(m + n)
4. DO(mn)

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

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

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ACái túi phân số, trong đó các món có thể bị chia nhỏ
2. BCả hai biến thể
3. CBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên
4. DKhông biến thể nào

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
2. BChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
3. CChứng minh X kiểm chứng được trong thời gian đa thức
4. DQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức