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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng không được có quá 1000 phần tử
2. BĐộ dài mảng phải là lũy thừa của hai
3. CMảng phải được sắp xếp
4. DMảng chỉ được chứa số dương

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A8 giây
2. B4 giây
3. C1 giây
4. D2 giây

Ghi nhớ (memoisation) là gì?

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

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. ACác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
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. DSắ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

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

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n), vì mọi hàm đều là little-o của chính nó
2. B2n = o(n), vì 2n tăng chậm
3. Cn² = o(n)
4. Dn = o(n²), nhưng n không phải o(n)

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. ATối đa log n lần giá trị nhỏ nhất
2. BLuôn là một phủ đỉnh nhỏ nhất
3. CCó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
4. DKhông rõ chất lượng so với tối ưu