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

Ghi nhớ (memoisation) là gì?

1. ATự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
2. BGiải phóng bộ nhớ sau khi một hàm trả về
3. CViết chú thích bên cạnh từng dòng mã
4. DLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ

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

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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

Độ 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(m + n)
2. BO(mn)
3. CO(mn log n)
4. DO(2^m+n)

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

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

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. AThuật toán Kruskal
2. BThuật toán Dijkstra
3. CBắt buộc phải dùng Bellman–Ford trong mọi trường hợp
4. DTìm kiếm theo chiều sâu

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(n) và không gian O(1)
2. BThời gian O(2ⁿ) và không gian O(1)
3. CThời gian O(log n) và không gian O(n)
4. DThời gian O(n) và không gian O(n)

Vì sao tra cứu trung bình trong bảng băm là O(1) nhưng trường hợp xấu nhất là O(n)?

1. ANhiều khóa có thể va chạm vào cùng một ngăn
2. BHàm băm chậm
3. CCác khóa phải được sắp xếp trước
4. DMảng có truy cập O(n)