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ó luôn mất đúng một giây
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

log₂ 1024 bằng bao nhiêu?

1. A512
2. B32
3. C10
4. D12

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp vun đống
2. BQuicksort
3. CSắp xếp nổi bọt
4. DSắp xếp trộn

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(mn log n)
2. BO(m + n)
3. CO(mn)
4. DO(2^m+n)

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Bài toán người bán hàng rong được phân loại thế nào?

1. ANó thuộc P vì thuật toán Dijkstra giải được nó bằng cách thăm mỗi thành phố một lần
2. BNó bất khả quyết định
3. CPhiên bản quyết định thuộc P nhưng phiên bản tối ưu hóa là NP-đầy đủ
4. DPhiên bản quyết định là NP-đầy đủ và phiên bản tối ưu hóa là NP-khó

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMỗi phép so sánh mất thời gian logarit
2. BMọi phần tử phải được so sánh ít nhất một lần
3. CMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
4. DTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh