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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B512
3. C10
4. D12

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 chỉ được chứa số dương
4. DMảng phải được sắp xếp

Thuật toán vét cạn là gì?

1. AThuật toán chạy trên nhiều bộ xử lý
2. BThuật toán luôn dùng đệ quy
3. CThuật toán thử mọi lời giải ứng viên có thể
4. DThuật toán đoán một đáp án ngẫu nhiên

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

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

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

1. AO(V × E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V + E)

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ACả hai biến thể
2. BKhông biến thể nào
3. CBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên
4. DCái túi phân số, trong đó các món có thể bị chia nhỏ