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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig Omega
2. BBig Theta
3. CLittle omega
4. DBig O

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Công thức truy hồi T(n) = T(n − 1) + O(n) có nghiệm là gì?

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

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

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

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AThứ tự tô-pô trong mọi đồ thị
2. BĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
3. CCây khung nhỏ nhất
4. DĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ACả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
2. BBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
3. CBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
4. DBài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ

Cận nào là đúng cho log(n!)?

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