Phiếu bài tập Thuật toán và độ phức tạp có đáp á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 / 2
4. DKhoảng 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. AQuicksort
2. BSắp xếp trộn
3. CSắp xếp nổi bọt
4. DSắp xếp vun đống

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

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

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó xóa cạnh đắt nhất cho đến khi không còn chu trình
2. BNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
3. CNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
4. DNó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây

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(d(n + k))
2. BO(n log n)
3. CO(n²)
4. DO(dn log k)

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BKhông, vì n³ nhỏ hơn n² khi n lớn
3. CĐúng, nhưng chỉ khi n nhỏ hơn 100
4. DĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³

Phát biểu nào về P và NP là đúng?

1. ACác bài toán NP không thể được kiểm chứng nhanh
2. BNP có nghĩa là "không đa thức"
3. CĐã được chứng minh rằng P ≠ NP
4. DMọi bài toán trong P cũng thuộc NP

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn
2. BCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O
3. CCó, vì cả hai đều là hàm mũ
4. DKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ