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

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

1. AO(n)
2. BO(log n)
3. CO(1)
4. DO(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. BChia để trị
3. CQuy hoạch động
4. DVét cạn

Ba bước của một thuật toán chia để trị là gì?

1. AĐoán, kiểm tra, lặp lại
2. BChia, trị, kết hợp
3. CĐọc, tính toán, ghi
4. DSắp xếp, tìm kiếm, trả về

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. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DĐúng, nhưng chỉ khi n nhỏ hơn 100

Thuật toán sắp xếp nào là ổn định?

1. AQuicksort (phiên bản tại chỗ điển hình)
2. BSắp xếp trộn
3. CSắp xếp vun đống
4. DSắp xếp chọn (phiên bản điển hình)

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AMột thứ tự tô-pô trong O(V²)
2. BĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
3. CMột cây khung nhỏ nhất trong O(E log V)
4. DĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)

Một bài toán là NP-đầy đủ nếu nó:

1. ANằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng
2. BGiải được trong thời gian đa thức
3. CKhông thể giải được
4. DThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

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