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 nhị phân trên một mảng đã sắp xếp là gì?

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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ALogarit
2. BHằng số
3. CTuyến tính
4. DBậc hai

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó không có lời giải
2. BNó có thể được giải trong thời gian đa thức
3. CNó có thể được giải trong thời gian hằng số
4. DNó chỉ có thể được giải bằng cách thử mọi khả năng

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

1. AChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
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 một thuật toán trên đầu vào tốt nhất

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ACác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
2. BSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
3. CSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
4. DSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã 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. B3-SAT, trong đó mỗi mệnh đề có đúng ba literal
3. CSAT tổng quát trên các công thức dạng chuẩn tắc hội
4. DThỏa mãn mạch

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

1. AO(V × E)
2. BO(V + E)
3. CO((V + E) log V)
4. DO(V³)