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. B12
3. C512
4. D10

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. ALựa chọn tham lam
2. BChia để trị
3. CVét cạn
4. DQuy hoạch động

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

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

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

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

Công thức truy hồi T(n) = 2T(n − 1) + O(1) có nghiệm là gì?

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

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Kruskal
2. BThuật toán Prim bắt đầu từ một nút
3. CThuật toán Dijkstra
4. DFloyd–Warshall

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
2. BCác bài toán cần thời gian hàm mũ trên mọi máy tính
3. CCác bài toán có thể giải song song
4. DCác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức