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(log n)
2. BO(1)
3. CO(n²)
4. DO(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. BMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
3. CMột cấu trúc dữ liệu lưu trữ các số
4. DBất kỳ chương trình máy tính nào có giao diện đồ họa

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

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

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của một thuật toán trên đầu vào tốt nhất
2. BChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
3. CChi phí kỳ vọng trên các đầu vào ngẫu nhiên
4. DChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(n²)
2. BO(d(n + k))
3. CO(dn log k)
4. DO(n log 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. ASắp xếp đầu vào trước khi chạy quicksort
2. BChỉ dùng đệ quy ở phía bên trái
3. CChọn pivot đồng đều ngẫu nhiên
4. DLuôn chọn phần tử đầu tiên

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

1. ANó bất khả quyết định
2. BPhiên bản quyết định là NP-đầy đủ và phiên bản tối ưu hóa là NP-khó
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. DNó 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