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

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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 1,000
2. BKhoảng 100
3. CKhoảng 20
4. DKhoảng 500,000

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng đã được sắp xếp
2. BMột mảng có thứ tự ngẫu nhiên
3. CMột mảng mà các phần tử đều khác nhau
4. DMột mảng có độ dài 2

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(2ⁿ) và không gian O(1)
2. BThời gian O(log n) và không gian O(n)
3. CThời gian O(n) và không gian O(n)
4. DThời gian O(n) và không gian O(1)

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

1. ACác bài toán không phải đa thức
2. BCác bài toán không thể giải trong thời gian đa thức
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 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ỉ