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

Độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp trộn là gì?

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

Đệ quy là gì?

1. AMột hàm gọi chính nó trên các đầu vào nhỏ hơn
2. BMột vòng lặp không bao giờ kết thúc
3. CMột loại cấu trúc dữ liệu
4. DMột phương pháp sắp xếp

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng không được có quá 1000 phần tử
2. BMảng phải được sắp xếp
3. CĐộ dài mảng phải là lũy thừa của hai
4. DMảng chỉ được chứa số dương

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn là O(n log n) trong trường hợp xấu nhất
2. BSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
3. CCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
4. DSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

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 log n)
2. BO(d(n + k))
3. CO(n²)
4. DO(dn log k)

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. CNó 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
4. DPhiên bản quyết định thuộc P nhưng phiên bản tối ưu hóa là NP-đầy đủ

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

1. ANên tránh các vòng lặp
2. BKhô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
3. CMộ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
4. DMọi chương trình cuối cùng đều dừng