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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig O
2. BBig Omega
3. CLittle omega
4. DBig Theta

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng chậm hơn g một cách nghiêm ngặt
2. Bf tăng nhanh hơn g một cách nghiêm ngặt
3. Cf luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới
4. Df tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g

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

1. AHàm mũ
2. BLogarit
3. CĐa thức
4. DTuyến tính

Độ 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)

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

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

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. BMột vòng lặp duy nhất
3. CHoàn toàn không có bài toán con, nên có thể giải trong một bước
4. DChỉ các đầu vào ngẫu nhiên

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

1. ACác bài toán không phải đa thức
2. BCác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ
3. CCác bài toán không thể giải trong thời gian đa thức
4. DCác bài toán mà không thuật toán nào giải được

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó là NP-khó
2. BNó luôn giải được trong O(V + E)
3. CNó bất khả quyết định
4. DNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu