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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. ALựa chọn tham lam
2. BVét cạn
3. CChia để trị
4. DQuy hoạch động

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó có thể được giải trong thời gian hằng số
2. BNó không có lời giải
3. CNó có thể được giải trong thời gian đa thức
4. DNó chỉ có thể được giải bằng cách thử mọi khả năng

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

1. AO(n)
2. BO(n log n)
3. CO(2ⁿ)
4. DO(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 không có cấu trúc đệ quy
2. BQuy 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
3. CSắp xếp trộn đã là O(n)
4. DCá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

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

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

1. ACác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
2. BCác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
3. CCác bài toán cần thời gian hàm mũ trên mọi máy tính
4. DCác bài toán có thể giải song song

Cận nào là đúng cho log(n!)?

1. AΘ(n)
2. BΘ(n log n)
3. CΘ(log n)
4. DΘ(n²)