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

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. ALogarit
2. BBậc hai
3. CTuyến tính
4. DHằng số

Độ 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(n²)
3. CO(n log n)
4. DO(1)

Ghi nhớ (memoisation) là gì?

1. AViết chú thích bên cạnh từng dòng mã
2. BLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
3. CGiải phóng bộ nhớ sau khi một hàm trả về
4. DTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi

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

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

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ASắp xếp trộn đã là O(n)
2. BCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
3. CQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
4. DSắp xếp trộn không có cấu trúc đệ quy

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

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

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ó chỉ hoạt động khi W = 0
2. BW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
3. CVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
4. DVì n luôn nhỏ

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX quy dẫn về một bài toán trong P, và X thuộc NP
2. BX không có thuật toán đa thức, và X quyết định được
3. CX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
4. DX thuộc P, và X quy dẫn về SAT