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 nổi bọt
2. BSắp xếp vun đống
3. CSắp xếp trộn
4. DQuicksort

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ATuyến tính
2. BBậc hai
3. CLogarit
4. DHằng số

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ACác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
2. BQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
3. CSắp xếp trộn không có cấu trúc đệ quy
4. DSắp xếp trộn đã là O(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(n log n)
3. CO(n)
4. DO(log n)

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

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

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

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

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
2. BViệc chọn chỉ có thể thực hiện trong O(n²)
3. CQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp