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. ALittle omega
2. BBig Omega
3. CBig O
4. DBig Theta

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

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(dn log k)
2. BO(n log n)
3. CO(d(n + k))
4. DO(n²)

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

1. ABài toán có thể giải trong thời gian hằng số
2. BMộ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
3. CBà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 đó
4. DMọi bài toán con đều có cùng kích thước

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

Một bài toán là NP-đầy đủ nếu nó:

1. ANằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng
2. BGiải được trong thời gian đa thức
3. CKhông thể giải được
4. DThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức

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ỗi phép so sánh mất thời gian logarit
2. BTì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
3. CMọi phần tử phải được so sánh ít nhất một lần
4. DMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n