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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AĐộ dài mảng phải là lũy thừa của hai
2. BMảng phải được sắp xếp
3. CMảng không được có quá 1000 phần tử
4. DMảng chỉ được chứa số dương

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

1. AĐa thức
2. BHàm mũ
3. CLogarit
4. DTuyến tính

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

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

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

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

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

Bài toán người bán hàng rong được phân loại thế nào?

1. APhiên bản quyết định thuộc P nhưng phiên bản tối ưu hóa là NP-đầy đủ
2. BNó bất khả quyết định
3. CNó thuộc P vì thuật toán Dijkstra giải được nó bằng cách thăm mỗi thành phố một lần
4. DPhiên bản quyết định là NP-đầy đủ và phiên bản tối ưu hóa là NP-khó

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ỉ dùng đệ quy ở phía bên trái
2. BChọn pivot đồng đều ngẫu nhiên
3. CLuôn chọn phần tử đầu tiên
4. DSắp xếp đầu vào trước khi chạy quicksort