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 trộn
4. DSắp xếp chèn

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
2. BThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n
3. CThời gian trên loại máy tính phổ biến nhất
4. DThời gian cho một đầu vào có độ dài trung bình

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó luôn mất đúng một giây
2. BThời gian chạy của nó không tăng theo kích thước đầu vào
3. CNó xử lý đúng một phần tử mỗi giây thời gian chạy
4. DNó chỉ có thể chạy một lần

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

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Quy hoạch động hữu ích khi một bài toán có:

1. AMột vòng lặp duy nhất
2. BHoàn toàn không có bài toán con, nên có thể giải trong một bước
3. CChỉ các đầu vào ngẫu nhiên
4. DCác bài toán con chồng lặp và cấu trúc con tối ưu

Phát biểu nào về P và NP là đúng?

1. ACác bài toán NP không thể được kiểm chứng nhanh
2. BMọi bài toán trong P cũng thuộc NP
3. CNP có nghĩa là "không đa thức"
4. DĐã được chứng minh rằng P ≠ NP

Cận nào là đúng cho log(n!)?

1. AΘ(log n)
2. BΘ(n²)
3. CΘ(n)
4. DΘ(n log n)