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

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A6 giây
2. B9 giây
3. C12 giây
4. D3 giây

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A2 giây
2. B1 giây
3. C8 giây
4. D4 giây

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 n / 2
2. BKhoảng n
3. CKhoảng log₂ n
4. DKhoảng n²

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

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

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AThứ tự tô-pô trong mọi đồ thị
2. BCây khung nhỏ nhất
3. CĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
4. DĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(n) và không gian O(1)
2. BThời gian O(2ⁿ) và không gian O(1)
3. CThời gian O(log n) và không gian O(n)
4. DThời gian O(n) và không gian O(n)

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. ALuôn chọn phần tử đầu tiên
2. BChọn pivot đồng đều ngẫu nhiên
3. CChỉ dùng đệ quy ở phía bên trái
4. DSắp xếp đầu vào trước khi chạy quicksort