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

Ghi nhớ (memoisation) là gì?

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

Big O của 3n² + 5n + 2 là gì?

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

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. ABậc hai
2. BLogarit
3. CHằng số
4. DTuyến tính

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BTìm kiếm theo chiều sâu
3. CThuật toán Kruskal
4. DThuật toán Dijkstra

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng mà các phần tử đều khác nhau
2. BMột mảng đã được sắp xếp
3. CMột mảng có thứ tự ngẫu nhiên
4. DMột mảng có độ dài 2

Quy hoạch động hữu ích khi một bài toán có:

1. ACác bài toán con chồng lặp và cấu trúc con tối ưu
2. BChỉ các đầu vào ngẫu nhiên
3. CMột vòng lặp duy nhất
4. DHoàn toàn không có bài toán con, nên có thể giải trong một bước

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. AKhông rõ chất lượng so với tối ưu
2. BCó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
3. CTối đa log n lần giá trị nhỏ nhất
4. DLuôn là một phủ đỉnh nhỏ nhất

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(1) mỗi lần tăng
2. BO(log n) mỗi lần tăng
3. CO(n) mỗi lần tăng
4. DO(n log n) mỗi lần tăng