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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. AThời gian chạy của nó không tăng theo kích thước đầu vào
2. BNó xử lý đúng một phần tử mỗi giây thời gian chạy
3. CNó chỉ có thể chạy một lần
4. DNó luôn mất đúng một 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. A1 giây
2. B8 giây
3. C4 giây
4. D2 giây

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

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

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

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. AThuật toán Dijkstra
2. BTìm kiếm theo chiều sâu
3. CThuật toán Kruskal
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

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. BBài toán có thể giải trong thời gian hằng số
3. CMộ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
4. DBà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 đó

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

1. ACác phép so sánh trên nút danh sách liên kết chậm hơn
2. BDanh sách liên kết không thể được sắp xếp
3. CTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
4. DĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp

Bài toán dừng cho thấy rằng:

1. ANên tránh các vòng lặp
2. BMột số chương trình chạy nhanh hơn trên máy tính nhanh hơn, nên việc dừng phụ thuộc vào phần cứng
3. CMọi chương trình cuối cùng đều dừng
4. DKhông thuật toán nào có thể quyết định, với mọi chương trình và đầu vào, liệu nó có dừng hay không