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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó chỉ có thể chạy một lần
2. BNó luôn mất đúng một giây
3. CNó xử lý đúng một phần tử mỗi giây thời gian chạy
4. DThời gian chạy của nó không tăng theo kích thước đầu vào

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. AHằng số
2. BBậc hai
3. CTuyến tính
4. DLogarit

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

1. AĐa thức
2. BLogarit
3. CTuyến tính
4. DHàm mũ

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ASắp xếp trộn không có cấu trúc đệ quy
2. BCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
3. CQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
4. DSắp xếp trộn đã là O(n)

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
2. BSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
3. CSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
4. DCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
2. BThứ tự tô-pô trong mọi đồ thị
3. CĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
4. DCây khung nhỏ nhất

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

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. A2ⁿ tăng nhanh hơn n!
2. Bn! tăng nhanh hơn 2ⁿ
3. CChúng tăng với cùng tốc độ
4. Dn! là O(n²)