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

Big O của 3n² + 5n + 2 là gì?

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

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

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

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 tối đa nó mất trên mọi đầu vào kích thước n
2. BThời gian nó mất trên đầu vào nhỏ nhất
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 nó mất trên một máy tính chậm

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. AMọi bài toán con đều có cùng kích thước
2. BMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
3. CBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
4. DBài toán có thể giải trong thời gian hằng số

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 100
2. BKhoảng 20
3. CKhoảng 500,000
4. DKhoảng 1,000

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
2. BChọn hoạt động ngắn nhất trước
3. CChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích
4. DChọn hoạt động bắt đầu sớm nhất

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị đầy đủ
2. BĐồ thị có hướng không chu trình
3. CĐồ thị có trọng số âm
4. DĐồ thị vô hướng

Phát biểu nào về ký hiệu little-o là đúng?

1. An² = o(n)
2. Bn = o(n²), nhưng n không phải o(n)
3. C2n = o(n), vì 2n tăng chậm
4. Dn = o(n), vì mọi hàm đều là little-o của chính nó