Phiếu bài tập Thuật toán và độ phức tạp có đáp án

log₂ 1024 bằng bao nhiêu?

1. A10
2. B12
3. C32
4. D512

Độ 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²)

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian nó mất trên đầu vào nhỏ nhất
2. BThời gian nó mất trên một máy tính chậm
3. CThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
4. DThời gian tối đa nó mất trên mọi đầu vào kích thước n

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(log n)
3. CO(1)
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(n log n + k log n)
4. DO(nk)

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 mà các phần tử đều khác nhau
3. CMột mảng có thứ tự ngẫu nhiên
4. DMột mảng có độ dài 2

Với biến thể bài toán cái túi nào thì quy tắc tham lam "lấy các món theo thứ tự giá trị trên cân nặng" luôn cho đáp án tối ưu?

1. ACả hai biến thể
2. BKhông biến thể nào
3. CBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên
4. DCái túi phân số, trong đó các món có thể bị chia nhỏ

Đị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