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

Thuật toán là gì?

1. AMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
2. BBất kỳ chương trình máy tính nào có giao diện đồ họa
3. CMột cấu trúc dữ liệu lưu trữ các số
4. DMột dãy hữu hạn các bước được xác định rõ để giải một bài toán

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

1. ANó luôn mất đúng một giây
2. BThời gian chạy của nó không tăng theo kích thước đầu vào
3. CNó xử lý đúng một phần tử mỗi giây thời gian chạy
4. DNó chỉ có thể chạy một lần

Thời gian chạy nào sau đây là đa thức?

1. AO(2ⁿ)
2. BO(n³)
3. CO(nⁿ)
4. DO(n!)

Quy hoạch động hữu ích khi một bài toán có:

1. AChỉ các đầu vào ngẫu nhiên
2. BHoàn toàn không có bài toán con, nên có thể giải trong một bước
3. CMột vòng lặp duy nhất
4. DCác bài toán con chồng lặp và cấu trúc con tối ưu

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

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

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

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

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. ADanh sách liên kết không thể được sắp xếp
2. BCác phép so sánh trên nút danh sách liên kết chậm hơn
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

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán cần thời gian hàm mũ trên mọi máy tính
2. BCác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
3. CCác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
4. DCác bài toán có thể giải song song