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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp vun đống
2. BQuicksort
3. CSắp xếp nổi bọt
4. DSắp xếp trộn

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

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

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

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

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 ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
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 là O(n log n) trong trường hợp xấu nhấ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

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(dn log k)
2. BO(n²)
3. CO(n log n)
4. DO(d(n + k))

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n log n)
2. BΘ(n^{log₂ 3}), khoảng n^1,585
3. CΘ(n³)
4. DΘ(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. CKhông rõ chất lượng so với tối ưu
4. DLuôn là một phủ đỉnh nhỏ nhất