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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. ALựa chọn tham lam
2. BQuy hoạch động
3. CVét cạn
4. DChia để trị

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n²
2. BKhoảng log₂ n
3. CKhoảng n
4. DKhoảng n / 2

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í của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
3. CChi phí kỳ vọng trên các đầu vào ngẫu nhiên
4. DChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất

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. BCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
3. CSắ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
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

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Ω(log n)
4. DΩ(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)

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. ACó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
2. BTối đa log n lần giá trị nhỏ nhất
3. CLuôn là một phủ đỉnh nhỏ nhất
4. DKhông rõ chất lượng so với tối ưu