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

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

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

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

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

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. CThử mọi lời giải có thể
4. DĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước

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

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

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