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 của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B512
3. C12
4. D10

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

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

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

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

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

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Ω(log n)
2. BΩ(n)
3. CΩ(n²)
4. DΩ(n log n)

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
2. BViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp
3. CQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt
4. DViệc chọn chỉ có thể thực hiện trong O(n²)

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. ABà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ũ
2. BCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
3. CBà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
4. DBà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