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

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian nó mất trên đầu vào nhỏ nhất
2. BThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
3. CThời gian nó mất trên một máy tính chậm
4. DThời gian tối đa nó mất trên mọi đầu vào kích thước n

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(nk)
2. BO(n + k)
3. CO(n log n + k log n)
4. DO(k n log 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. CMộ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
4. DBài toán có thể giải trong thời gian hằng số

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
2. BViệc chọn chỉ có thể thực hiện trong O(n²)
3. CQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. A2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
2. BThỏa mãn mạch
3. CSAT tổng quát trên các công thức dạng chuẩn tắc hội
4. D3-SAT, trong đó mỗi mệnh đề có đúng ba literal