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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó luôn mất đúng một giây
2. BThời gian chạy của nó không tăng theo kích thước đầu vào
3. CNó xử lý đúng một phần tử mỗi giây thời gian chạy
4. DNó chỉ có thể chạy một lần

Đệ quy là gì?

1. AMột loại cấu trúc dữ liệu
2. BMột phương pháp sắp xếp
3. CMột hàm gọi chính nó trên các đầu vào nhỏ hơn
4. DMột vòng lặp không bao giờ kết thúc

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))

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 4 đồng; tối ưu là 3
2. BTham lam dùng 3 đồng; tối ưu là 3
3. CTham lam dùng 3 đồng; tối ưu là 2
4. DTham lam dùng 2 đồng; tối ưu là 2

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị đầy đủ
2. BĐồ thị có trọng số âm
3. CĐồ thị có hướng không chu trình
4. DĐồ thị vô hướng

Cận nào là đúng cho log(n!)?

1. AΘ(n)
2. BΘ(log n)
3. CΘ(n log n)
4. DΘ(n²)