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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. ALựa chọn tham lam
2. BQuy hoạch động
3. CChia để trị
4. DVét cạ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 dãy hữu hạn các bước được xác định rõ để giải một bài toán
4. DMột cấu trúc dữ liệu lưu trữ các số

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V × E)
2. BO(V²)
3. CO(E log V)
4. DO(V + E)

Độ 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)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(m + n)

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
2. BĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
3. CMột thứ tự tô-pô trong O(V²)
4. DMột cây khung nhỏ nhất trong O(E log V)

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

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

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
2. BVì nó chỉ hoạt động khi W = 0
3. CVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
4. DVì n luôn nhỏ

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

1. AKhô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
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. DNên tránh các vòng lặp