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

Ba bước của một thuật toán chia để trị là gì?

1. ASắp xếp, tìm kiếm, trả về
2. BĐoán, kiểm tra, lặp lại
3. CChia, trị, kết hợp
4. DĐọc, tính toán, ghi

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

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

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

1. AThờ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
2. BThời gian cho một đầu vào có độ dài trung bình
3. CThời gian trên loại máy tính phổ biến nhất
4. DGiá 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

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

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

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

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

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ACơ số chỉ quan trọng với n nhỏ
2. BLogarit luôn được làm tròn thành số nguyên
3. CCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
4. DMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu

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

1. ACá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ỉ
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 không phải đa thức
4. DCác bài toán mà không thuật toán nào giải được

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ASắp xếp đầu vào trước khi chạy quicksort
2. BChỉ dùng đệ quy ở phía bên trái
3. CLuôn chọn phần tử đầu tiên
4. DChọn pivot đồng đều ngẫu nhiên