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 chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. AQuicksort
2. BSắp xếp nổi bọt
3. CSắp xếp chèn
4. DSắp xếp trộ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ó 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
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ó chia mảng làm đôi rồi trộn lại

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. ATuyến tính
2. BĐa thức
3. CHàm mũ
4. DLogarit

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

1. AO(k n log n)
2. BO(n + k)
3. CO(nk)
4. DO(n log n + k log n)

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

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

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

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

1. ACác bài toán không thể giải trong thời gian đa thức
2. BCác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ
3. CCác bài toán mà không thuật toán nào giải được
4. DCác bài toán không phải đa thức