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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp nổi bọt
2. BSắp xếp trộn
3. CSắp xếp chèn
4. DQuicksort

Độ 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(E log V)
2. BO(V²)
3. CO(V × E)
4. DO(V + E)

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

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

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AĐúng, nhưng chỉ khi n nhỏ hơn 100
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm

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

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

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

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

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n^{log₂ 7}), khoảng n^2,81