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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A4 giây
2. B1 giây
3. C2 giây
4. D8 giây

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B12
3. C512
4. D10

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

1. AO(n log n + k log n)
2. BO(k n log n)
3. CO(nk)
4. DO(n + k)

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

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

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp chọn (phiên bản điển hình)
2. BSắp xếp trộn
3. CQuicksort (phiên bản tại chỗ điển hình)
4. DSắp xếp vun đống

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức
2. BQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
3. CChứng minh X kiểm chứng được trong thời gian đa thức
4. DChứng minh X không có thuật toán đa thức cho đầu vào nhỏ

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