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

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΘ (Big Theta)
2. BΩ (Big Omega)
3. CO (Big O)
4. Do (little o)

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 nó mất trên một máy tính chậm
3. CThời gian tối đa nó mất trên mọi đầu vào kích thước n
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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B10
3. C12
4. D512

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động bắt đầu sớm nhất
2. BChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích

Một thuật toán tham lam:

1. ALuôn cho lời giải tối ưu
2. BChỉ dùng đệ quy
3. CThử mọi lời giải có thể
4. DĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước

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

Thuật toán Bellman–Ford phát hiện chu trình trọng số âm có thể đến được từ nguồn bằng cách nào?

1. ANó kiểm tra xem có cạnh nào có trọng số âm không
2. BSau V − 1 vòng, nó kiểm tra xem có cạnh nào vẫn có thể được nới lỏng không
3. CNó đếm các chu trình bằng tìm kiếm theo chiều sâu
4. DNó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách

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

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