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

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AThời gian cho một đầu vào có độ dài trung bình
2. BThời gian trên loại máy tính phổ biến nhất
3. CGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
4. DThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig O
2. BBig Theta
3. CLittle omega
4. DBig Omega

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

1. AO(1)
2. BO(n)
3. CO(n²)
4. DO(log 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ó đú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 đó
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ó thể giải trong thời gian hằng số
4. DMọi bài toán con đều có cùng kích thước

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. ASắp xếp chèn là O(n log n) trong trường hợp xấu nhất
2. BSắ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
3. CCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
4. DSắ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

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

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

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n), vì mọi hàm đều là little-o của chính nó
2. Bn² = o(n)
3. C2n = o(n), vì 2n tăng chậm
4. Dn = o(n²), nhưng n không phải o(n)