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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng log₂ n
2. BKhoảng n / 2
3. CKhoảng n
4. DKhoảng n²

Độ phức tạp không gian đo lường:

1. ALượng bộ nhớ một thuật toán cần khi đầu vào tăng
2. BSố dòng mã
3. CDung lượng đĩa của tệp chương trình sau khi được biên dịch
4. DKích thước vật lý của máy tính

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

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

Một thuật toán tham lam:

1. ALuôn cho lời giải tối ưu
2. BChỉ dùng đệ quy
3. CĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước
4. DThử mọi lời giải có thể

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

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

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

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ái túi phân số, trong đó các món có thể bị chia nhỏ
2. BCả hai biến thể
3. CKhông biến thể nào
4. DBài toán cái túi 0/1, trong đó các món luôn phải được lấy nguyên

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

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