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

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

1. ABig O
2. BBig Omega
3. CBig Theta
4. DLittle omega

Thuật toán vét cạn là gì?

1. AThuật toán luôn dùng đệ quy
2. BThuật toán đoán một đáp án ngẫu nhiên
3. CThuật toán chạy trên nhiều bộ xử lý
4. DThuật toán thử mọi lời giải ứng viên có thể

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp trộn
2. BSắp xếp nổi bọt
3. CQuicksort
4. DSắp xếp chè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(n²)
2. BO(n log n)
3. CO(dn log k)
4. DO(d(n + k))

Công thức truy hồi T(n) = 2T(n/2) + O(1) có nghiệm là gì?

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

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. ACác phép so sánh trên nút danh sách liên kết chậm hơn
2. BTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
3. CDanh sách liên kết không thể được sắp xếp
4. DĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. An! tăng nhanh hơn 2ⁿ
2. Bn! là O(n²)
3. CChúng tăng với cùng tốc độ
4. D2ⁿ tăng nhanh hơn n!