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

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. AHàm mũ
2. BĐa thức
3. CTuyến tính
4. DLogarit

log₂ 1024 bằng bao nhiêu?

1. A32
2. B10
3. C512
4. D12

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. AMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
2. BMọi bài toán con đều có cùng kích thước
3. CBài toán có thể giải trong thời gian hằng số
4. DBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(mn log n)
2. BO(mn)
3. CO(2^m+n)
4. DO(m + n)

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

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMọi phần tử phải được so sánh ít nhất một lần
2. BMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
3. CMỗi phép so sánh mất thời gian logarit
4. DTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. AMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn
2. BSố âm không thể lưu trong hàng đợi ưu tiên
3. CNó chỉ hoạt động trên đồ thị vô hướng
4. DNó rơi vào vòng lặp vô hạn ở mọi cạnh âm