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

log₂ 1024 bằng bao nhiêu?

1. A10
2. B32
3. C512
4. D12

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

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

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

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

1. AHàm mũ
2. BHằng số
3. CLogarit
4. DTuyến tính

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng có độ dài 2
2. BMột mảng có thứ tự ngẫu nhiên
3. CMột mảng đã được sắp xếp
4. DMột mảng mà các phần tử đều khác nhau

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n²), nhưng n không phải o(n)
2. B2n = o(n), vì 2n tăng chậm
3. Cn = o(n), vì mọi hàm đều là little-o của chính nó
4. Dn² = o(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²)
2. BΘ(n log n)
3. CΘ(n³)
4. DΘ(n^{log₂ 3}), khoảng n^1,585