Phiếu bài tập Thuật toán và độ phức tạp có đáp á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. 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ớ

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

1. Af tăng chậm hơn g một cách nghiêm ngặt
2. Bf 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
3. Cf tăng nhanh hơn g một cách nghiêm ngặt
4. Df 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

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

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

1. ALuôn cho lời giải tối ưu
2. BThử mọi lời giải có thể
3. CChỉ dùng đệ quy
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(1) có nghiệm là gì?

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

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. ANó chỉ hoạt động trên đồ thị vô hướng
2. BSố âm không thể lưu trong hàng đợi ưu tiên
3. CNó rơi vào vòng lặp vô hạn ở mọi cạnh âm
4. DMộ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

Định lý Cook–Levin đã thiết lập điều gì?

1. AMọi bài toán NP đều giải được trong thời gian hàm mũ
2. BBài toán dừng là bất khả quyết định
3. CBài toán thỏa mãn Boole (SAT) là NP-đầy đủ
4. DP không bằng NP