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

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. BQuy hoạch động
3. CChia để trị
4. DVét cạn

Sắp xếp chọn hoạt động như thế nào?

1. ANó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
2. BNó chia mảng làm đôi rồi trộn lại
3. CNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
4. DNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyể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. ACác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
2. BSắ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
3. CSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
4. DSắ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

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

1. AMột cây khung nhỏ nhất trong O(E log 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. CĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
4. DMột thứ tự tô-pô trong O(V²)

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

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

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ACả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
2. BBài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ
3. CBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
4. DBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
2. BQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức
3. CQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
4. DChứng minh X kiểm chứng được trong thời gian đa thức