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

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
2. Bf tăng nhanh hơn g một cách nghiêm ngặt
3. Cf tăng chậm hơn g một cách nghiêm ngặt
4. Df luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới

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

Ghi nhớ (memoisation) là gì?

1. AGiải phóng bộ nhớ sau khi một hàm trả về
2. BTự độ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
3. CLư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ớ
4. DViết chú thích bên cạnh từng dòng mã

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

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

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

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp trộn
2. BQuicksort (phiên bản tại chỗ điển hình)
3. CSắp xếp chọn (phiên bản điển hình)
4. DSắp xếp vun đống

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
2. BCó, vì cả hai đều là hàm mũ
3. CCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O
4. DKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
2. BCác bài toán cần thời gian hàm mũ trên mọi máy tính
3. CCác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
4. DCác bài toán có thể giải song song