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 trộn là gì?

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

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

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

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

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

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

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
2. BNó chạy trong thời gian O(1)
3. CTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toàn
4. DNó tự động trả về 0

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

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

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n^{log₂ 3}), khoảng n^1,585
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n log n)