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

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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

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

1. ATuyến tính
2. BĐa thức
3. CHàm mũ
4. DLogarit

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 1,000
2. BKhoảng 500,000
3. CKhoảng 100
4. DKhoảng 20

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

Phân tích khấu hao đo lường điều gì?

1. AChi phí kỳ vọng trên các đầu vào ngẫu nhiên
2. BChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
3. CChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
4. DChi phí của một thuật toán trên đầu vào tốt nhất

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. BKhông thể giải được
3. CThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
4. DGiải được trong thời gian đa thức

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. AChọn pivot đồng đều ngẫu nhiên
2. BSắp xếp đầu vào trước khi chạy quicksort
3. CLuôn chọn phần tử đầu tiên
4. DChỉ dùng đệ quy ở phía bên trái