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

Sắp xếp chọn hoạt động như thế nào?

1. ANó chia mảng làm đôi rồi trộn lại
2. BNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
3. CNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
4. DNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng nhanh hơn g một cách nghiêm ngặt
2. Bf tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
3. Cf tăng chậm hơn g một cách nghiêm ngặt
4. Df luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới

Big O của 3n² + 5n + 2 là gì?

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

1. AΩ(n)
2. BΩ(log n)
3. CΩ(n log n)
4. DΩ(n²)

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

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Kruskal
2. BThuật toán Dijkstra
3. CFloyd–Warshall
4. DThuật toán Prim bắt đầu từ một nút

Định lý Cook–Levin đã thiết lập điều gì?

1. AMọi bài toán NP đều giải được trong thời gian hàm mũ
2. BP không bằng NP
3. CBài toán dừng là bất khả quyết định
4. DBài toán thỏa mãn Boole (SAT) là NP-đầy đủ