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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AQuy hoạch động
2. BChia để trị
3. CVét cạn
4. DLựa chọn tham lam

Thuật toán là gì?

1. AMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
2. BBất kỳ chương trình máy tính nào có giao diện đồ họa
3. CMột cấu trúc dữ liệu lưu trữ các số
4. DMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học

Độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp chèn là gì?

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

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

Độ 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(log n)
3. CO(n)
4. DO(n log n)

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

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

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
2. BCác bài toán có thể giải song song
3. CCác bài toán cần thời gian hàm mũ trên mọi máy tính
4. DCác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức

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₂ 3}), khoảng n^1,585
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n log n)