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

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
2. BThời gian cho một đầu vào có độ dài trung bình
3. CThời gian trên loại máy tính phổ biến nhất
4. DThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n

Độ phức tạp không gian đo lường:

1. ADung lượng đĩa của tệp chương trình sau khi được biên dịch
2. BSố dòng mã
3. CLượng bộ nhớ một thuật toán cần khi đầu vào tăng
4. DKích thước vật lý của máy tính

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
2. BMột cây khung nhỏ nhất trong O(E log V)
3. CMột thứ tự tô-pô trong O(V²)
4. DĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)

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. AThuật toán Kruskal
2. BTìm kiếm theo chiều sâu
3. CThuật toán Dijkstra
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 3 đồng; tối ưu là 3
2. BTham lam dùng 4 đồng; tối ưu là 3
3. CTham lam dùng 3 đồng; tối ưu là 2
4. DTham lam dùng 2 đồng; tối ưu là 2

Phát biểu nào về P và NP là đúng?

1. ACác bài toán NP không thể được kiểm chứng nhanh
2. BNP có nghĩa là "không đa thức"
3. CMọi bài toán trong P cũng thuộc NP
4. DĐã được chứng minh rằng P ≠ NP

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ABài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
2. BBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
3. CCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
4. DBài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ