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

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

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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp trộn
2. BSắp xếp nổi bọt
3. CSắp xếp chèn
4. DQuicksort

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

1. AO(1)
2. BO(log n)
3. CO(n log 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(log n)
4. DO(n²)

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. AMọi bài toán con đều có cùng kích thước
2. BBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
3. CBài toán có thể giải trong thời gian hằng số
4. DMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con

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

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

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
2. BMọi phần tử phải được so sánh ít nhất một lần
3. CMỗi phép so sánh mất thời gian logarit
4. DTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sá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ó là NP-khó
2. BNó bất khả quyết định
3. CNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
4. DNó luôn giải được trong O(V + E)