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

Thời gian chạy nào sau đây là đa thức?

1. AO(2ⁿ)
2. BO(n³)
3. CO(n!)
4. DO(nⁿ)

Ba bước của một thuật toán chia để trị là gì?

1. AChia, trị, kết hợp
2. BSắp xếp, tìm kiếm, trả về
3. CĐọc, tính toán, ghi
4. DĐoán, kiểm tra, lặp lại

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

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. AMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
2. BCơ số chỉ quan trọng với n nhỏ
3. CCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
4. DLogarit luôn được làm tròn thành số nguyên

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ACác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
2. BSắp xếp trộn đã là O(n)
3. CSắp xếp trộn không có cấu trúc đệ quy
4. DQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng

Một bài toán là NP-đầy đủ nếu nó:

1. AKhông thể giải được
2. BThuộc NP và mọi bài toán NP đều quy dẫn về nó trong thời gian đa thức
3. CGiải được trong thời gian đa thức
4. DNằm ngoài NP nhưng khó hơn mọi bài toán NP, chẳng hạn bài toán dừng

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. ANó chỉ hoạt động trên đồ thị vô hướng
2. BSố âm không thể lưu trong hàng đợi ưu tiên
3. CNó rơi vào vòng lặp vô hạn ở mọi cạnh âm
4. DMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn